Smallest number greater or equals to N such that it has no odd positioned bit set | Function to count the total bits ; Iterate and find the number of set bits ; Right shift the number by 1 ; Function to find the nearest number ; Count the total number of bits ; To get the position ; If the last set bit is at odd position then answer will always be a number with the left bit set ; Set all the even bits which are possible ; If the number still is less than N ; Return the number by setting the next even set bit ; If we have reached this position it means tempsum > n hence turn off even bits to get the first possible number ; Turn off the bit ; If it gets lower than N then set it and return that number ; Driver code
def countBits ( n ) : NEW_LINE INDENT count = 0 ; NEW_LINE while ( n > 0 ) : NEW_LINE INDENT count += 1 ; NEW_LINE n >>= 1 ; NEW_LINE DEDENT return count ; NEW_LINE DEDENT def findNearestNumber ( n ) : NEW_LINE INDENT cnt = countBits ( n ) ; NEW_LINE cnt -= 1 ; NEW_LINE if ( cnt % 2 ) : NEW_LINE INDENT return 1 << ( cnt + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT tempnum = 0 ; NEW_LINE for i in range ( 0 , cnt + 1 , 2 ) : NEW_LINE INDENT tempnum += 1 << i ; NEW_LINE DEDENT if ( tempnum < n ) : NEW_LINE INDENT return ( 1 << ( cnt + 2 ) ) ; NEW_LINE DEDENT elif ( tempnum == n ) : NEW_LINE INDENT return n ; NEW_LINE DEDENT for i in range ( 0 , cnt + 1 , 2 ) : NEW_LINE INDENT tempnum -= ( 1 << i ) ; NEW_LINE if ( tempnum < n ) : NEW_LINE INDENT tempnum += ( 1 << i ) ; NEW_LINE return tempnum ; NEW_LINE DEDENT DEDENT DEDENT DEDENT n = 19 ; NEW_LINE print ( findNearestNumber ( n ) ) ; NEW_LINE