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

**Alexei A. Frounze** · Nov 15 '05, 01:49 AM

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

"William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
news:Pine.GSO.4 .58.05081415362 20.2309@cpu02.s tudent.cs.uwate rloo.ca...[color=blue]
> 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?[/color]

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** · Nov 15 '05, 01:49 AM

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

"Alexei A. Frounze" <alexfru@chat.r u> writes:[color=blue]
> "William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
> news:Pine.GSO.4 .58.05081415362 20.2309@cpu02.s tudent.cs.uwate rloo.ca...[color=green]
>> 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?[/color]
>
> Wrong group.[/color]

How is this the wrong group?
[color=blue]
> A hint anyway: think of binary representation of powers of 2 and not powers
> of 2. You'll see the answer. I stop here.[/color]

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_Keit h) kst-u@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.

**William** · Nov 15 '05, 01:49 AM

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

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:
[color=blue]
> "Alexei A. Frounze" <alexfru@chat.r u> writes:[color=green]
> > "William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
> > news:Pine.GSO.4 .58.05081415362 20.2309@cpu02.s tudent.cs.uwate rloo.ca...[color=darkred]
> >> 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?[/color]
> >
> > Wrong group.[/color]
>
> How is this the wrong group?
>[color=green]
> > A hint anyway: think of binary representation of powers of 2 and not powers
> > of 2. You'll see the answer. I stop here.[/color]
>
> 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_Keit h) kst-u@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.
>[/color]

**Alexei A. Frounze** · Nov 15 '05, 01:49 AM

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

"William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
news:Pine.GSO.4 .58.05081416354 30.2309@cpu02.s tudent.cs.uwate rloo.ca...[color=blue]
> let x = 1000 (8, a power of 2); x-1 = 111
> then
> x & (x-1) = 1111[/color]

So, you don't even know how the operator & works. A point for you.
[color=blue]
> !(x & (x-1)) = 0000
> how does (1000 && 0000) == 0?[/color]

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

**Alexei A. Frounze** · Nov 15 '05, 01:49 AM

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

"Keith Thompson" <kst-u@mib.org> wrote in message
news:lnek8ws1za .fsf@nuthaus.mi b.org...[color=blue]
> "Alexei A. Frounze" <alexfru@chat.r u> writes:[color=green]
> > "William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
> > news:Pine.GSO.4 .58.05081415362 20.2309@cpu02.s tudent.cs.uwate rloo.ca...[color=darkred]
> >> 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?[/color]
> >
> > Wrong group.[/color]
>
> How is this the wrong group?[/color]

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?
[color=blue][color=green]
> > A hint anyway: think of binary representation of powers of 2 and not[/color][/color]
powers[color=blue][color=green]
> > of 2. You'll see the answer. I stop here.[/color]
>
> 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.[/color]

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

**akarl** · Nov 15 '05, 01:50 AM

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

Alexei A. Frounze wrote:[color=blue]
> "Keith Thompson" <kst-u@mib.org> wrote in message
> news:lnek8ws1za .fsf@nuthaus.mi b.org...
>[color=green]
>>"Alexei A. Frounze" <alexfru@chat.r u> writes:
>>[color=darkred]
>>>"William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
>>>news:Pine.GS O.4.58.05081415 36220.2309@cpu0 2.student.cs.uw aterloo.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.[/color]
>>
>>How is this the wrong group?[/color]
>
> 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?[/color]

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** · Nov 15 '05, 01:50 AM

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

akarl <fusionfive@com hem.se> writes:[color=blue]
> Alexei A. Frounze wrote:[color=green]
>> "Keith Thompson" <kst-u@mib.org> wrote in message
>> news:lnek8ws1za .fsf@nuthaus.mi b.org...
>>[color=darkred]
>>>"Alexei A. Frounze" <alexfru@chat.r u> writes:
>>>
>>>>"William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
>>>>news:Pine.G SO.4.58.0508141 536220.2309@cpu 02.student.cs.u waterloo.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?[/color]
>> 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?[/color]
>
> 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.[/color]

