Count of numbers having only one unset bit in a range [ L , R ] | C ++ program for the above approach ; Function to count numbers in the range [ L , R ] having exactly one unset bit ; Stores the count elements having one zero in binary ; Stores the maximum number of bits needed to represent number ; Loop over for zero bit position ; Number having zero_bit as unset and remaining bits set ; Sets all bits before zero_bit ; Set the bit at position j ; Set the bit position at j ; If cur is in the range [ L , R ] , then increment ans ; Return ans ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int count_numbers ( int L , int R ) { int ans = 0 ; int LogR = log2 ( R ) + 1 ; for ( int zero_bit = 0 ; zero_bit < LogR ; zero_bit ++ ) { int cur = 0 ; for ( int j = 0 ; j < zero_bit ; j ++ ) { cur |= ( 1LL << j ) ; } for ( int j = zero_bit + 1 ; j < LogR ; j ++ ) { cur |= ( 1LL << j ) ; if ( cur >= L && cur <= R ) { ans ++ ; } } } return ans ; } int main ( ) { long long L = 4 , R = 9 ; cout << count_numbers ( L , R ) ; return 0 ; }