Count total set bits in all numbers from 1 to n | A O ( Logn ) complexity program to count set bits in all numbers from 1 to n ; Returns position of leftmost set bit . The rightmost position is considered as 0 ; Given the position of previous leftmost set bit in n ( or an upper bound onleftmost position ) returns the new position of leftmost set bit in n ; The main recursive function used by countSetBits ( ) ; Get the position of leftmost set bit in n . This will be used as an upper bound for next set bit function ; Use the position ; Base Case : if n is 0 , then set bit count is 0 ; get position of next leftmost set bit ; If n is of the form 2 ^ x - 1 , i . e . , if n is like 1 , 3 , 7 , 15 , 31 , . . etc , then we are done . Since positions are considered starting from 0 , 1 is added to m ; update n for next recursive call ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; unsigned int getLeftmostBit ( int n ) { int m = 0 ; while ( n > 1 ) { n = n >> 1 ; m ++ ; } return m ; } unsigned int getNextLeftmostBit ( int n , int m ) { unsigned int temp = 1 << m ; while ( n < temp ) { temp = temp >> 1 ; m -- ; } return m ; } unsigned int _countSetBits ( unsigned int n , int m ) ; unsigned int countSetBits ( unsigned int n ) { int m = getLeftmostBit ( n ) ; return _countSetBits ( n , m ) ; } unsigned int _countSetBits ( unsigned int n , int m ) { if ( n == 0 ) return 0 ; m = getNextLeftmostBit ( n , m ) ; if ( n == ( ( unsigned int ) 1 << ( m + 1 ) ) - 1 ) return ( unsigned int ) ( m + 1 ) * ( 1 << m ) ; n = n - ( 1 << m ) ; return ( n + 1 ) + countSetBits ( n ) + m * ( 1 << ( m - 1 ) ) ; } int main ( ) { int n = 17 ; cout << " Total ▁ set ▁ bit ▁ count ▁ is ▁ " << countSetBits ( n ) ; return 0 ; }