The C standard specifies that integers are represented in binary.

--
Keith Thompson (The_Other_Keit h) kst-u@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.

**William** · Nov 15 '05, 01:50 AM

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

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:
[color=blue]
> "William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
> news:Pine.GSO.4 .58.05081416354 30.2309@cpu02.s tudent.cs.uwate rloo.ca...[color=green]
> > let x = 1000 (8, a power of 2); x-1 = 111
> > then
> > x & (x-1) = 1111[/color]
>
> So, you don't even know how the operator & works. A point for you.
>[color=green]
> > !(x & (x-1)) = 0000
> > how does (1000 && 0000) == 0?[/color]
>
> 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
>
>
>[/color]

**Martin Ambuhl** · Nov 15 '05, 01:50 AM

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

Keith Thompson wrote:[color=blue]
> "Alexei A. Frounze" <alexfru@chat.r u> writes:
>[color=green]
>>"William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
>>news:Pine.GSO .4.58.050814153 6220.2309@cpu02 .student.cs.uwa terloo.ca...
>>[color=darkred]
>>>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?[/color]
>>
>>Wrong group.[/color]
>
>
> How is this the wrong group?[/color]

Because your question has nothing to do with C. It is about the
behavior of binary numbers.[color=blue][color=green]
>>A hint anyway: think of binary representation of powers of 2 and not powers
>>of 2. You'll see the answer. I stop here.[/color]
>
>
> 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.[/color]

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** · Nov 15 '05, 01:50 AM

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

Martin Ambuhl <mambuhl@earthl ink.net> writes:[color=blue]
> Keith Thompson wrote:[color=green]
>> "Alexei A. Frounze" <alexfru@chat.r u> writes:
>>[color=darkred]
>>>"William" <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
>>>news:Pine.GS O.4.58.05081415 36220.2309@cpu0 2.student.cs.uw aterloo.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.[/color]
>> How is this the wrong group?[/color]
>
> Because your question has nothing to do with C. It is about the
> behavior of binary numbers.[/color]

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).
[color=blue][color=green][color=darkred]
>>>A hint anyway: think of binary representation of powers of 2 and not powers
>>>of 2. You'll see the answer. I stop here.[/color]
>> 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.[/color]
>
> Yes, it makes perfect sense.[/color]
[snip][color=blue]
> So you were indeed to think of the binary representation of
> "powers of 2"
> and
> "not powers of 2."[/color]

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.
[color=blue]
> 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.[/color]

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

--
Keith Thompson (The_Other_Keit h) kst-u@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.

**Christian Bau** · Nov 15 '05, 01:50 AM

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

In article
<Pine.GSO.4.58. 0508141536220.2 309@cpu02.stude nt.cs.uwaterloo .ca>,
William <wh2leung@stude nt.cs.uwaterloo .ca> wrote:
[color=blue]
> 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?[/color]

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.

**akarl** · Nov 15 '05, 01:50 AM

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

Keith Thompson wrote:[color=blue]
> akarl <fusionfive@com hem.se> writes:
>[color=green]
>>Alexei A. Frounze wrote:
>>[color=darkred]
>>>"Keith Thompson" <kst-u@mib.org> wrote in message
>>>news:lnek8ws 1za.fsf@nuthaus .mib.org...
>>>
>>>
>>>>"Alexei A. Frounze" <alexfru@chat.r u> writes:
>>>>
>>>>
>>>>>"William " <wh2leung@stude nt.cs.uwaterloo .ca> wrote in message
>>>>>news:Pine. GSO.4.58.050814 1536220.2309@cp u02.student.cs. uwaterloo.ca...
>>>>>
>>>>>
>>>>>>Origina l 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?[/color]
>>
>>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.[/color]
>
>
> The C standard specifies that integers are represented in binary.[/color]

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

August

**shappen@gmail.com** · Nov 15 '05, 01:50 AM

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

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** · Nov 15 '05, 01:50 AM

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

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:[color=blue]
> 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?[/color]

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.

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

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

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment