Sum of powers of 2

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).

Solution :

1. 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

Complexities :

• Time : O(1)
• Space : O(1)

Code :

bool check_form(int N){

if(N < 2)

return false;

N = N & (N-1);

if(!N)

return true;

return (N & (N-1));

}