Please do not top-post. Place your answer below or interspersed

with the text you are replying to.

<snip: Behaviour of "if (x && !(x & (x-1)) == 0)" for 8/1000b>

William wrote:

x & (x-1) = 0000

!(x & (x-1)) = 1 (since 0000 is just 0)

(x && !(x & (x-1))) = 1000 && 1 = 1

therefore, if (x && !(x & (x-1)) == 0)

returns false if x is a power of 2; true if x is NOT a power of 2.

Can someone please verify for a newbie like me?

Yep. Note that all bit operations should be performed only

on unsigned types and that the explanation below only holds

for nonnegative integers x.

I would rather parse the whole thing in another way; please have

a look at an operator precedence table of your choice:

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

x &&

is equivalent to

x!=0 &&

meaning x is a candidate for a power of two only if x is not zero.

The following logical expression is only evaluated if x!=0.

!(....) == 0

is equivalent to

(....) != 0

or

(....)

x & (x-1)

leaves all bits of x higher than (left of) the lowest (rightmost) set

bit untouched and sets the rest to 0: Let x = bb..b10...0:

bb..b10...0 - 1 is bb..b01...1

which becomes

bb..b00...0

under x & (x-1).

This means that for x!=0 the above is zero if bb..b is zero, i.e. if

x contains exactly one set bit, i.e. if x is a power of two.

So, if we want to test for powers of two, we need

if (x && !(x & (x-1)))

or

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

The original test tests for nonzero non-power-of-two x.

Cheers

Michael

--

E-Mail: Mine is an /at/ gmx /dot/ de address.