I understand that (2 * i == (i ^( i - 1) + 1) in Java will let me find if a number is a power of two. But can someone explain why this works?
What is an exponent of 2? In summary, the power of a number refers to how many times we will have to multiply the base. Let's put an example: 2 to the power of 5, which we can write as 2 5 2^5 25 means 2 × × 2 × 2 × 2 × 2 2 \times \times 2 \times 2 \times 2 \times 2 2××2×2×2×2.
Use the "Power" function to specify an exponent using the format "Power(number,power)." When used by itself, you need to add an "=" sign at the beginning. As an example, "=Power(10,2)" raises 10 to the second power.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With