Count total set bits in all numbers from range L to R | Returns position of leftmost set bit The rightmost position is taken as 0 ; Function that gives the position of previous leftmost set bit in n ; Function that returns count of set bits present in all numbers from 1 to n ; Get the position of leftmost set bit in n ; Use the position ; Function to count the set bits between the two numbers N and M ; Base Case ; Get position of next leftmost set bit ; If n is of the form 2 ^ x - 1 ; Update n for next recursive call ; Function that counts the set bits between L and R ; Driver Code ; Given L and R ; Function Call
def getLeftmostBit ( n ) : NEW_LINE INDENT m = 0 ; NEW_LINE while ( n > 1 ) : NEW_LINE INDENT n = n >> 1 ; NEW_LINE m += 1 ; NEW_LINE DEDENT return m ; NEW_LINE DEDENT def getNextLeftmostBit ( n , m ) : NEW_LINE INDENT temp = 1 << m ; NEW_LINE while ( n < temp ) : NEW_LINE INDENT temp = temp >> 1 ; NEW_LINE m -= 1 ; NEW_LINE DEDENT return m ; NEW_LINE DEDENT def countSetBit ( n ) : NEW_LINE INDENT m = getLeftmostBit ( n ) ; NEW_LINE return _countSetBit ( n , m ) ; NEW_LINE DEDENT def _countSetBit ( n , m ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT m = getNextLeftmostBit ( n , m ) ; NEW_LINE if ( n == int ( 1 << ( m + 1 ) ) - 1 ) : NEW_LINE INDENT return int ( m + 1 ) * ( 1 << m ) ; NEW_LINE DEDENT n = n - ( 1 << m ) ; NEW_LINE return ( ( n + 1 ) + countSetBit ( n ) + m * ( 1 << ( m - 1 ) ) ) ; NEW_LINE DEDENT def countSetBits ( L , R ) : NEW_LINE INDENT return abs ( countSetBit ( R ) - countSetBit ( L - 1 ) ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT L = 3 ; NEW_LINE R = 5 ; NEW_LINE print ( " Total ▁ set ▁ bit ▁ count ▁ is ▁ " , countSetBits ( L , R ) ) ; NEW_LINE DEDENT