CODEWITHSUNDEEP
algorithm
GurdeepS
GurdeepS

Reputation: 67223

Query about working out whether number is a power of 2

Using the classic code snippet:

if (x & (x-1)) == 0

If the answer is 1, then it is false and not a power of 2. However, working on 5 (not a power of 2) and 4 results in:

0001 1111 0001 1111 0000 1111

That's 4 1s.

Working on 8 and 7:

1111 1111 0111 1111

0111 1111

The 0 is first, but we have 4.

In this link (http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/) for both cases, the answer starts with 0 and there is a variable number of 0s/1s. How does this answer whether the number is a power of 2?

Upvotes: 3

Views: 2206

Answers (4)

Ajay Bidyarthy
Ajay Bidyarthy

Reputation: 156

((n & (n-1)) == 0)

It checks whether the value of “n” is a power of 2.

Example: 

 if n = 8, the bit representation is 1000
 n & (n-1) = (1000) & ( 0111) = (0000)
 So it return zero only if its value is in power of 2.
 The only exception to this is ‘0’.
 0 & (0-1) = 0 but ‘0’ is not the power of two.

Why does this make sense?

Imagine what happens when you subtract 1 from a string of bits. You read from left to right, turning each 0 to a 1 until you hit a 1, at which point that bit is flipped:

1000100100 -> (subtract 1) -> 1000100011

Thus, every bit, up through the first 1, is flipped. If there’s exactly one 1 in the number, then every bit (other than the leading zeros) will be flipped. Thus, n & (n-1) == 0 if there’s exactly one 1. If there’s exactly one 1, then it must be a power of two.

Upvotes: 1

Charlie Martin
Charlie Martin

Reputation: 112366

Keep in mind that if x is a power of 2, there is exactly 1 bit set. Subtract 1, and you know two things: the resulting value is not a power of two, and the bit that was set is no longer set. So, when you do a bitwise and &, every bit that was set in x is not unset, and all the bits in (x-1) that are set must be matched against bits not set in x. So the and of each bit is always 0.

In other words, for any bit pattern, you are guaranteed that (x&(x-1)) is zero.

Upvotes: 1

Joel
Joel

Reputation: 19358

Any power of two number can be represent in binary with a single 1 and multiple 0s.

eg. 
10000(16) 
1000(8) 
100(4)

If you subtract 1 from any power of two number, you will get all 1s to the right of where the original one was.

10000(16) - 1 = 01111(15)

ANDing these two numbers will give you 0 every time.

In the case of a non-power of two number, subtracting one will leave at least one "1" unchanged somewhere in the number like:

10010(18) - 1 = 10001(17)

ANDing these two will result in 

10000(16) != 0

Upvotes: 5

Tyler McHenry
Tyler McHenry

Reputation: 76660

You need refresh yourself on how binary works. 5 is not represented as 0001 1111 (5 bits on), it's represented as 0000 0101 (2^2 + 2^0), and 4 is likewise not 0000 1111 (4 bits on) but rather 0000 0100 (2^2). The numbers you wrote are actually in unary.

Wikipedia, as usual, has a pretty thorough overview.

Upvotes: 8

Related Questions