计算一个数字的未设置位-yiteyi-C++库

给定一个数字n，在MSB（最高有效位）之后计算未设置位。 例如：

null

Input : 17Output : 3Binary of 17 is 10001so unset bit is 3Input : 7Output : 0

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

A. 简单解决方案 就是遍历所有位并计算未设置的位。

C++

                         // C++ program to count unset bits in an integer                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     countunsetbits(                                     int                                     n)                       
                         {                       
                                                 int                                     count = 0;                       
                                   
                                                 // x holds one set digit at a time                       
                                                 // starting from LSB to MSB of n.                       
                                                 for                                     (                                     int                                     x = 1; x <= n; x = x<<1)                       
                                                 if                                     ((x & n) == 0)                       
                                                 count++;                       
           
                                                 return                                     count;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 17;                       
                                                 cout << countunsetbits(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // JAVA Code to Count unset bits in a number                       
                         class                                     GFG {                       
           
                                                 public                                     static                                     int                                     countunsetbits(                                     int                                     n)                       
                                                 {                       
                                                 int                                     count =                                     0                                     ;                       
                                   
                                                 // x holds one set digit at a time                       
                                                 // starting from LSB to MSB of n.                       
                                                 for                                     (                                     int                                     x =                                     1                                     ; x <= n; x = x<<                                     1                                     )                       
                                                 if                                     ((x & n) ==                                     0                                     )                       
                                                 count++;                       
                                   
                                                 return                                     count;                       
                                                 }                       
                                   
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     17                                     ;                       
                                                 System.out.println(countunsetbits(n));                       
                                                 }                       
                         }                       
                         // This code is contributed by Arnav Kr. Mandal.                       

Python3

                         # Python 3 program to count unset                       
                         # bits in an integer                       
           
                         def                                     countunsetbits(n):                       
                                                 count                                     =                                     0                       
                                   
                                                 # x holds one set digit at a time                       
                                                 # starting from LSB to MSB of n.                       
                                                 x                                     =                                     1                       
                                                 while                                     (x < n                                     +                                     1                                     ):                       
                                                 if                                     ((x & n)                                     =                                     =                                     0                                     ):                       
                                                 count                                     +                                     =                                     1                       
                                                 x                                     =                                     x <<                                     1                       
           
                                                 return                                     count                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 n                                     =                                     17                       
                                                 print                                     (countunsetbits(n))                       
                                   
                         # This code is contributed by                       
                         # Shashank_Sharma                       

C#

                         // C# Code to Count unset                       
                         // bits in a number                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Function to count unset bits                       
                                                 public                                     static                                     int                                     countunsetbits(                                     int                                     n)                       
                                                 {                       
                                                 int                                     count = 0;                       
                                   
                                                 // x holds one set digit at a time                       
                                                 // starting from LSB to MSB of n.                       
                                                 for                                     (                                     int                                     x = 1; x <= n; x = x << 1)                       
                                                 if                                     ((x & n) == 0)                       
                                                 count++;                       
                                   
                                                 return                                     count;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 17;                       
                                                 Console.Write(countunsetbits(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal.                       

PHP

                         <?php                       
                         // PHp program to count                       
                         // unset bits in an integer                       
                         function                                     countunsetbits(                                     $n                                     )                       
                         {                       
                                                 $count                                     = 0;                       
                                   
                                                 // x holds one set digit                       
                                                 // at a time starting                       
                                                 // from LSB to MSB of n.                       
                                                 for                                     (                                     $x                                     = 1;                                     $x                                     <=                                     $n                                     ;                       
                                                 $x                                     =                                     $x                                     << 1)                       
                                                 if                                     ((                                     $x                                     &                                     $n                                     ) == 0)                       
                                                 $count                                     ++;                       
           
                                                 return                                     $count                                     ;                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 17;                       
                         echo                                     countunsetbits(                                     $n                                     );                       
           
                         // This code is contributed                       
                         // by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to count unset bits in an integer                       
           
                         function                                     countunsetbits(n)                       
                         {                       
                                                 var                                     count = 0;                       
                                   
                                                 // x holds one set digit at a time                       
                                                 // starting from LSB to MSB of n.                       
                                                 for                                     (                                     var                                     x = 1; x <= n; x = x<<1)                       
                                                 if                                     ((x & n) == 0)                       
                                                 count++;                       
           
                                                 return                                     count;                       
                         }                       
           
                         // Driver code                       
                         var                                     n = 17;                       
                         document.write(countunsetbits(n));                       
           
                         </script>                       

输出：

上述解决方案的复杂性 日志（n） . 高效的解决方案： 这个想法是在O（1）时间内切换位。然后应用中讨论的任何方法计数设定位文章在GCC中，我们可以使用_builtin_popcount（）直接计算集合位。第一切换位然后应用上述函数_builtin_popcount（）。

C++

                         // An optimized C++ program to count unset bits                       
                         // in an integer.                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     countUnsetBits(                                     int                                     n)                       
                         {                       
                                                 int                                     x = n;                       
                                   
                                                 // Make all bits set MSB                       
                                                 // (including MSB)                       
                                   
                                                 // This makes sure two bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >> 1;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >> 2;                       
           
                                                 n |= n >> 4;                       
                                                 n |= n >> 8;                       
                                                 n |= n >> 16;                       
           
                                                 // Count set bits in toggled number                       
                                                 return                                     __builtin_popcount(x ^ n);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 17;                       
                                                 cout << countUnsetBits(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // An optimized Java program to count unset bits                       
                         // in an integer.                       
                         class                                     GFG                       
                         {                       
           
                         static                                     int                                     countUnsetBits(                                     int                                     n)                       
                         {                       
                                                 int                                     x = n;                       
           
                                                 // Make all bits set MSB                       
                                                 // (including MSB)                       
                                   
                                                 // This makes sure two bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >>                                     1                                     ;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >>                                     2                                     ;                       
           
                                                 n |= n >>                                     4                                     ;                       
                                                 n |= n >>                                     8                                     ;                       
                                                 n |= n >>                                     16                                     ;                       
           
                                                 // Count set bits in toggled number                       
                                                 return                                     Integer.bitCount(x^ n);                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     17                                     ;                       
                                                 System.out.println(countUnsetBits(n));                       
                         }                       
                         }                       
           
                         /* This code contributed by PrinciRaj1992 */                       

Python3

                         # An optimized Python program to count                       
                         # unset bits in an integer.                       
                         import                                     math                       
           
                         def                                     countUnsetBits(n):                       
                                                 x                                     =                                     n                       
           
                                                 # Make all bits set MSB(including MSB)                       
           
                                                 # This makes sure two bits(From MSB                       
                                                 # and including MSB) are set                       
                                                 n |                                     =                                     n >>                                     1                       
           
                                                 # This makes sure 4 bits(From MSB and                       
                                                 # including MSB) are set                       
                                                 n |                                     =                                     n >>                                     2                       
           
                                                 n |                                     =                                     n >>                                     4                       
                                                 n |                                     =                                     n >>                                     8                       
                                                 n |                                     =                                     n >>                                     16                       
           
                                                 t                                     =                                     math.log(x ^ n,                                     2                                     )                       
           
                                                 # Count set bits in toggled number                       
                                                 return                                     math.floor(t)                       
           
                         # Driver code                       
                         n                                     =                                     17                       
                         print                                     (countUnsetBits(n))                       
           
                         # This code is contributed 29AjayKumar                       

C#

                         // An optimized C# program to count unset bits                       
                         // in an integer.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         static                                     int                                     countUnsetBits(                                     int                                     n)                       
                         {                       
                                                 int                                     x = n;                       
           
                                                 // Make all bits set MSB                       
                                                 // (including MSB)                       
                                   
                                                 // This makes sure two bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >> 1;                       
           
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >> 2;                       
           
                                                 n |= n >> 4;                       
                                                 n |= n >> 8;                       
                                                 n |= n >> 16;                       
           
                                                 // Count set bits in toggled number                       
                                                 return                                     BitCount(x^ n);                       
                         }                       
           
                         static                                     int                                     BitCount(                                     long                                     x)                       
                         {                       
           
                                                 // To store the count                       
                                                 // of set bits                       
                                                 int                                     setBits = 0;                       
                                                 while                                     (x != 0) {                       
                                                 x = x & (x - 1);                       
                                                 setBits++;                       
                                                 }                       
           
                                                 return                                     setBits;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 int                                     n = 17;                       
                                                 Console.WriteLine(countUnsetBits(n));                       
                         }                       
                         }                       
           
                         // This code contributed by Rajput-Ji                       

PHP

                         <?php                       
                         // An optimized PHP program                       
                         // to count unset bits in                       
                         // an integer.                       
           
                         function                                     countUnsetBits(                                     $n                                     )                       
                         {                       
                                                 $x                                     =                                     $n                                     ;                       
           
                                                 // Make all bits set                       
                                                 // MSB(including MSB)                       
           
                                                 // This makes sure two                       
                                                 // bits(From MSB and                       
                                                 // including MSB) are set                       
                                                 $n                                     |=                                     $n                                     >> 1;                       
           
                                                 // This makes sure 4                       
                                                 // bits(From MSB and                       
                                                 // including MSB) are set                       
                                                 $n                                     |=                                     $n                                     >> 2;                       
           
                                                 $n                                     |=                                     $n                                     >> 4;                       
                                                 $n                                     |=                                     $n                                     >> 8;                       
                                                 $n                                     |=                                     $n                                     >> 16;                       
           
                                                 $t                                     = log(                                     $x                                     ^                                     $n                                     ,2);                       
                                   
                                                 // Count set bits                       
                                                 // in toggled number                       
                                                 return                                     floor                                     (                                     $t                                     );                       
                         }                       
           
                         // Driver code                       
                         $n                                     = 17;                       
                         echo                                     countUnsetBits(                                     $n                                     );                       
           
                         // This code is contributed                       
                         // by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to count unset bits                       
                         // in an integer.                       
           
                         function                                     countUnsetBits(n)                       
                         {                       
                                                 let x = n;                       
                                   
                                                 // Make all bits set MSB                       
                                                 // (including MSB)                       
                                   
                                                 // This makes sure two bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >> 1;                       
                                   
                                                 // This makes sure 4 bits                       
                                                 // (From MSB and including MSB)                       
                                                 // are set                       
                                                 n |= n >> 2;                       
                                   
                                                 n |= n >> 4;                       
                                                 n |= n >> 8;                       
                                                 n |= n >> 16;                       
                                   
                                                 // Count set bits in toggled number                       
                                                 return                                     BitCount(x^ n);                       
                         }                       
           
                         function                                     BitCount(x)                       
                         {                       
                                   
                                                 // To store the count                       
                                                 // of set bits                       
                                                 let setBits = 0;                       
                                                 while                                     (x != 0) {                       
                                                 x = x & (x - 1);                       
                                                 setBits++;                       
                                                 }                       
                                   
                                                 return                                     setBits;                       
                         }                       
           
                         // Driver Code                       
           
                                                 let n = 17;                       
                                                 document.write(countUnsetBits(n));                       
           
                         // This code is contributed by susmitakundugoaldanga.                       
                         </script>                       

输出：

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

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

THE END

技术文章