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

[William]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Thanks.

 

[Alexei A. Frounze]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Wrong group.
A hint anyway: think of binary representation of powers of 2 and not powers
of 2. You'll see the answer. I stop here.

Alex

 

[Keith Thompson]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Wrong group.

How is this the wrong group?

A hint anyway: think of binary representation of powers of 2 and not powers
of 2. You'll see the answer. I stop here.

It's hard to understand what you mean by that. I *think* you mean

Think of
binary representation of powers of 2
and not
powers of 2.

but when I first read it I thought you were talking about "powers of 2
and not powers of 2", which doesn't make any sense.

 

[William]

let x = 1000 (8, a power of 2); x-1 = 111
then
x & (x-1) = 1111
!(x & (x-1)) = 0000
how does (1000 && 0000) == 0?

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Wrong group.

How is this the wrong group?

A hint anyway: think of binary representation of powers of 2 and not powers
of 2. You'll see the answer. I stop here.

It's hard to understand what you mean by that. I *think* you mean

Think of
binary representation of powers of 2
and not
powers of 2.

but when I first read it I thought you were talking about "powers of 2
and not powers of 2", which doesn't make any sense.

 

[Alexei A. Frounze]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Wrong group.

How is this the wrong group?

The Q was about the algo. But the group is about the language. Isn't this
what you want here, i.e. get the trolls and irrelevant Qs out?

It's hard to understand what you mean by that. I *think* you mean

Think of
binary representation of powers of 2
and not
powers of 2.

but when I first read it I thought you were talking about "powers of 2
and not powers of 2", which doesn't make any sense.

Oh come on, you know what I meant. And it wasn't obviously some C operators
like &,&& and !. If I had wanted to throw some C in, I'd have done that.

Alex

 

[Alexei A. Frounze]

let x = 1000 (8, a power of 2); x-1 = 111
then
x & (x-1) = 1111

So, you don't even know how the operator & works. A point for you.

!(x & (x-1)) = 0000
how does (1000 && 0000) == 0?

And then you told yourself, there was x & (x-1), but not x && (x-1). You've
got another point! How about reading a book on C or looking into some C
reference?

Alex

 

[akarl]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Wrong group.

How is this the wrong group?

The Q was about the algo. But the group is about the language. Isn't this
what you want here, i.e. get the trolls and irrelevant Qs out?

The question was how to implement a solution in C and it can be done in
standard C without any non-standard libraries, so it's on topic.
However, you may argue that it's off topic since the solution depends on
the binary representation of integers.

August

 

[Keith Thompson]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Wrong group.

How is this the wrong group?

The Q was about the algo. But the group is about the language. Isn't
this
what you want here, i.e. get the trolls and irrelevant Qs out?

The question was how to implement a solution in C and it can be done
in standard C without any non-standard libraries, so it's on topic.
However, you may argue that it's off topic since the solution depends
on the binary representation of integers.

The C standard specifies that integers are represented in binary.

 

[William]

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?

Thanks.

 

[Martin Ambuhl]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Wrong group.

How is this the wrong group?

Because your question has nothing to do with C. It is about the
behavior of binary numbers.

It's hard to understand what you mean by that. I *think* you mean

Think of
binary representation of powers of 2
and not
powers of 2.

but when I first read it I thought you were talking about "powers of 2
and not powers of 2", which doesn't make any sense.

Yes, it makes perfect sense. Since you need the push, I'll fill it out
for you.
Think about the representation of a power of 2:
x: 0...000...010......0
and
x-1: 0...000..001......1

x & (x-1) is then
0...000..000......0 == 0

Think about the representation of "not a power of 2" (and not zero),
there will be at least two bits set in such a number:
x: 0...010...010......0
and
x-1: 0...010..001......1

x & (x-1) is then
0...010..000......0 != 0

Note that all ones in a "not a power of 2" except the rightmost one
remains in x & (x-1).

So you were indeed to think of the binary representation of
"powers of 2"
and
"not powers of 2."

Before you label things as not making any sense, consider that it might
be that you have a cognitive shortcoming and that the thing does make
sense to those who are willing to think about it.

 

[Keith Thompson]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Wrong group.

How is this the wrong group?

Because your question has nothing to do with C. It is about the
behavior of binary numbers.

It wasn't my question. In any case, it's about the behavior of
certain C operators (which happen to operate on binary numbers, which
C requires).

It's hard to understand what you mean by that. I *think* you mean
Think of
binary representation of powers of 2
and not
powers of 2.
but when I first read it I thought you were talking about "powers of
2
and not powers of 2", which doesn't make any sense.

Yes, it makes perfect sense. [snip]
So you were indeed to think of the binary representation of
"powers of 2"
and
"not powers of 2."

Ok. If he had written "non powers of 2", it would have been easier to
understand. My problem was with the poor wording of the statement,
not with the underlying concepts.

Before you label things as not making any sense, consider that it
might be that you have a cognitive shortcoming and that the thing does
make sense to those who are willing to think about it.

<sarcasm>Yeah, that must be it.</sarcasm>

 

[akarl]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Wrong group.

How is this the wrong group?

The Q was about the algo. But the group is about the language. Isn't
this
what you want here, i.e. get the trolls and irrelevant Qs out?

The question was how to implement a solution in C and it can be done
in standard C without any non-standard libraries, so it's on topic.
However, you may argue that it's off topic since the solution depends
on the binary representation of integers.

The C standard specifies that integers are represented in binary.

OK, in that case there is no question about it.

August

 

[Christian Bau]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

Write down exactly what happens in the expression when x is a power of
two, then write down exactly what happens when x is not a power of two,
then it is quite obvious.

 

[shappen]

I think this is the right answer:
if(test&&(test&(test-1))==0)
printf("The number is the power of 2!\n");
else
printf("The number is not the power of 2!\n");

 

[Michael Mair]

Please do not top-post. Place your answer below or interspersed
with the text you are replying to.

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

 

[Christian Kandeler]

Original question:
"Give a one-line C expression to test whether a number
is a power of 2. [No loops allowed - it's a simple test.]"

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

My question:
Why does this expression work?

It doesn't. You have to drop the negation.


Christian

 

[Anonymous 7843]

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?

Thanks.

Yes, mostly. It seems to fail on the edge cases of 0 and the most
negative int, e.g. -INT_MAX-1 or -2147483648 on a 2's complement
machine with sizeof(int) == 4.

However, the type of x was not stated and I assumed int. If one
assumes it is an unsigned int then there is no problem with
-INT_MAX-1.

x==0 is still wrong, plus it's somewhat counter-intuitive for the
expression to return false for "yes, it's a power of two" A better
expression that fixes these two issues might be:

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

More disturbing of course is in many mathematical contexts in
which powers of two are interesting, it's common for the range of
the numbers involved to be larger than what will fit into an int.
The bitwise trickery won't work on float or double, obviously.

 

[caleb.vandyke]

I don't think that works. There shouldn't be the ! in the expression
and this will return true is x = 1, which obviously isn't correct.

 

[Keith Thompson]

I don't think that works. There shouldn't be the ! in the expression
and this will return true is x = 1, which obviously isn't correct.

You don't think *what* works?

Don't assume your readers have easy access to the article to which
you're replying. You can provide proper quotations and attributions
through groups.google.com; search this newsgroup for advice (which has
been offered hundreds of times.

 

[Clark S. Cox III]

I don't think that works. There shouldn't be the ! in the expression
and this will return true is x = 1, which obviously isn't correct.

2**0 == 1