找到一个数字的最高有效位-yiteyi-C++库

给定一个数，找出比给定的一个数（2的幂）小的最大数，或者找到最有效的位数。

null

例如：

Input : 10Output : 8Greatest number which is a Power of 2 less than 10 is 8Binary representation of 10 is 1010The most significant bit correspondsto decimal number 8.Input : 18Output : 16

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 简单解决方案 将n除以2，直到它变为0，并在执行此操作时增加一个计数。此计数实际上代表MSB的位置。

C++

                         // Simple CPP program to find MSB number                       
                         // for given n.                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     setBitNumber(                                     int                                     n)                       
                         {                       
                                                 if                                     (n == 0)                       
                                                 return                                     0;                       
           
                                                 int                                     msb = 0;                       
                                                 n = n / 2;                       
                                                 while                                     (n != 0) {                       
                                                 n = n / 2;                       
                                                 msb++;                       
                                                 }                       
           
                                                 return                                     (1 << msb);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 0;                       
                                                 cout << setBitNumber(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Simple Java program to find                       
                         // MSB number for given n.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                                 static                                     int                                     setBitNumber(                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n ==                                     0                                     )                       
                                                 return                                     0                                     ;                       
           
                                                 int                                     msb =                                     0                                     ;                       
                                                 n = n /                                     2                                     ;                       
           
                                                 while                                     (n !=                                     0                                     ) {                       
                                                 n = n /                                     2                                     ;                       
                                                 msb++;                       
                                                 }                       
           
                                                 return                                     (                                     1                                     << msb);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     0                                     ;                       
                                                 System.out.println(setBitNumber(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by ajit                       

Python3

                         # Simple Python3 program                       
                         # to find MSB number                       
                         # for given n.                       
                         def                                     setBitNumber(n):                       
                                                 if                                     (n                                     =                                     =                                     0                                     ):                       
                                                 return                                     0                                     ;                       
           
                                                 msb                                     =                                     0                                     ;                       
                                                 n                                     =                                     int                                     (n                                     /                                     2                                     );                       
           
                                                 while                                     (n >                                     0                                     ):                       
                                                 n                                     =                                     int                                     (n                                     /                                     2                                     );                       
                                                 msb                                     +                                     =                                     1                                     ;                       
           
                                                 return                                     (                                     1                                     << msb);                       
           
                         # Driver code                       
                         n                                     =                                     0                                     ;                       
                         print                                     (setBitNumber(n));                       
                                   
                         # This code is contributed                       
                         # by mits                       

C#

                         // Simple C# program to find                       
                         // MSB number for given n.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                                 static                                     int                                     setBitNumber(                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n == 0)                       
                                                 return                                     0;                       
           
                                                 int                                     msb = 0;                       
                                                 n = n / 2;                       
           
                                                 while                                     (n != 0) {                       
                                                 n = n / 2;                       
                                                 msb++;                       
                                                 }                       
           
                                                 return                                     (1 << msb);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     public                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 0;                       
                                                 Console.WriteLine(setBitNumber(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by akt_mit                       

PHP

                         <?php                       
                         // Simple PhP program                       
                         // to find MSB number                       
                         // for given n.                       
           
                         function                                     setBitNumber(                                     $n                                     )                       
                         {                       
                                                 if                                     (                                     $n                                     == 0)                       
                                                 return                                     0;                       
           
                                                 $msb                                     = 0;                       
                                                 $n                                     =                                     $n                                     / 2;                       
           
                                                 while                                     (                                     $n                                     != 0)                       
                                                 {                       
                                                 $n                                     =                                     $n                                     / 2;                       
                                                 $msb                                     ++;                       
                                                 }                       
           
                                                 return                                     (1 <<                                     $msb                                     );                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 0;                       
                         echo                                     setBitNumber(                                     $n                                     );                       
                                   
                         // This code is contributed                       
                         // by akt_mit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript  program                       
                         // to find MSB number                       
                         // for given n.                       
           
                         function                                     setBitNumber(n)                       
                         {                       
                                                 if                                     (n == 0)                       
                                                 return                                     0;                       
           
                                                 let msb = 0;                       
                                                 n = n / 2;                       
           
                                                 while                                     (n != 0)                       
                                                 {                       
                                                 n = $n / 2;                       
                                                 msb++;                       
                                                 }                       
           
                                                 return                                     (1 << msb);                       
                         }                       
           
                         // Driver code                       
                         let n = 0;                       
                         document.write (setBitNumber(n));                       
                                   
                         // This code is contributed by Bobby                       
           
                         </script>                       

输出：

一 有效解决方案 对于固定大小的整数（例如32位），请逐个设置位，然后加1，以便只设置MSB后面的位。最后右移1并返回答案。此解决方案不需要任何条件检查。

C++

                         // CPP program to find MSB number for given n.                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     setBitNumber(                                     int                                     n)                       
                         {                       
                                                 // Below steps set bits after                       
                                                 // MSB (including MSB)                       
           
                                                 // Suppose n is 273 (binary                       
                                                 // is 100010001). It does following                       
                                                 // 100010001 | 010001000 = 110011001                       
                                                 n |= n >> 1;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set. It does following                       
                                                 // 110011001 | 001100110 = 111111111                       
                                                 n |= n >> 2;                       
           
                                                 n |= n >> 4;                       
                                                 n |= n >> 8;                       
                                                 n |= n >> 16;                       
           
                                                 // Increment n by 1 so that                       
                                                 // there is only one set bit                       
                                                 // which is just before original                       
                                                 // MSB. n now becomes 1000000000                       
                                                 n = n + 1;                       
           
                                                 // Return original MSB after shifting.                       
                                                 // n now becomes 100000000                       
                                                 return                                     (n >> 1);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 273;                       
                                                 cout << setBitNumber(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find MSB                       
                         // number for given n.                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     setBitNumber(                                     int                                     n)                       
                                                 {                       
           
                                                 // Below steps set bits after                       
                                                 // MSB (including MSB)                       
           
                                                 // Suppose n is 273 (binary                       
                                                 // is 100010001). It does following                       
                                                 // 100010001 | 010001000 = 110011001                       
                                                 n |= n >>                                     1                                     ;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set. It does following                       
                                                 // 110011001 | 001100110 = 111111111                       
                                                 n |= n >>                                     2                                     ;                       
           
                                                 n |= n >>                                     4                                     ;                       
                                                 n |= n >>                                     8                                     ;                       
                                                 n |= n >>                                     16                                     ;                       
           
                                                 // Increment n by 1 so that                       
                                                 // there is only one set bit                       
                                                 // which is just before original                       
                                                 // MSB. n now becomes 1000000000                       
                                                 n = n +                                     1                                     ;                       
           
                                                 // Return original MSB after shifting.                       
                                                 // n now becomes 100000000                       
                                                 return                                     (n >>                                     1                                     );                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String arg[])                       
                                                 {                       
                                                 int                                     n =                                     273                                     ;                       
                                                 System.out.print(setBitNumber(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python program to find                       
                         # MSB number for given n.                       
           
                         def                                     setBitNumber(n):                       
           
                                                 # Below steps set bits after                       
                                                 # MSB (including MSB)                       
                                   
                                                 # Suppose n is 273 (binary                       
                                                 # is 100010001). It does following                       
                                                 # 100010001 | 010001000 = 110011001                       
                                                 n |                                     =                                     n>>                                     1                       
                                   
                                                 # This makes sure 4 bits                       
                                                 # (From MSB and including MSB)                       
                                                 # are set. It does following                       
                                                 # 110011001 | 001100110 = 111111111                       
                                                 n |                                     =                                     n>>                                     2                       
                                   
                                                 n |                                     =                                     n>>                                     4                       
                                                 n |                                     =                                     n>>                                     8                       
                                                 n |                                     =                                     n>>                                     16                       
                                   
                                                 # Increment n by 1 so that                       
                                                 # there is only one set bit                       
                                                 # which is just before original                       
                                                 # MSB. n now becomes 1000000000                       
                                                 n                                     =                                     n                                     +                                     1                       
                                   
                                                 # Return original MSB after shifting.                       
                                                 # n now becomes 100000000                       
                                                 return                                     (n >>                                     1                                     )                       
           
                         # Driver code                       
           
                         n                                     =                                     273                       
                         print                                     (setBitNumber(n))                       
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# program to find MSB number for given n.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     setBitNumber(                                     int                                     n)                       
                                                 {                       
           
                                                 // Below steps set bits after                       
                                                 // MSB (including MSB)                       
           
                                                 // Suppose n is 273 (binary                       
                                                 // is 100010001). It does following                       
                                                 // 100010001 | 010001000 = 110011001                       
                                                 n |= n >> 1;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set. It does following                       
                                                 // 110011001 | 001100110 = 111111111                       
                                                 n |= n >> 2;                       
           
                                                 n |= n >> 4;                       
                                                 n |= n >> 8;                       
                                                 n |= n >> 16;                       
           
                                                 // Increment n by 1 so that                       
                                                 // there is only one set bit                       
                                                 // which is just before original                       
                                                 // MSB. n now becomes 1000000000                       
                                                 n = n + 1;                       
           
                                                 // Return original MSB after shifting.                       
                                                 // n now becomes 100000000                       
                                                 return                                     (n >> 1);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 273;                       
                                                 Console.WriteLine(setBitNumber(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

PHP

                         <?php                       
                         // PHP program to find                       
                         // MSB number for given n.                       
           
                         function                                     setBitNumber(                                     $n                                     )                       
                         {                       
                                                 // Below steps set bits                       
                                                 // after MSB (including MSB)                       
           
                                                 // Suppose n is 273 (binary                       
                                                 // is 100010001). It does                       
                                                 // following 100010001 |                       
                                                 // 010001000 = 110011001                       
                                                 $n                                     |=                                     $n                                     >> 1;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including                       
                                                 // MSB) are set. It does                       
                                                 // following 110011001 |                       
                                                 // 001100110 = 111111111                       
                                                 $n                                     |=                                     $n                                     >> 2;                       
           
                                                 $n                                     |=                                     $n                                     >> 4;                       
                                                 $n                                     |=                                     $n                                     >> 8;                       
                                                 $n                                     |=                                     $n                                     >> 16;                       
           
                                                 // Increment n by 1 so                       
                                                 // that there is only                       
                                                 // one set bit which is                       
                                                 // just before original                       
                                                 // MSB. n now becomes                       
                                                 // 1000000000                       
                                                 $n                                     =                                     $n                                     + 1;                       
           
                                                 // Return original MSB                       
                                                 // after shifting. n                       
                                                 // now becomes 100000000                       
                                                 return                                     (                                     $n                                     >> 1);                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 273;                       
                         echo                                     setBitNumber(                                     $n                                     );                       
           
                         // This code is contributed                       
                         // by akt_mit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find MSB                       
                         // number for given n.                       
                         function                                     setBitNumber(n)                       
                         {                       
                                   
                                                 // Below steps set bits after                       
                                                 // MSB (including MSB)                       
           
                                                 // Suppose n is 273 (binary                       
                                                 // is 100010001). It does following                       
                                                 // 100010001 | 010001000 = 110011001                       
                                                 n |= n >> 1;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set. It does following                       
                                                 // 110011001 | 001100110 = 111111111                       
                                                 n |= n >> 2;                       
           
                                                 n |= n >> 4;                       
                                                 n |= n >> 8;                       
                                                 n |= n >> 16;                       
           
                                                 // Increment n by 1 so that                       
                                                 // there is only one set bit                       
                                                 // which is just before original                       
                                                 // MSB. n now becomes 1000000000                       
                                                 n = n + 1;                       
           
                                                 // Return original MSB after shifting.                       
                                                 // n now becomes 100000000                       
                                                 return                                     (n >> 1);                       
                         }                       
           
                         // Driver code                       
                         let n = 273;                       
                         document.write(setBitNumber(n));                       
           
                         // This code is contributed by suresh07                       
           
                         </script>                       

输出：

时间复杂度为O（1）。

另一种方法： 给定一个数字n。首先，找到最有效的集合位的位置，然后在第k位计算集合位的值。

感谢Rohit Narayan提出这种方法。

C++

                         // CPP program to find MSB                       
                         // number for given n.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     setBitNumber(                                     int                                     n)                       
                         {                       
           
                                                 // To find the position                       
                                                 // of the most significant                       
                                                 // set bit                       
                                                 int                                     k = (                                     int                                     )(log2(n));                       
           
                                                 // To return the the value                       
                                                 // of the number with set                       
                                                 // bit at k-th position                       
                                                 return                                     1 << k;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 273;                       
                                                 cout << setBitNumber(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find MSB                       
                         // number for given n.                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     setBitNumber(                                     int                                     n)                       
                                                 {                       
           
                                                 // To find the position of the                       
                                                 // most significant set bit                       
                                                 int                                     k = (                                     int                                     )(Math.log(n) / Math.log(                                     2                                     ));                       
           
                                                 // To return the the value of the number                       
                                                 // with set bit at k-th position                       
                                                 return                                     1                                     << k;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String arg[])                       
                                                 {                       
                                                 int                                     n =                                     273                                     ;                       
                                                 System.out.print(setBitNumber(n));                       
                                                 }                       
                         }                       

Python3

                         # Python program to find                       
                         # MSB number for given n.                       
                         import                                     math                       
           
                         def                                     setBitNumber(n):                       
                                   
                                                 # To find the position of                       
                                                 # the most significant                       
                                                 # set bit                       
                                                 k                                     =                                     int                                     (math.log(n,                                     2                                     ))                       
                                   
                                                 # To return the value                       
                                                 # of the number with set                       
                                                 # bit at k-th position                       
                                                 return                                     1                                     << k                       
           
                         # Driver code                       
                         n                                     =                                     273                       
                         print                                     (setBitNumber(n))                       

C#

                         // C# program to find MSB                       
                         // number for given n.                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
           
                                                 static                                     int                                     setBitNumber(                                     int                                     n)                       
                                                 {                       
           
                                                 // To find the position of the                       
                                                 // most significant set bit                       
                                                 int                                     k = (                                     int                                     )(Math.Log(n) / Math.Log(2));                       
           
                                                 // To return the the value of the number                       
                                                 // with set bit at k-th position                       
                                                 return                                     1 << k;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     public                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 273;                       
                                                 Console.WriteLine(setBitNumber(n));                       
                                                 }                       
                         }                       

PHP

                         <?php                       
                         // PHP program to find MSB                       
                         // number for given n.                       
           
                         function                                     setBitNumber(                                     $n                                     )                       
                         {                       
           
                                                 // To find the position                       
                                                 // of the most significant                       
                                                 // set bit                       
                                                 $k                                     =(int)(log(                                     $n                                     , 2));                       
           
                                                 // To return the the value                       
                                                 // of the number with set                       
                                                 // bit at k-th position                       
                                                 return                                     1 <<                                     $k                                     ;                       
                         }                       
           
                         // Driver code                       
                                                 $n                                     = 273;                       
                                                 echo                                     setBitNumber(                                     $n                                     );                       
           
                         // This code is contributed                       
                         // by jit_t.                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // Javascript program to find                       
                                                 // MSB number for given n.                       
                                   
                                                 function                                     setBitNumber(n)                       
                                                 {                       
                                   
                                                 // To find the position of the                       
                                                 // most significant set bit                       
                                                 let k = parseInt(Math.log(n) / Math.log(2), 10);                       
                                   
                                                 // To return the the value of the number                       
                                                 // with set bit at k-th position                       
                                                 return                                     1 << k;                       
                                                 }                       
                                   
                                                 let n = 273;                       
                                                 document.write(setBitNumber(n));                       
                                   
                         </script>                       

输出：

本文由 德万舒阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章