Power of 2 formula help

I understand that (2 * i == (i ^( 开发者_JAVA技巧i - 1) + 1) in Java will let me find if a number is a power of two. But can someone explain why this works?

---

2*i == (i ^ (i-1)) + 1

Basically, if i was a a power of 2, it would have a single 1 in its bit pattern. If you subtract 1 from that, all the lower bits of that 1 bit become 1, and that power-of-two bit will become 0. Then you do an XOR on the bits, which produces an all 1 bit pattern. You add 1 to that, and you get the next power of 2.

Remember XOR truth table:

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

Example:

Let's say i is 256, which is this bit pattern.

100000000 = 2^8 = 256

100000000 - 1 = 011111111 = 2^7 + 2^6 + ... + 2^0 = 255

100000000 ^ 011111111 = 111111111 = = 2^8 + 2^7 + ... + 2^0 = 511

111111111 + 1 = 1000000000 = 2^9 = 512 = 2*i

Here's an example when you are not presented with a power of 2

i = 100 = 2^6 + 2^5 + 2^2

0110 0100

0110 0100 - 1 = 99 = 2^6 + 2^5 + 2^1 + 2^0 = 0110 0011

0110 0100 ^ 0110 0011 = 0000 0111 = 2^2 + 2^1 + 2^0 = 7

0000 0111 + 1 = 000 1000 = 2^3 = 8 != (2*i)

Simplified Version

Also, there's a modified version of this check to determine if some positive, unsigned integer is a power of 2.

(i & (i-1)) == 0

Basically, same rationale

If i is a power of 2, it has a single 1 bit in its bit representation. If you subtract 1 from it, the 1 bit becomes 0, and all the lower bits become 1. Then AND will produce an all 0 bit-pattern.

---

The important bit is the i^(i-1) (I'm assuming this is a small typo in the question). Suppose i is a power of 2. Then its binary expansion is a 1 followed by many zeroes. i-1 is a number where that leading 1 is replaced by a zero and all the zeroes are replaced by ones. So the result of the XOR is a string of 1's that's the same number of bits as i.

On the other hand, if i isn't a power of 2, subtracting 1 from it won't flip all of those bits - the xor then identifies which bits didn't carry from one place to the next when you subtracted 1. There'll be a zero in the result of the xor, so when you add the 1, it won't carry into the next bit position.