Count numbers up to N having Kth bit set | Function to return the count of number of 1 's at ith bit in a range [1, n - 1] ; Store count till nearest power of 2 less than N ; If K - th bit is set in N ; Add to result the nearest power of 2 less than N ; Return result ; Driver Code ; Function Call
def getcount ( n , k ) : NEW_LINE INDENT res = ( n >> ( k + 1 ) ) << k NEW_LINE if ( ( n >> k ) & 1 ) : NEW_LINE INDENT res += n & ( ( 1 << k ) - 1 ) NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 14 NEW_LINE K = 2 NEW_LINE print ( getcount ( N + 1 , K ) ) NEW_LINE DEDENT