Ten Ways to Check if an Integer Is a Power Of Two in C

http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/


To write a program to check if an integer is a power of two, you could follow two basic strategies: check the number based on its decimal value, or check it based on its binary representation. The former approach is more human-friendly but generally less efficient; the latter approach is more machine-friendly but generally more efficient. We will explore both approaches, comparing ten different but equivalent C functions.

Decimal-Based Approaches to Checking for Powers of Two

Decimal integers in C source code are converted to binary form, but technically you don’t need to know that; you can still treat them as decimal in the algorithms you write. The first six functions presented are based on that view.

1. Divide by Two

This function implements the “pencil and paper” method of checking whether an integer is a power of two. It repeatedly divides x, the 32-bit unsigned integer being tested, by 2. It divides until either the quotient becomes 1, in which case x is a power of two, or the quotient becomes odd before reaching 1, in which case x is not a power of two.

int isPowerOfTwo (unsigned int x)
{
 while (((x % 2) == 0) && x > 1) /* While x is even and > 1 */
   x /= 2;
 return (x == 1);
}

2. Check All

This function hard codes the first 32 nonnegative powers of two into one `OR’ expression. If x is a power of two less than 2,147,483,648, or 231, the expression will short-circuit according to C-semantics. If x is not a power of two or is 231 , all 32 values will be inspected.

int isPowerOfTwo (unsigned int x)
{
 return (
   x == 1 || x == 2 || x == 4 || x == 8 || x == 16 || x == 32 ||
   x == 64 || x == 128 || x == 256 || x == 512 || x == 1024 ||
   x == 2048 || x == 4096 || x == 8192 || x == 16384 ||
   x == 32768 || x == 65536 || x == 131072 || x == 262144 ||
   x == 524288 || x == 1048576 || x == 2097152 ||
   x == 4194304 || x == 8388608 || x == 16777216 ||
   x == 33554432 || x == 67108864 || x == 134217728 ||
   x == 268435456 || x == 536870912 || x == 1073741824 ||
   x == 2147483648);
}

3. Check Next Power

This function computes each power of two incrementally, quitting when x is less than or equal to the current power of two.

int isPowerOfTwo (unsigned int x)
{
 unsigned int powerOfTwo = 1;

 while (powerOfTwo < x && powerOfTwo < 2147483648)
   powerOfTwo *= 2;
 return (x == powerOfTwo);
}

The hard coded constant for 231 prevents overflowing the 32-bit unsigned integer.

4. Linear Search

This function is the same as the Check Next Power algorithm except that the powers of two are precomputed and stored in a table.

int isPowerOfTwo (unsigned int x)
{  
 unsigned int powersOfTwo[32] = 
   {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,
    65536,131072,262144,524288,1048576,2097152,4194304,8388608,
    16777216,33554432,67108864,134217728,268435456,536870912,
    1073741824,2147483648};

 int exponent = 0;

 while (powersOfTwo[exponent] < x && exponent < 31)
   exponent++;
 return (x == powersOfTwo[exponent]);
}

5. Binary Search

This function does a binary search of powers of two stored in a table.

int isPowerOfTwo (unsigned int x)
{  
 unsigned int powersOfTwo[32] = 
   {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,
    65536,131072,262144,524288,1048576,2097152,4194304,8388608,
    16777216,33554432,67108864,134217728,268435456,536870912,
    1073741824,2147483648};

 unsigned char isAPowerOfTwo;

 int interval = 16;
 int exponent = interval; /* Start out at midpoint */ 
 
 switch (x) {
   case 0:
	isAPowerOfTwo = 0;
        break;
   case 1: /* Special case makes binary search easier */
	isAPowerOfTwo = 1;
	break;
   default:
     while (x != powersOfTwo[exponent] && interval > 1) {
       if (x < powersOfTwo[exponent])
        exponent -= interval/2;
       else
        exponent += interval/2;
       interval /= 2;
     }
     isAPowerOfTwo = x == powersOfTwo[exponent];
 }
 
 return (isAPowerOfTwo);
}

6. Log Search

This function uses logarithms to determine if x is a power of two, put perhaps not in the way you’d expect. The log in base 2 of x, or log2(x), is the exponent n to which 2 is raised to get x. Mathematically, if n is an integer, then x is a power of two; if n is not an integer, then x is not. But in a computer, when floating-point calculations are used, things don’t always work out this neatly (see section “Beware of Logarithms” for more about this.)

In this case, the solution is to choose the two integral exponents that bound the logarithm and compare x to their corresponding powers of two; x can only be a power of two if it matches one of the two.

Since Visual C++ does not have a built-in function for log2(x), a change of base is used to compute it.

int isPowerOfTwo (unsigned int x)
{  
 int exponent = 0;
 unsigned char isAPowerOfTwo;

 unsigned int powersOfTwo[32] = 
   {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,
    65536,131072,262144,524288,1048576,2097152,4194304,8388608,
    16777216,33554432,67108864,134217728,268435456,536870912,
    1073741824,2147483648};

 if (x == 0 || x > 2147483648) 
   isAPowerOfTwo = 0;
 else
   {
    exponent = (int)(log((double)x)/log(2.0)); /* Log base 2 */
    isAPowerOfTwo = (x == powersOfTwo[exponent] ||
                     x == powersOfTwo[exponent+1]);
   }
 return (isAPowerOfTwo);
}

When the exponent is 31, the OR expression will short-circuit before trying to access the table out-of-bounds.

Binary-Based Approaches to Checking for Powers of Two

An arguably more direct way to check if an integer is a power of two is to access its binary representation. An unsigned integer is a power of two if and only if it has exactly one 1 bit. The four functions below are based on that observation.

7. Count Ones

This function is probably the first that comes to mind — counting 1 bits. Of course you don’t need to count all 1 bits; you can stop counting if more than one 1 bit is found.

int isPowerOfTwo (unsigned int x)
{
 unsigned int numberOfOneBits = 0;

 while(x && numberOfOneBits <=1)
   {
    if ((x & 1) == 1) /* Is the least significant bit a 1? */
      numberOfOneBits++;
    x >>= 1;          /* Shift number one bit to the right */
   }

 return (numberOfOneBits == 1); /* 'True' if only one 1 bit */
}

8. Shift Right

This function is the equivalent of the Divide by Two algorithm. Dividing a binary integer by 2 is the same as shifting it right one bit, and checking whether a binary integer is odd is the same as checking if its least significant bit is 1.

int isPowerOfTwo (unsigned int x)
{
 while (((x & 1) == 0) && x > 1) /* While x is even and > 1 */
   x >>= 1;
 return (x == 1);
}

The only way the statement “x == 1” becomes true is when there is only one 1 bit in x to start with.

9. Decrement and Compare

This function is a common one-liner you’ll find on the Web, and is how the check is implemented in malloc.c in the GNU C Library (glibc).

int isPowerOfTwo (unsigned int x)
{
  return ((x != 0) && !(x & (x - 1)));
}

There are two halves to the expression: x != 0 and !(x & (x – 1)). The first half makes 0 a special case, since the second half only works correctly for positive numbers. The second half — the interesting part of the expression — is true when x is a power of two and false when x is not. Let’s see why.

Let n be the position of the leftmost 1 bit if x. If x is a power of two, its lone 1 bit is in position n. This means x – 1 has a 0 in position n. To see why, recall how binary subtraction works. When subtracting 1 from x, the borrow propagates all the way to position n; bit n becomes 0 and all lower bits become 1. Now, since x has no 1 bits in common with x – 1, x & (x – 1) is 0, and !(x & (x – 1)) is true.

Here are some examples (I’ll use 8-bit unsigned integers to keep things manageable):

Decrement and Compare, when x is a power of two
x x – 1 x & (x – 1)
00000001 00000000 00000000
00000100 00000011 00000000
00010000 00001111 00000000

If x is not a power of two, x – 1 has a 1 in position n. This is because the borrow will not propagate to position n. Subtraction borrows from the lowest 1 bit, which by virtue of x not being a power of two, is before position n. The lowest 1 bit is like a firewall that prevents the borrow from reaching position n. Since x and x – 1 have at least one 1 bit in common — at position n — x & (x – 1) is nonzero, and !(x & (x – 1)) is false.

Here are some examples:

Decrement and Compare, when x is a NOT power of two
x x – 1 x & (x – 1)
00000011 00000010 00000010
00000110 00000101 00000100
00001011 00001010 00001010
00011100 00011011 00011000

10. Complement and Compare

This function is another one-liner that can be found on the Web. At it’s core, it is similar to the Decrement and Compare method.

int isPowerOfTwo (unsigned int x)
{
  return ((x != 0) && ((x & (~x + 1)) == x));
}

The first half of the expression ensures that x is a positive integer. The second half of the expression, (x & (~x + 1)) == x, is true only when x is a power of two. It compares x with its two’s complement. The two’s complement of x is computed with ~x + 1, which inverts the bits of x and adds 1 (~x + 1 is equivalent to -x, but negation is technically illegal for an unsigned integer).

Let n be the position of the leftmost 1 bit if x. If x is a power of two, its lone 1 bit is in position n. This means ~x has a 0 in position n and 1s everywhere else. When 1 is added to ~x, all positions below n become 0 and the 0 at position n becomes 1. In other words, the carry propagates all the way to position n. So what happens is this: negating x inverts all its bits, but adding 1 inverts them back, from position n on down. So, (x & (~x + 1)) == x is true.

Here are some examples:

Complement and Compare, when x is a power of two
x ~x ~x + 1 x & (~x + 1)
00000001 11111110 11111111 00000001
00000100 11111011 11111100 00000100
00010000 11101111 11110000 00010000

If x is not a power of two, ~x has at least one 0 below position n. When 1 is added, the carry will not propagate to position n. In other words, not all bits from position n and below will be inverted back. This means (x & (~x + 1)) == x is false.

Here are some examples:

Complement and Compare, when x is a NOT power of two
x ~x ~x + 1 x & (~x + 1)
00000011 11111100 11111101 00000001
00000110 11111001 11111010 00000010
00001011 11110100 11110101 00000001
00011100 11100011 11100100 00000100

Endianness

In case you were wondering, these algorithms are endian-independent. Integers are accessed numerically and logically with arithmetic, bitwise, and logical operators, not as byte strings.

Comparing the Algorithms

As for readability, the decimal-based algorithms are more human-friendly. Divide by Two and Check Next Power are methods you might use if you had to check by hand; Check All, Linear Search, Binary Search, and Log Search are methods you might use if you had a table of powers of two to consult. The binary-based algorithms are designed for machines, but if you understand how they work, you’ll appreciate their elegance.

As for performance, the table below shows how the algorithms stack up. I wrote a test case to call each function with all 232 unsigned integer values. I used the Microsoft Visual C++ 2008 Express Edition compiler and ran the program on an Intel Core Duo machine. I repeated the test case three times and computed the average running time for each function.

The algorithms are listed from fastest to slowest. As you might expect, the binary-based functions are generally the fastest.

Running Time to Check All 232 Integers
Algorithm Elapsed Time
No. Name
10 Complement and Compare 6 minutes, 43 seconds
9 Decrement and Compare 6 minutes, 51 seconds
8 Shift Right 7 minutes, 2 seconds
2 Check All 8 minutes, 42 seconds
7 Count Ones 10 minutes, 14 seconds
1 Divide by Two 10 minutes, 44 seconds
3 Check Next Power 14 minutes, 8 seconds
5 Binary Search 18 minutes, 17 seconds
6 Log Search 21 minutes, 58 seconds
4 Linear Search 26 minutes, 20 seconds

How NOT to Check

Beware of Signed Integers

If you want to check signed integers, you either have to modify the routines above or filter out negative numbers before calling them. As an example, consider Decrement and Compare. If you switched its parameter from unsigned integer to signed integer, it would handle all negative numbers correctly except one: -2,147,483,648. The problem is that in two’s complement, the largest negative integer of any given word size looks like a power of two. In this case, that’s -231, or -2,147,483,648, and it looks like this: 10000000000000000000000000000000. The fix is to change the check “x != 0” to “x > 0”.

Beware of Logarithms

The following code is wrong:

int isPowerOfTwo(unsigned int x)
{
  /* Incorrect way to check */
 double exponent;
 unsigned char isAPowerOfTwo;

 if (x == 0)
   isAPowerOfTwo = 0;
 else
   {
    exponent = log((double)x)/log(2.0); /* Log base 2 */
    isAPowerOfTwo = int(exponent) == exponent;
   }
 return (isAPowerOfTwo);
}

As I hinted in the Log Search algorithm section, the logarithm calculation can return nonintegers when an integer is expected. This is true of the above function, and specifically, for two powers of two: 536,870,912 (2^29) and 2,147,483,648 (2^31). It computes log2(229) as 29.000000000000004, and log2(231) as 31.000000000000004. These are extremely close to, but are not, integers.

You might think you could build in a tolerance so that “close” values are treated as integers. But where do you draw the line? log2(229 + 1) = 29.000000003, and log2(231 + 1) = 31.0000000007. Should those be treated as integers? No!

The solution is to choose the two integral exponents that bound the logarithm and compare x to their corresponding powers of two. That is what we did in section “Log Search”.

Determining Which Power of Two an Integer Is

If you also want to know which power of two an integer is, that is, what its exponent is, the functions above must be modified. The Linear Search and Log Search functions require the least change; they just have to return the computed exponent. The other functions would need to be changed to varying degrees, some to the point where the code would change dramatically.

Summary

I presented ten C functions that showed different ways of checking whether an integer is a power of two. No doubt you could implement them differently, like using macros instead of functions. Beyond that, you could modify them to work for different word sizes. You could also translate them easily to other languages, like PHP, Java, and of course, C++.

The two approaches I discussed should give you more insight into the nature of the powers of two, both as decimal and binary numbers.

Afterword (July 2011)

I wrote this article two and a half years ago, but it recently got a lot of attention on Reddit and Hacker News. Based on that discussion — and the resulting reader comments below — I’d like to make a few additional points.

This article was intended mainly for students, written as if they were given this problem as an assignment. The decimal-based approaches appear first because they are more likely to be understood, and more likely to be what a beginner would come up with on their own. The binary-based approaches are more sophisticated, so appear after the more obvious solutions. There’s no doubt that methods 9 (Decrement and Compare) and 10 (Complement and Compare) are the ones to use in practice — they are short, simple (once you know how they work!), fast, and like all the binary-based methods, independent of integer size.

As some readers pointed out, most of the decimal-based methods have some dependence on the binary representation: the maximum power of two in an unsigned integer (231) must be known. In any case, the point is that the methods use basic mathematical operations — on constants specified in decimal — instead of bit manipulation.

As for the benchmarks, if you use a different compiler — or different compiler options — you’ll get different results. For example, I used debug mode in my tests; when I reran them in release mode (on Visual Studio 2010 Express Edition), they ran much faster. While methods 9 and 10 were still the fastest, some of the other methods switched positions. One difference worth noting is that method 1 (Divide by Two) and method 8 (Shift Right) executed in almost identical times; this makes sense, since they were compiled into virtually identical code by release mode optimizations.

As you’ll see from the Reddit and Hacker News discussions, and from the comments below, there are many more ways to check for powers of two — and many variations (some improved) on the methods I presented. Some of those methods are faster than methods 9 and 10, but they use OS-dependent function calls or inline assembler. I don’t consider them C-based methods.

Dingbat

52 Responses to “Ten Ways to Check if an Integer Is a Power Of Two in C”

  1. Jeff Says:

    A variation on counting the ones (#7), though I don’t know how fast it might be, uses a lookup table. For example, take 4-bits at a time (shifting and masking as necessary) and use the value to index into an array like:

    int bitpop[16] = { 0, 1, 1, 2 … 2, 3, 3, 4 };

    Shift and mask by 8 and index into a 256-element array fir more speed (and memory).

    Offsetting the slowness of counting ones is you get back more information than just whether or not a value is a power of two.

  2. Rick Regan Says:

    Jeff,

    I coded your idea, but in the spirit of how I coded #7 (quitting once the bit count exceeds 1):

    int isPowerOfTwo (unsigned int x)
    {
     unsigned int numberOfOneBits = 0;
     unsigned int oneBits[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
    
     while(x && numberOfOneBits <= 1)
       {
        numberOfOneBits += oneBits[x & 0xF];
        x >>= 4; /* Examine next 4 bits */
       }
    
     return (numberOfOneBits == 1); /* 'True' if only one 1 bit */
    }
    

    This ran in 16 minutes, 38 seconds 13 minutes, 1 second, making it slower than #7.

    The algorithms with the table lookups seem good in principle, but are among the slowest. Maybe they’d compare better for 64-bit integers? (Of course humans may no longer inhabit the planet when those runs finish ;) )

  3. Jeff Says:

    Ii confess my surprise at the lookup table’s poor performance.

    So I tried it on my machine (Mac w/ 2.16 GHz Intel Cor 2 Duo, and gcc 4.0.1 (Apple Inc. build 5465, using only default options).

    I also added a modified lookup function where the lookup array was a global. I repeated the three cases (the first two literally cut-and-pasted from above) 10 times each, and got…

    #7: 152 seconds
    lookup table w/ local array: 105 s
    lookup table w/ global array: 80 s

    So, one could conclude that
    a) chip and compiler can make a BIG difference
    b) you need a faster machine! :) :)

  4. Rick Regan Says:

    Jeff,

    I ran them on an Intel Core Duo processor T2050, 1.60 GHz. But that’s only part of the difference. I didn’t mention that my loop that called each function 2^32 times also included a verification that the result was correct (seems kind of recursive, doesn’t it?). I really shouldn’t have left the checks in after I verified the algorithms, so I repeated the runs without them and updated the tables above. The algorithms still perform in the same relative order.

    As an aside, I also re-ran your “table method” algorithm against #7 without short-circuiting the while loops (so counted all 1 bits). Your table algorithm did indeed perform better in that case.

  5. Find if a number is a power of two, v2 « Kami Kode Says:

    […] to how to find using only bitwise operators, if a number is a power of two. This site led me to another site with 10 different ways to check if an integer is a power of two; the one I need is a slight […]

  6. duedl0r Says:

    You don’t compare doubles with the == operator. You always have to do this: |d1 – d2| < eps. eps small. So in your log search you define a proper eps to get correct results.

  7. Sycren Says:

    Just wondering, but to find which power of two it is, would you just find the index of the 1 bit -1. ie 8 is 1000 so 4th position – 1.. so.. 2^3

  8. John Says:

    I wrote a similar post using the Factor programming language, if you’re curious to see how that looks:

    http://re-factor.blogspot.com/2011/04/powers-of-2.html

  9. Ricardo Says:

    You can find the binary-based one-liners (ie. 9 and 10) in “Hacker’s delight”, 2nd chapter (“Basics”)

    http://www.hackersdelight.org/basics.pdf

    along with many other interesting stuff :)

  10. James Says:

    Was curious how the 4 bit lookup would actually compare to an 8 or 16. Simple benchmark on my machine (10k iterations of checks between 0-500k, avg of 3) gives:

    4 bit tables : 74 seconds
    4 bit, modified: 52 seconds
    8 bit tables : 29 seconds
    complement and compare: 23 seconds
    16 bit tables: 21 seconds

    Where the 4-bit table is the provided code above. “4 bit, modified” simply unrolled the loop.

    For the 8/16 bit tests, I initialized a static table (included in the timing) and then ran the 10k iterations. Only the “4 bit” test involved short circuiting (it’s more expensive to check/branch than to just do the computations, it seems)

  11. James Says:

    One other thought: the checks for Complement and Compare and Decrement and Compare are in the wrong order – most of the time, x != 0. Checking it first serves causes you to check that 2^32 times, vs 32 times. ~10% speedup, vs. my previous numbers, and it makes complement-and-compare a contender again, and decrement-and-compare the winner, speedwise (for my machine, at least).

    Decrement-and-compare: 21s
    Decrement-and-compare (reversed checks): 19s

    Complement-and-compare: 23s
    Complement-and-compare (reversed): 21s

    In both cases a 10% speedup by swapping the ordering to do the most-often-failed check first.

  12. cookiemonster Says:

    What about x & (int.max-1) ==0 ?

  13. Matt Says:

    What about the bsr instruction, which Visual Studio should be able to access with the intrinsics: _BitScanReverse, _BitScanReverse64?

    bsr – Scans source operand for first bit set.

    Rough pseudo-code would be:

    bsr in,out
    return (out>>y == in);

    That should be maybe faster than anything you’ve shown so far.

  14. Matt Says:

    In the above comment I meant to say:

    return (1>>out == in);

  15. Matt Says:

    Sorry I had my shift backwards in the examples above, here is the working code, it seems to be pretty fast.

    unsigned long in;
    unsigned long out = 0;

    for (in = 1; in<ULONG_MAX; in++)
    {
    _BitScanReverse(&out, in);
    bool isPowerOfTwo = ((1<<out) == in);
    if (isPowerOfTwo)
    {
    cout << in << " is a power of 2" << endl;
    }
    }

  16. Fantasy Says:

    Part of SSE4.2 has POPCNT instruction. This could improve solution #7.

  17. Chase Sechrist Says:

    Could you also translate this to a few common architectures? I would be very interested in seeing a person’s interpretation of the code represented in asm, and what the common compiler tools are outputting.

    I bet the compilers are dumb.

  18. Chase Sechrist Says:

    Well actually, now that I think about it, they have to be.. Don’t processors add more complex operations over time that reduce the amount of C code you have to write?

  19. etrain Says:

    count me baffled and angry that
    1) shift right wasn’t the only option.
    2) it’s not the fastest option.

    – failed C hacker.

  20. Asokan Pichai Says:

    int isPowerOf2( unsigned int n ) {
    if ( n == 1) return 1;
    if (n % 2 == 1) return 0;
    return isPowerOf2(n/2);
    }

    is my favourite way of writing this.

  21. Nakosa Says:

    Or the following, to prevent StackOverflow when n == 0;

    private static function isPowerOf2(n:int):int {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n % 2 == 1) return 0;
    return isPowerOf2Recursive(n/2);
    }

  22. epb Says:

    Did you have optimizations enabled for the test?

    Any decent compiler (optimizer, rather) would generate identical code for #2 and #8 – shift and mask instead of divide and modulo by constant power of two, yet they are apart by miles.

  23. Rick Regan Says:

    @duedl0r,

    I am not using doubles other than when I cast them to int — so I do not “compare doubles with the == operator”. I do mention in the “how not to check” section that you’d need a “tolerance” if you want to compare doubles directly; but as I mention, how do you pick the tolerance to get “correct results”?

  24. Rick Regan Says:

    @Sycren,

    Yes, once you know it’s a power of two you can find the “index” of the 1 bit to get the exponent; but that extra code, for example, would turn the “one-liners” into multi-liners.

  25. Rick Regan Says:

    @James,

    Thanks for sharing your “table lookup” evaluation. And as for reversing the “if not 0″ checks in “Complement and Compare” and “Decrement and Compare” — I agree.

  26. Rick Regan Says:

    @cookiemonster,

    Sorry — I don’t understand your question.

  27. Rick Regan Says:

    @epb,

    I assume you meant #1 (Divide_By_Two) and #8 (Shift_Right). I was running with the default settings (and in debug mode, for no good reason). This is the generated code:

    Divide_By_Two

     while (((x % 2) == 0) && x > 1) /* While x is even and > 1 */
    0041BA1E  mov         eax,dword ptr [x]  
    0041BA21  xor         edx,edx  
    0041BA23  mov         ecx,2  
    0041BA28  div         eax,ecx  
    0041BA2A  test        edx,edx  
    0041BA2C  jne         isPowerOfTwo_Divide_By_Two+3Eh (41BA3Eh)  
    0041BA2E  cmp         dword ptr [x],1  
    0041BA32  jbe         isPowerOfTwo_Divide_By_Two+3Eh (41BA3Eh)  
       x /= 2;
    0041BA34  mov         eax,dword ptr [x]  
    0041BA37  shr         eax,1  
    0041BA39  mov         dword ptr [x],eax  
    0041BA3C  jmp         isPowerOfTwo_Divide_By_Two+1Eh (41BA1Eh) 
    

    Shift_Right

     while (((x & 1) == 0) && x > 1) /* While x is even and > 1 */
    0041C46E  mov         eax,dword ptr [x]  
    0041C471  and         eax,1  
    0041C474  jne         isPowerOfTwo_Shift_Right+36h (41C486h)  
    0041C476  cmp         dword ptr [x],1  
    0041C47A  jbe         isPowerOfTwo_Shift_Right+36h (41C486h)  
       x >>= 1;
    0041C47C  mov         eax,dword ptr [x]  
    0041C47F  shr         eax,1  
    0041C481  mov         dword ptr [x],eax  
    0041C484  jmp         isPowerOfTwo_Shift_Right+1Eh (41C46Eh)  
    

    Update: In release mode, the code is identical, except for comments and labels; here is the assembler (for Divide_By_Two):

     while (((x % 2) == 0) && x > 1) /* While x is even and > 1 */
    00401003  mov         eax,dword ptr [x]  
    00401006  test        al,1  
    00401008  jne         isPowerOfTwo_Divide_By_Two+1Bh (40101Bh)  
    0040100A  lea         ebx,[ebx]  
    00401010  cmp         eax,1  
    00401013  jbe         isPowerOfTwo_Divide_By_Two+1Bh (40101Bh)  
       x /= 2;
    00401015  shr         eax,1  
    00401017  test        al,1  
    00401019  je          isPowerOfTwo_Divide_By_Two+10h (401010h)  
    
  28. Rick Regan Says:

    @epb,

    I compiled #1 and #8 under MinGW with gcc -O2; both produce identical code (only label names differ) as you expected:

    	pushl	%ebp
    	movl	%esp, %ebp
    	movl	8(%ebp), %eax
    	testb	$1, %al
    	je	L72
    	jmp	L68
    	.p2align 2,,3
    L73:
    	shrl	%eax
    	testb	$1, %al
    	jne	L68
    L72:
    	cmpl	$1, %eax
    	ja	L73
    L68:
    	decl	%eax
    	sete	%al
    	movzbl	%al, %eax
    	leave
    	ret
    
  29. Rick Regan Says:

    @Matt,

    Here’s how I coded your function, in the style of my article:

    int isPowerOfTwo (unsigned int x)
    {
     unsigned long index;
    
     _BitScanReverse(&index, x);
     return ((1<<index) == x);
    }
    

    I ran it on the same machine I ran the others on, but in release mode (I reran all the others in release mode too, having run them in debug mode the first time). Guess what? Yours is the fastest.

  30. Rick Regan Says:

    @Asokan and @Nakosa ( :) ),

    Here’s how I coded your function, in the style of my article:

    int isPowerOfTwo (unsigned int x)
    {
     if (x == 0) return 0;
     if (x == 1) return 1;
     if (x % 2 == 1) return 0;
     return isPowerOfTwo(x/2);
    }
    

    By my latest tests, it places as the 6th fastest (slower than “Divide by Two”).

  31. foobar Says:

    int is_power_of_two (int x) {
    return x != 0 && (x & -x) == x;
    }

  32. Rick Regan Says:

    @foobar,

    That’s the same as #10 (“Complement and Compare”) since, as I noted, ~x + 1 is equivalent to -x (I am using unsigned integers).

  33. Friday miscellany — The Endeavour Says:

    […] language fixes something 10 ways to check whether an integer is a power of 2 Version control by […]

  34. Ivan Tikhonov Says:

    Count Ones is actually better to be renamed and rewritten as “Check the only one”

    So basically you:

    1. find that one exists.
    2. find that no ones exist beyond first.

    This way you remove increment and condition inside of loop.


    int isPowerOfTwo (unsigned int x)
    {
    while(x && (x&1)==0) x>>=1; // shift till 1 found
    if(!x) return 0; // no ones found at all
    x>>=1;
    return x==0; // check there is no ones past first one
    }

    Also if you unroll while loop there will be no need for “x not zero” checking at all.

  35. Stefanus Du Toit Says:

    (x & (x – 1)) == 0

    If I remember right I first read this in Hacker’s Delight or HAKMEM.

  36. Stefanus Du Toit Says:

    (and yes that is essentially no 9 – though I often don’t care about the zero case)

  37. Rick Regan Says:

    @Ivan,

    I agree. Your code is a cleaner version of my “Count Ones” (#7) — and a lot faster.

  38. Pseudonym Says:

    If you’re on a POSIX.1 compliant platform, should contain the ffs() function. If you’re lucky, your system will use your CPU’s built-in priority encoder instruction to implement this, and you can do the following. Hopefully no loops, and at most one branch or conditional move:

    int isPowerOfTwo(int x)
    {
    int bit = ffs(x);
    return bit ? ((1 << (bit – 1)) == x) : 0;
    }

  39. AAL Says:

    You can use this macro and a bit of other code to quickly determine if only one bit is set, then check if it is BIT0the odd case the number 1:

    /* Returns ZERO if paramter has a single bit set high */
    #define nHasOnlyOne1( p ) ( ((p)==0) || ( (p) & ((p)-1) ) )

  40. Harold Rabbie Says:

    If you’re using gcc, that compiler includes a builtin function
    int __builtin_popcount (unsigned int x) which returns the number of 1-bits in x.

    So (__builtin_popcount (x) == 1) is true iff x is a power of 2.
    Some processor architectures even include a population count instruction.

  41. Krzysztof Wesołowski Says:

    Also note that some approaches can be implemented in C as macro to be calculated with constant argument at compile time (or for example with template argument with C++ to do static_asserts etc.).

  42. Rick Regan Says:

    @AAL,

    Your code is the negation of “Decrement and Compare.” You just need to negate it to get the right answer: if !nHasOnlyOne1(x) is true, the x is a power of two.

  43. Powers of two « Computing: the Science of Nearly Everything Says:

    […] big thanks to Rick Regan and his in-depth Ten Ways to Check if an Integer Is a Power Of Two in C blog post) LD_AddCustomAttr("AdOpt", "1"); LD_AddCustomAttr("Origin", "other"); […]

  44. Lior Says:

    Another way I was today inform of (assuming word length is reasonable, n): create a Boolean array, sized 2^n. For each element, store true if the index is a power of two and false otherwise: b[0]=false, b[1]=true, b[2]=true, b[3]=false, b[4]=true, b[5]=false,…

    Time complexity is now O(1).

  45. AASHISH Says:

    I give u best solution.
    Logic–> when u convert a decimal number to its binary number then u get series of 1 and 0
    Now if a number is power of two then u will observe it has only one (bit 1) and if u do binary AND of of it with a number just previous to it ,then u will get series of Zeros
    For example
    8=1000(binary form ) here u can see only one (bit 1) is there and rest are zeros
    Now the number just previous to 8 is 7
    so, 7=0111 and if u perform AND operation on it as
    1000(8)
    (AND) 0111(7)
    ———
    0000(0)
    ———
    So if we perform AND operation between the number (which we want to check is a power of two or not) and the number just previous to it and result comes as zeros then its power of two otherwise it’s not.

    PROGRAM(IN C_LANGUAGE)

    #include
    #include
    main()
    {
    int num, num1,sum;
    clrscr();
    printf(“Enter the number”);
    scanf(“%d”,&num);
    printf(“\nEntered number=%d”,num);
    num1=num-1;
    sum=num & num1;
    if(sum==0)
    printf(“\n Entered number is power of two”);
    else
    printf(“\n Entered number is not power of two”);
    getch();

    Voila!!!! Isn’t it sooooo easy!!!!
    Enjoy!!!

  46. Rick Regan Says:

    @AASHISH,

    Yes, that’s method 9, “Decrement and Compare” (except you don’t check if num == 0).

  47. Divanushka Says:

    return (x > 0) && ((x & ~(x – 1)) == x)

  48. Rick Regan Says:

    @Divanushka,

    That works too. If x is a power of two, x – 1 is the inversion of x, that is, a 0 followed by all 1s. Inverting that gives a 1 followed by all 0s, that is, x.

  49. SAMPATH Says:

    I think we can improve the performance of 10 solution by re arranging the conditional statement so that , since for most of the inputs the first condition will ((x & (~x + 1)) == x) fail because of which the second condition won’t be executed.(short circuit)

    10. Complement and Compare

    int isPowerOfTwo (unsigned int x)
    {
    return (((x & (~x + 1)) == x)&& (x != 0));
    }

  50. Bit Wise concepts and tricks | GO 2 Computer Science and Trading Technologies Says:

    […] http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ […]

  51. Phuc LV Says:

    There is a very good way to determine if a non-zero number is a power of 2 in the famous bithacks page: (v & (v – 1)) == 0
    To check for zero, use v && !(v & (v – 1));
    http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

  52. Rick Regan Says:

    @Phuc LV,

    That’s method 9, “Decrement and Compare”.

Leave a Comment

(To reduce spam, cookies must be enabled)


css.php