Smallest number exceeding N whose Kth bit is set | Function to find the number greater than n whose Kth bit is set ; Stores the resultant number ; If Kth bit is not set ; cur will be the sum of all powers of 2 < k ; If the current bit is set ; Add Kth power of 2 to n and subtract the all powers of 2 less than K that are set ; If the kth bit is set ; First unset bit position ; Sum of bits that are set ; Add Kth power of 2 to n and subtract the all powers of 2 less than K that are set ; If Kth bit became unset then set it again ; Return the resultant number ; Driver code ; Print ans
def find_next ( n , k ) : NEW_LINE INDENT ans = 0 NEW_LINE if ( ( n & ( 1 << k ) ) == 0 ) : NEW_LINE INDENT cur = 0 NEW_LINE for i in range ( k ) : NEW_LINE INDENT if ( n & ( 1 << i ) ) : NEW_LINE INDENT cur += 1 << i NEW_LINE DEDENT DEDENT ans = n - cur + ( 1 << k ) NEW_LINE DEDENT else : NEW_LINE INDENT first_unset_bit , cur = - 1 , 0 NEW_LINE for i in range ( 64 ) : NEW_LINE INDENT if ( ( n & ( 1 << i ) ) == 0 ) : NEW_LINE INDENT first_unset_bit = i NEW_LINE break NEW_LINE DEDENT else : NEW_LINE INDENT cur += ( 1 << i ) NEW_LINE DEDENT DEDENT ans = n - cur + ( 1 << first_unset_bit ) NEW_LINE if ( ( ans & ( 1 << k ) ) == 0 ) : NEW_LINE INDENT ans += ( 1 << k ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT N , K = 15 , 2 NEW_LINE print ( find_next ( N , K ) ) NEW_LINE