Checking if a number is a power of 2 without loops

Question

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;
}

• sneakysnake: 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?
• JDługosz: 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.
• Roland Illig: For related bit-fiddling tricks, see the book "Hacker's Delight".

Answer 1

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)

Answer 2

• 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).

• Toby Speight: Probably ought to add a few negative numbers to the test suite of corner cases - or (better) change nr to an unsigned type.