在一个范围内计数未设置的位-yiteyi-C++库

给定一个非负数 N 还有两个价值观 L 和 R .问题是计算范围内未设置的位数 L 到 R 在二进制表示中 N ，即从最右边开始计算未设置的位 lth 最右边一点 rth 一点例如：

null

Input : n = 42, l = 2, r = 5Output : 2(42)₁₀ = (101010)₂There are '2' unset bits in the range 2 to 5.Input : n = 80, l = 1, r = 4Output : 4

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法： 以下是步骤：

计算号码 =（（1< 号码有 R 位数和范围内的位数 L 到 R 是唯一的设定位。
计算数字中的设置位数 （n&num） 参考这邮递顺其自然计数 .
计算 ans =（r–l+1）–计数。
回来 ans .

C++

                         // C++ implementation to count unset bits in the                       
                         // given range                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to get no of set bits in the                       
                         // binary representation of 'n'                       
                         unsigned                                     int                                     countSetBits(                                     int                                     n)                       
                         {                       
                                                 unsigned                                     int                                     count = 0;                       
                                                 while                                     (n) {                       
                                                 n &= (n - 1);                       
                                                 count++;                       
                                                 }                       
                                                 return                                     count;                       
                         }                       
           
                         // function to count unset bits                       
                         // in the given range                       
                         unsigned                                     int                                     countUnsetBitsInGivenRange(unsigned                                     int                                     n,                       
                                                 unsigned                                     int                                     l, unsigned                                     int                                     r)                       
                         {                       
                                                 // calculating a number 'num' having 'r' number                       
                                                 // of bits and bits in the range l to r are the                       
                                                 // only set bits                       
                                                 int                                     num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1);                       
           
                                                 // returns number of unset bits in the range                       
                                                 // 'l' to 'r' in 'n'                       
                                                 return                                     (r - l + 1) - countSetBits(n & num);                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 unsigned                                     int                                     n = 80;                       
                                                 unsigned                                     int                                     l = 1, r = 4;                       
                                                 cout << countUnsetBitsInGivenRange(n, l, r);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to count unset bits in the                       
                         // given range                       
                         class                                     GFG {                       
                                   
                                                 // Function to get no of set bits in the                       
                                                 // binary representation of 'n'                       
                                                 static                                     int                                     countSetBits(                                     int                                     n)                       
                                                 {                       
                                                 int                                     count =                                     0                                     ;                       
                                   
                                                 while                                     (n >                                     0                                     ) {                       
                                                 n &= (n -                                     1                                     );                       
                                                 count++;                       
                                                 }                       
                                   
                                                 return                                     count;                       
                                                 }                       
           
                                                 // function to count unset bits                       
                                                 // in the given range                       
                                                 static                                     int                                     countUnsetBitsInGivenRange(                                     int                                     n,                       
                                                 int                                     l,                                     int                                     r)                       
                                                 {                       
                                   
                                                 // calculating a number 'num' having 'r'                       
                                                 // number of bits and bits in the range                       
                                                 // l to r are the only set bits                       
                                                 int                                     num = ((                                     1                                     << r) -                                     1                                     ) ^ ((                                     1                                     <<                       
                                                 (l -                                     1                                     )) -                                     1                                     );                       
           
                                                 // returns number of unset bits in the range                       
                                                 // 'l' to 'r' in 'n'                       
                                                 return                                     (r - l +                                     1                                     ) - countSetBits(n & num);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     80                                     ;                       
                                                 int                                     l =                                     1                                     , r =                                     4                                     ;                       
                                   
                                                 System.out.print(                       
                                                 countUnsetBitsInGivenRange(n, l, r));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python3 implementation to count                       
                         # unset bits in the given range                       
           
                         # Function to get no of set bits in                       
                         # the binary representation of 'n'                       
                         def                                     countSetBits (n):                       
                                                 count                                     =                                     0                       
                                                 while                                     n:                       
                                                 n &                                     =                                     (n                                     -                                     1                                     )                       
                                                 count                                     +                                     =                                     1                       
                                                 return                                     count                       
           
                         # function to count unset bits                       
                         # in the given range                       
                         def                                     countUnsetBitsInGivenRange (n, l, r):                       
                                   
                                                 # calculating a number 'num' having                       
                                                 # 'r' number of bits and bits in the                       
                                                 # range l to r are the only set bits                       
                                                 num                                     =                                     ((                                     1                                     << r)                                     -                                     1                                     ) ^ ((                                     1                                     << (l                                     -                                     1                                     ))                                     -                                     1                                     )                       
                                   
                                                 # returns number of unset bits                       
                                                 # in the range 'l' to 'r' in 'n'                       
                                                 return                                     (r                                     -                                     l                                     +                                     1                                     )                                     -                                     countSetBits(n & num)                       
           
                         # Driver code to test above                       
                         n                                     =                                     80                       
                         l                                     =                                     1                       
                         r                                     =                                     4                       
                         print                                     (countUnsetBitsInGivenRange(n, l, r))                       
           
                         # This code is contributed by "Sharad_Bhardwaj"                       

C#

                         // C# implementation to count unset bits in the                       
                         // given range                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Function to get no of set bits in the                       
                                                 // binary representation of 'n'                       
                                                 static                                     int                                     countSetBits(                                     int                                     n)                       
                                                 {                       
                                                 int                                     count = 0;                       
                                   
                                                 while                                     (n > 0) {                       
                                                 n &= (n - 1);                       
                                                 count++;                       
                                                 }                       
                                   
                                                 return                                     count;                       
                                                 }                       
                                   
                                                 // function to count unset bits                       
                                                 // in the given range                       
                                                 static                                     int                                     countUnsetBitsInGivenRange(                                     int                                     n,                       
                                                 int                                     l,                                     int                                     r)                       
                                                 {                       
                                   
                                                 // calculating a number 'num' having 'r'                       
                                                 // number of bits and bits in the range l                       
                                                 // to r are the only set bits                       
                                                 int                                     num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1);                       
                                   
                                                 // returns number of unset bits in the range                       
                                                 // 'l' to 'r' in 'n'                       
                                                 return                                     (r - l + 1) - countSetBits(n & num);                       
                                                 }                       
                                   
                                                 //Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 80;                       
                                                 int                                     l = 1, r = 4;                       
                                   
                                                 Console.Write(countUnsetBitsInGivenRange(n, l, r));                       
                                                 }                       
                         }                       
           
                         //This code is contributed by Anant Agarwal.                       

