How does this bitwise operation check for a power of 2?

Question

Here's a condition that checks if a number is 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

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.

Answer 2

Subtracting 1 from a positive "power of 2" number will always unset the top bit (which is the ONLY non-zero bit in "power of 2" numbers) and will set all lower bits to "1". Therefore, the AND operation always returns 0 for "power of 2" numbers. That explains how the "power of 2" is detected by looking for 0.

Now onto the non-"power of 2" numbers: Subtracting 1 from a number which ISN'T a "power of 2" will ALWAYS keep the top bit (representing the highest "power of 2" that the original number had exceeded), meaning that the AND operation on non-"power of 2" numbers is ALWAYS non-zero.

Another way of expressing it: The ONLY way to unset the top bit of a binary number is by subtracting 1 from a pure "power of 2" number. In ALL other cases, the top bit will remain set after subtracting 1.

If it's still not clear, here's yet another way of expressing it: When "subtracting 1" from a binary number, the ONLY way to unset the top bit of the resulting binary number is when the input was a PURE "power of 2" number (all "powers of 2" ONLY have EXACTLY 1 bit set). In ALL other cases, the top bit (aka "the highest power of 2 that the original number had exceeded") will remain set after subtracting 1, which is how we know that ALL non-zero results AREN'T powers of 2.

Lastly, note that 2^0 = 1 which means that "1" is technically the "0th power of 2". But this is usually not what you want when you're checking for powers of 2. So you can prevent that by ensuring that the number is always >= 2 (when you're looking for unsigned integer power of 2s).

Here's an example written in Python:

def is_power_of_two(x: int) -> bool:
    return x >= 2 and (x & (x - 1)) == 0

GNU's glibc also uses the same algorithm in glibc/misc/sys/param.h:

#define powerof2(x)     ((((x) - 1) & (x)) == 0)

PS: Beware that I have only validated the algorithm for positive (unsigned) integers. I don't know if it works for negative integers too, and I don't want to try since that's not what I need in my application. But there's a good chance this binary-AND technique also works for negative numbers, since GNU glibc doesn't check for positive numbers. Use negative numbers at your own risk, though!

Answer 3

When you decrement a positive integer by 1:

1. if it is zero, you get -1.
2. if its least significant bit is 1, this bit is set to 0, the other bits are unchanged.
3. otherwise, all the low order 0 bits are set to 1 and the lowest 1 bit if set to 0, the other bits are unchanged.

Case 1: x & (x - 1) is 0, yet x is not a power of 2, trivial counter example.

Cases 2 and 3: if x and x-1 have no bits in common, it means the other bits in both of the above cases are all zero, hence the number has a single 1 bit, hence it is a power of 2.

If x is negative, this test does not work for two's complement representation of signed integers as either decrementing overflows or x and x-1 have at least the sign bit in common, which means x & (x-1) is not zero.

To test for a power of 2 the code should be:

int is_power_of_2(unsigned x) {
    return x > 0 && !(x & (x - 1));
}

Note that the above expression works for signed integer types as well:

int is_power_of_2(int x) {
    return x && !(x & (x - 1));
}

The test in the question is incorrect:

• x != 1 is redundant because (x & (x - 1)) is 0 for x == 1,
• the test evaluates to false for x == 0, which is not a power of 2.

It should be changed to:

    if ((num <= 0) || (num & (num - 1))) {
        /* num is not a power of 2 */
    }

Answer 4

Mathematically speaking Math.pow(2,n) is always a number above 0, there is an asymptote at x = 0. So we dont have to worry about number 0 and numbers below zero. ( Our domain is generally going to be real numbers)

Second Thing which many have suggested is that if we do an bitwise and of a number which is of the form Math.pow(2,n) that is all other numbers except leading one in binary form are zero, and the number below has all the numbers 1, and the leading one is zero ( this is what compiler will put )

and 1 & 0 = 0 so the number resulting will be zero.

function checkifisTwosPower(int number):
    if( number <= 0):
        output = false;
    else:
        if(equal(number & number -1, 0)) return true;
        else return false;
    fi;

Answer 5

#include <stdio.h>
void powerof2(int a);
int a;

int main()
{
    while(1)
    {
       printf("Enter any no. and Check  whether no is power of 2 or no \n");
       scanf("%d",&a);
       powerof2(a);
    }
}
void powerof2(int a)
{
    int count = 0;
    int b=0;
   while(a)
   {
     b=a%2;
     a=a/2;
     if(b == 1)
        {  count++;  }
   }
  if(count == 1)
   {
      printf("power of 2\n");
   }
  else
    printf("not power of 2\n");
}

Answer 6

Suppose n is the given number, if n is power of 2 (n && !(n & (n-1)) will return 1 else return 0

Answer 7

I prefer this approach that relies on two's complement:

bool checkPowTwo(int x){
    return (x & -x) == x;
}

Answer 8

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 9

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 10

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 11

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.