Explain ((n & (n-1)) == 0)

variant of question:-

 find whether a no is power of two ?

It's figuring out if n is either 0 or an exact power of two.

how ?

It works because of binary Bits Magic.
but before explaining first i want to define them  
n ->  unsigned long 
(n-1) -> it is simple Subtraction 
& -> The bitwise AND operator (&) compares each bit of the first operand to the corresponding bit of the second operand. If both bits are 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0.

Bitwise AND Truth Table :

now, why it work ?

because all number n which is power of 2 follow some pattern

look at this:

2  = 10
4  = 100
8  = 1000
16= 10000
32= 100000
64= 1000000

and all number (n-1) also follow some pattern

1=   01
3  = 011
7  = 0111
15= 01111
32= 011111
64= 0111111

all number n which is power of 2 has msb( leftmost bit ) 1 followed by all 0's              and all (n-1) number  has msb( leftmost bit ) 0 followed by all 1's

when we perform logical & operation between n and (n-1) answer will always 0.

example:

For n=2

  n           2 =  1 0
n-1     &  1 =  0 1
           ------------------
                      0 0
           ------------------

For n=4

  n           4 =  1 0 0
n-1     &  3 =  0 1 1
           ------------------
                      0 0 0
           ------------------

For n=8

  n           8 =  1 0 0 0
n-1     &  7 =  0 1 1 1
           ------------------
                      0 0 0 0
           ------------------

And so on...

But what about 0 ?

let n=0
n-1= (0-1)= (-1)
binary representation of 0=0000
and (-1) represent in 2's complement form 
Therefore binary representation of (-1)=1111

For n=0
  n               0 =  0 0 0 0
n-1      &  (-1) =  1 1 1 1
          -----------------------
                          0 0 0 0
          -----------------------

What if i only want to find whether number is power of two or not ?

(n != 0) && ((n & (n - 1)) == 0);

code:

#include <stdio.h> 
int main()
{
 int n,x;
 printf("enter value of n:");
 scanf("%d",&n);
 x= n & (n-1);
    if( x==0)
     printf("n is either 0 or an exact power of two.");
    else
     printf("n is neither 0 nor an exact power of two.");
  return 0;
}

output:-

enter value of n:16
n is either 0 or an exact power of two.

To find whether number is power of two or not?

code:

#include <stdio.h> 
int main()
{
 int n,x;
 printf("enter value of n:");
 scanf("%d",&n);
 x= n & (n-1);
    if( x==0)
     printf("number is power of 2");
    else
     printf("number is not power of 2");
  return 0;
}

output:-

enter value of n:16
number is power of 2

SHARE