How does this bitwise operation check for a power

Question

I'm looking at some code which should be trivial -- but my math is failing me miserably here.

Here's a condition that checks if a number if a power of 2 using the following:

if((num != 1) && (num & (num - 1))) { /* make num pow of 2 */ }

My question is, how does using a bitwise AND between num and num - 1 determine if a number is a power of 2?

Answer 1

It determines whether integer is power of 2 or not. If (x & (x-1)) is zero then the number is power of 2.

For example, let x be 8 (1000 in binary); then x-1 = 7 (0111).

if    1000
  &   0111
---------------
      0000

C program to demonstrate:

#include <stdio.h>

void main()
{
    int a = 8;
    if ((a&(a-1))==0)
    {
        printf("the bit is power of 2  \n");
    }
    else 
    {
        printf("the bit is not power of 2\n");
    }
}

This outputs the bit is power of 2.

#include <stdio.h>

void main()
{
    int a = 7;
    if ((a&(a-1))==0)
    {
        printf("the bit is power of 2  \n");
    }
    else 
    {
        printf("the bit is not power of 2\n");
    }
}

This outputs the bit is not power of 2.

Answer 2

Well, the first case will check for 2⁰ == 1.

For the other cases the num & (num - 1) comes into play:

That's saying if you take any number, and mask off the bits from one lower, you'll get one of two cases:

1. if the number is a power of two already, then one less will result in a binary number that only has the lower-order bits set. Using & there will do nothing.

   • Example with 8: 0100 & (0100 - 1) --> (0100 & 0011) --> 0000

2. if the number is not a power of two already, then one less will not touch the highest bit, so the result will be at least the largest power of two less than num.

   • Example with 3: 0011 & (0011 - 1) --> (0011 & 0010) --> 0010

   • Example with 13: 1101 & (1101 - 1) --> (1101 & 1100) --> 1100

So the actual expression finds everything that isn't a power of two, including 2⁰.

Answer 3

Following program in C will find out if the number is power of 2 and also find which power of 2, the number is.

#include<stdio.h>
void main(void)
{
    unsigned int a;
    unsigned int count=0
    unsigned int check=1;
    unsigned int position=0;
    unsigned int temp;
    //get value of a
    for(i=0;i<sizeof(int)*8;i++)//no of bits depend on size of integer on that machine
    {
        temp = a&(check << i);
        if(temp)
        {
            position = i;
            count++;
        }
    }
    if(count == 1)
    {
        printf("%d is 2 to the power of %d",a,position);
    }
    else
    {
        printf("Not a power of 2");
    }
}

There are other ways to do this:- if a number is a power of 2, only 1 bit will be set in the binary format

for example 8 is equivalent to 0x1000, substracting 1 from this, we get 0x0111.

End operation with the original number(0x1000) gives 0.

if that is the case, the number is a power of 2

    void IsPowerof2(int i)
    {
    if(!((i-1)&1))
    {
    printf("%d" is a power of 2, i);
    }
    }

another way can be like this:-

If we take complement of a number which is a power of 2,

for example complement of 8 i.e 0x1000 , we get 0x0111 and add 1 to it, we get

the same number, if that is the case, that number is a power of 2

    void IsPowerof2(int i)
    {
    if(((~1+1)&i) == 1)
    {
    printf("%d" is a power of 2,i):
    }
    }                                                     

Answer 4

Well,

if you have X = 1000 then x-1 = 0111. And 1000 && 0111 is 0000.

Each number X that is a power of 2 has an x-1 that has ones on the position x has zeroes. And a bitwise and of 0 and 1 is always 0.

If the number x is not a power of two, for example 0110. The x-1 is 0101 and the and gives 0100.

For all combinbations within 0000 - 1111 this leads to

   X  X-1 X && X-1  
0000 1111 0000   
0001 0000 0000 
0010 0001 0000
0011 0010 0010
0100 0011 0000
0101 0100 0100
0110 0101 0100
0111 0110 0110
1000 0111 0000
1001 1000 1000
1010 1001 1000
1011 1010 1010
1100 1011 1000
1101 1100 1100
1110 1101 1100
1111 1110 1110

And there is no need for a separate check for 1.

Answer 5

Explained here nicely

Also the expression given considers 0 to be a power of 2. To fix that use !(x & (x - 1)) && x; instead.

Answer 6

Any power of 2 minus 1 is all ones: (2 ^N - 1 = 111....b)

2 = 2^1.  2-1 = 1 (1b)
4 = 2^2.  4-1 = 3 (11b)
8 = 2^3.  8-1 = 7 (111b)

Take 8 for example. 1000 & 0111 = 0000

So that expression tests if a number is NOT a power of 2.