如何判斷一個數是否為2的Ｎ次方 (轉貼)

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

第九個方法很酷

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