Count set bits in a range
Given a non-negative number n and two values l and r. The problem is to count the number of set bits in the range l to r in the binary representation of n, i.e, to count set bits from the rightmost lth bit to the rightmost rth bit.
Constraint: 1 <= l <= r <= number of bits in the binary representation of n.
Examples:
Input : n = 42, l = 2, r = 5 Output : 2 (42)10 = (101010)2 There are '2' set bits in the range 2 to 5. Input : n = 79, l = 1, r = 4 Output : 4
Approach: Following are the steps:
- Calculate num = ((1 << r) – 1) ^ ((1 << (l-1)) – 1). This will produce a number num having r number of bits and bits in the range l to r are the only set bits.
- Count number of set bits in the number (n & num). Refer this post.
C++
// C++ implementation to count set 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 set bits in the given range unsigned int countSetBitsInGivenRange(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 set bits in the range // 'l' to 'r' in 'n' return countSetBits(n & num); } // Driver program to test above int main() { unsigned int n = 42; unsigned int l = 2, r = 5; cout << countSetBitsInGivenRange(n, l, r); return 0; } |
Java
// Java implementation to count set 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 set bits in the given range static int countSetBitsInGivenRange( 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 set bits in the range // 'l' to 'r' in 'n' return countSetBits(n & num); } // Driver code public static void main(String[] args) { int n = 42 ; int l = 2 , r = 5 ; System.out.print(countSetBitsInGivenRange(n, l, r)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 implementation to count # set 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 = count + 1 return count # function to count set bits in # the given range def countSetBitsInGivenRange(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 set bits in the range # 'l' to 'r' in 'n' return countSetBits(n & num) # Driver program to test above n = 42 l = 2 r = 5 ans = countSetBitsInGivenRange(n, l, r) print (ans) # This code is contributed by Saloni Gupta. |
C#
// C# implementation to count set 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 set bits in the given range static int countSetBitsInGivenRange( 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 set bits in the range // 'l' to 'r' in 'n' return countSetBits(n & num); } //Driver code public static void Main() { int n = 42; int l = 2, r = 5; Console.WriteLine(countSetBitsInGivenRange(n, l, r)); } } // This code is contributed by Anant Agarwal. |
PHP
<?php // PHP implementation to count // set 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 set // bits in the given range function countSetBitsInGivenRange( $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 // set bits in the range // 'l' to 'r' in 'n' return countSetBits( $n & $num ); } // Driver Code $n = 42; $l = 2; $r = 5; echo countSetBitsInGivenRange( $n , $l , $r ); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript implementation to // count set bits in the // given range // Function to get no of set bits in the // binary representation of 'n' function countSetBits(n) { let count = 0; while (n > 0) { n &= (n - 1); count++; } return count; } // function to count set // bits in the given range function countSetBitsInGivenRange(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 let num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1); // returns number of set // bits in the range // 'l' to 'r' in 'n' return countSetBits(n & num); } // driver program let n = 42; let l = 2, r = 5; document.write(countSetBitsInGivenRange(n, l, r)); </script> |
Output:
2
Time Complexity: O(logn)
Auxiliary Space: O(1)
Contact Us