Check if a number can be expressed as 2 ^ x + 2 ^ y | Utility function to check if a number is power of 2 or not ; Utility function to determine the value of previous power of 2 ; function to check if n can be expressed as 2 ^ x + 2 ^ y or not ; if value of n is 0 or 1 it can not be expressed as 2 ^ x + 2 ^ y ; if n is power of two then it can be expressed as sum of 2 ^ x + 2 ^ y ; if the remainder after subtracting previous power of 2 is also a power of 2 then it can be expressed as 2 ^ x + 2 ^ y ; driver code
def isPowerOfTwo ( n ) : NEW_LINE INDENT return ( n and ( not ( n & ( n - 1 ) ) ) ) NEW_LINE DEDENT def previousPowerOfTwo ( n ) : NEW_LINE INDENT while ( n & n - 1 ) : NEW_LINE INDENT n = n & n - 1 NEW_LINE DEDENT return n NEW_LINE DEDENT def checkSum ( n ) : NEW_LINE INDENT if ( n == 0 or n == 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT elif ( isPowerOfTwo ( n ) ) : NEW_LINE INDENT print ( n // 2 , n // 2 ) NEW_LINE return True NEW_LINE DEDENT else : NEW_LINE INDENT x = previousPowerOfTwo ( n ) NEW_LINE y = n - x ; NEW_LINE if ( isPowerOfTwo ( y ) ) : NEW_LINE INDENT print ( x , y ) NEW_LINE return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT DEDENT n1 = 20 NEW_LINE if ( checkSum ( n1 ) ) : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT n2 = 11 NEW_LINE if ( checkSum ( n2 ) ) : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT