Difference of powers of 2

Devise an algorithm to find whether a given positive number N is of the form 2^x - 2^y (^ means exponentiation, x and y are positive and x>y>0).

Solution :

1. We first take OR of N and N-1 to make all right bits 1
2. Then add 1 and use N & N-1 trick to see if result is zero to conclude that N was of the correct form.

Complexities :

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

Code :

bool check_form(int N){

if(N < 2) return false;

N = N | N-1;      // better written as N |= N-1;

N++;
return N & N-1;

}