Checking if a no is power of 2

general
, ,
1

Hi community,

Came across a simple piece of code to check if a given no is a power of 2. Thought of sharing it here , many may be aware of this though.

Method- 1

Suppose we have a no n and we want to check if its a power of 2.

  if(!(n&n-1==0)) printf("power of zero!!!");
Explanation:
 suppose n=8 (1000 in binary) then n-1=7 (0111);
 

                   1000 
                 & 0111
                 =    0
if n=6
                    110
                  & 101
                  = 100

Method 2:

Assuming n>0

if ((n & -n) == n) {
// n is a power of two

}

Edit- Have added Method 2 to check for it.

Edit 2- Some of the other methods for checking this can be found here. pow of 2
Edit 3- For detailed implementation check this link link text

Hope this helps. Happy coding …

3 Likes
2

@smsubham XOR of 1000 and 0111 is 1111.
Although it can be changed to !(N&(N-1))==0 to check power of two.

1 Like
3

By mistake mentioned xor. Thanks for pointing out. @srd091

4

Simply take binary of the given number and check for number of occurrences of ‘1’ in that binary string.if that count equals to 1 then it’s a power of 2 otherwise not.you can check occurrences easily just by calling a simple function in java.

e.g.

1 = 0001 i.e 2^0
512=100000000 i.e 2^9

3=0011 2 1’s

14=1110 3 1’s.

5

Hi

The solution i have provided is simpler i guess…
Also we could modify your solution to check till no of 1’s is < 2 then stop. If it stops before reaching end of string then its isn’t a power of 2 else it is. This decreases time complexity for the code.

N.B. - Above isn’t a question but a solution to find if a no power of 2.

6

Another method can be this
C++ code

int remainder,num,flag=1;
while(num!=0)
{ remainder = num % 2;
num = num / 2;
if(remainder!=0)
{ flag=-1;
break;
}
}

7

Use _builtinpopcount(n)==1

1 Like
8

As suggested by @abhi1shek1, we can use built-in function in c/c++ which checks for numbers of ON(1) bits in a binary representation of a number.

int check_if_pow_of_2 (int n){
     return __builtin_popcount(n)==1; 
}

It is much faster and simpler :slight_smile:

1 Like
9

You can take log(to base 10) and take mod 0.301 (log 2). If the mod is zero then the no. is a power of 2 which is log(no.)/0.301.
n = log10(n) ;
if (n % 0.301 == 0) then
power of 2 ;

10

bit wise operations are faster than function calling , so solution provided in this question should work faster