Algorithms Forever ...: 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 :
- 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)); }
Read full article from Algorithms Forever ...: Sum of powers of 2
