4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – sneakysnake May 14 '18 at 22:00
  • \$\begingroup\$ 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. \$\endgroup\$ – JDługosz May 15 '18 at 2:12
  • \$\begingroup\$ For related bit-fiddling tricks, see the book "Hacker's Delight". \$\endgroup\$ – Roland Illig May 15 '18 at 4:45
3
\$\begingroup\$

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)
\$\endgroup\$
10
\$\begingroup\$
  • 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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.