PHP

                         <?php                       
                         // php implementation to count                       
                         // unset bits in the given range                       
           
                         // Function to get no of set bits in                       
                         // the binary representation of 'n'                       
                         function                                     countSetBits(                                     $n                                     )                       
                         {                       
                                                 $count                                     = 0;                       
                                                 while                                     (                                     $n                                     )                       
                                                 {                       
                                                 $n                                     &= (                                     $n                                     - 1);                       
                                                 $count                                     ++;                       
                                                 }                       
                                                 return                                     $count                                     ;                       
                         }                       
           
                         // function to count unset                       
                         // bits in the given range                       
                         function                                     countUnsetBitsInGivenRange(                                     $n                                     ,                                     $l                                     ,                                     $r                                     )                       
                         {                       
                                   
                                                 // calculating a number 'num'                       
                                                 // having 'r' number                       
                                                 // of bits and bits in the                       
                                                 // range l to r are the                       
                                                 // only set bits                       
                                                 $num                                     = ((1 <<                                     $r                                     ) - 1) ^                       
                                                 ((1 << (                                     $l                                     - 1)) - 1);                       
           
                                                 // returns number of unset                       
                                                 // bits in the range                       
                                                 // 'l' to 'r' in 'n'                       
                                                 return                                     (                                     $r                                     -                                     $l                                     + 1) -                       
                                                 countSetBits(                                     $n                                     &                                     $num                                     );                       
                         }                       
           
                                                 // Driver code                       
                                                 $n                                     = 80;                       
                                                 $l                                     = 1;                       
                                                 $r                                     = 4;                       
                                                 echo                                     countUnsetBitsInGivenRange(                                     $n                                     ,                                     $l                                     ,                                     $r                                     );                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript implementation to count unset bits in the                       
                         // given range                       
           
                         // Function to get no of set bits in the                       
                         // binary representation of 'n'                       
                         function                                     countSetBits(n)                       
                         {                       
                                                 var                                     count = 0;                       
                                                 while                                     (n) {                       
                                                 n &= (n - 1);                       
                                                 count++;                       
                                                 }                       
                                                 return                                     count;                       
                         }                       
           
                         // function to count unset bits                       
                         // in the given range                       
                         function                                     countUnsetBitsInGivenRange(n, l, r)                       
                         {                       
                                                 // calculating a number 'num' having 'r' number                       
                                                 // of bits and bits in the range l to r are the                       
                                                 // only set bits                       
                                                 var                                     num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1);                       
           
                                                 // returns number of unset bits in the range                       
                                                 // 'l' to 'r' in 'n'                       
                                                 return                                     (r - l + 1) - countSetBits(n & num);                       
                         }                       
           
                         // Driver program to test above                       
                         var                                     n = 80;                       
                         var                                     l = 1, r = 4;                       
                         document.write( countUnsetBitsInGivenRange(n, l, r));                       
           
                         </script>                       

输出：

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

THE END

技术文章