Count numbers up to N whose rightmost set bit is K | Function to count the numbers in the range [ 1 , N ] whose rightmost set bit is K ; Stores the number whose rightmost set bit is K ; Numbers whose rightmost set bit is i ; Subtracting the number whose rightmost set bit is i , from N ; Since i = k , then the number whose rightmost set bit is K is stored ; Driver Code
def countNumberHavingKthBitSet ( N , K ) : NEW_LINE INDENT numbers_rightmost_setbit_K = 0 NEW_LINE for i in range ( 1 , K + 1 ) : NEW_LINE INDENT numbers_rightmost_bit_i = ( N + 1 ) // 2 NEW_LINE N -= numbers_rightmost_bit_i NEW_LINE if ( i == K ) : NEW_LINE INDENT numbers_rightmost_setbit_K = numbers_rightmost_bit_i NEW_LINE DEDENT DEDENT print ( numbers_rightmost_setbit_K ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 15 NEW_LINE K = 2 NEW_LINE countNumberHavingKthBitSet ( N , K ) NEW_LINE DEDENT