Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Power of 2 formula help

Tags:

java

math

binary

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?

like image 448
Peter Chappy Avatar asked Feb 22 '11 18:02

Peter Chappy


People also ask

How do you calculate the power of 2?

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.

How do you write 2 powers in Excel?

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.


1 Answers

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.

like image 52
逆さま Avatar answered Sep 27 '22 21:09

逆さま