By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,841 Members | 854 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,841 IT Pros & Developers. It's quick & easy.

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

P: n/a
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.
Nov 15 '05 #1
Share this Question
Share on Google+
20 Replies


P: n/a
"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca...
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
Nov 15 '05 #2

P: n/a
"Alexei A. Frounze" <al*****@chat.ru> writes:
"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca...
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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 15 '05 #3

P: n/a
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?


On Sun, 14 Aug 2005, Keith Thompson wrote:
"Alexei A. Frounze" <al*****@chat.ru> writes:
"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca...
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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Nov 15 '05 #4

P: n/a
"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca...
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
Nov 15 '05 #5

P: n/a
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org...
"Alexei A. Frounze" <al*****@chat.ru> writes:
"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca...
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?
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.


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
Nov 15 '05 #6

P: n/a
Alexei A. Frounze wrote:
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org...
"Alexei A. Frounze" <al*****@chat.ru> writes:
"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.stu dent.cs.uwaterloo.ca...

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
Nov 15 '05 #7

P: n/a
akarl <fu********@comhem.se> writes:
Alexei A. Frounze wrote:
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org...
"Alexei A. Frounze" <al*****@chat.ru> writes:

"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.st udent.cs.uwaterloo.ca...

>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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 15 '05 #8

P: n/a
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.
On Mon, 15 Aug 2005, Alexei A. Frounze wrote:
"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca...
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

Nov 15 '05 #9

P: n/a
Keith Thompson wrote:
"Alexei A. Frounze" <al*****@chat.ru> writes:
"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.stud ent.cs.uwaterloo.ca...
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.
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.


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.
Nov 15 '05 #10

P: n/a
Martin Ambuhl <ma*****@earthlink.net> writes:
Keith Thompson wrote:
"Alexei A. Frounze" <al*****@chat.ru> writes:
"William" <wh******@student.cs.uwaterloo.ca> wrote in message
news:Pi******************************@cpu02.stu dent.cs.uwaterloo.ca...

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).
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.


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>

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 15 '05 #11

P: n/a
In article
<Pi******************************@cpu02.student.cs .uwaterloo.ca>,
William <wh******@student.cs.uwaterloo.ca> wrote:
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.
Nov 15 '05 #12

P: n/a
Keith Thompson wrote:
akarl <fu********@comhem.se> writes:
Alexei A. Frounze wrote:
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org...
"Alexei A. Frounze" <al*****@chat.ru> writes:
>"William" <wh******@student.cs.uwaterloo.ca> wrote in message
>news:Pi******************************@cpu02.s tudent.cs.uwaterloo.ca...
>
>
>>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

Nov 15 '05 #13

P: n/a
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");

Nov 15 '05 #14

P: n/a
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.
Nov 15 '05 #15

P: n/a
William wrote:
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
Nov 15 '05 #16

P: n/a
In article <Pi******************************@cpu02.student.cs .uwaterloo.ca>,
William <wh******@student.cs.uwaterloo.ca> 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?

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.
Nov 15 '05 #17

P: n/a
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.

Nov 15 '05 #18

P: n/a
"ca***********@gmail.com" <ca***********@gmail.com> writes:
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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 15 '05 #19

P: n/a
On 2005-08-16 00:54:41 -0400, "ca***********@gmail.com"
<ca***********@gmail.com> said:
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

--
Clark S. Cox, III
cl*******@gmail.com

Nov 15 '05 #20

P: n/a

Clark S. Cox III wrote:
On 2005-08-16 00:54:41 -0400, "ca***********@gmail.com"
<ca***********@gmail.com> said:
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

--
Clark S. Cox, III
cl*******@gmail.com


Yep, that will teach me to post after my bedtime. Of course 1 is a
power of two; 2^0 = 1. Yikes, sorry about that.

Nov 15 '05 #21

This discussion thread is closed

Replies have been disabled for this discussion.