Blog # 47 : 2^x + 2^y

Devise an algorithm to find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive). Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj, Gurpreet & Ankit Remarks: Use concepts of bit manipulation. Check for right-most bit. Hints: The rightmost bit may be set to zero by (N & N-1), so we do it twice and if the number becomes zero, it means it had 2 bits as 1 before thus having the required form 2^x + 2^y. Also consider the case where x = y separately. Solution: The rightmost bit may be set to zero by (N & N-1), so we do it twice and if the number becomes zero, it means it had 2 bits as 1 before thus having the required form 2^x + 2^y. When x = y: The number of bits set to 1 in binary representation of N is one. Applying N=(N & N-1), once will make N=0. Now, one cannot apply N= (N & N-1) again, as this will change the value of N ( ! = 0 ). Hence, one must check if after using the formula N=(N & N-1) ,N has become 0 or not. Another test case is when N=1 , 0 . In that case N&(N-1) = 0 and it doesnt mean x=y. So in our algorithm the first step must be modified as : if(N>1), use the formula N=(N& (N-1) ) and check if N=0. Hence, We consider the case when x=y, so only one bit is set. Also we check if number is not 0 or 1 initially for which answer is false. bool check_form(int N){ if(N < 2) return false; N = N & (N-1); if(!N) return true; return !(N & (N-1)); }