# Checking if a number is a power of 2 without loops

I made a short program which checks if a number is a power of 2 without using any loops. The idea: A number which is a power of 2 must have only one bit "1" ( ex: 8= 1000, 4=100 and so on). Suppose we have a power of 2:nr = 10...000 (in binary), if we subtract 1 we will get something like this:nr-1= 01...111. Now, if we do nr&(nr-1) we should always get 0 if the nr is a power of 2 and some random number if it isn't. What other solutions are there for this problem?

#include <stdio.h>
#include <stdlib.h>

int main()
{
int nr;
scanf("%d",&nr);
if((nr&(nr-1))==0)
{
printf("\n%d is a power of 2",nr);
}
else
{
printf("\n%d is not a power of 2",nr);
}
return 0;
}

• but i'm not checking if a number is divisible by 2, i'm checking if a number is a power of 2. what do you mean? – sneakysnake May 14 '18 at 22:00
• CPUs have a "population count" instruction built in. Compilers often provide access to it via an intrinsic. So return ++popcnt(nr)==1; is all you need. – JDługosz May 15 '18 at 2:12
• For related bit-fiddling tricks, see the book "Hacker's Delight". – Roland Illig May 15 '18 at 4:45

What other solutions are there for this problem?

OP's code can incorrectly reports 0 and -2147483648 (INT_MIN) are both powers-of 2.

A simple change is to use unsigned rather than int @Toby Speight. This avoids 1) the corner case of INT_MIN - 1 which is undefined behavior and 2) and-ing a negative int, which is implementation defined behavior.

unsigned nr;
scanf("%u",&nr);
if ((nr & (nr-1)) == 0 && nr)

• Use only necessary #includes. The <stdlib.h> is not needed here.

• Give your operators some breathing space. ((nr&(nr-1))==0) is next to unreadable.

• Separate logic from presentation:

int is_power_of_two(int nr)
{
return nr & (nr - 1) == 0;
}


is much more reusable.

• Care about corner cases. Your code claims that 0 is a power of two (which it is not).

• Probably ought to add a few negative numbers to the test suite of corner cases - or (better) change nr to an unsigned type. – Toby Speight May 15 '18 at 10:25