469,609 Members | 1,652 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,609 developers. It's quick & easy.

test whether a number is a power of 2

Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.
Nov 13 '05 #1
17 21347
Matt <jr********@hotmail.com> scribbled the following:
Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


((((x&&!(x&(x-!!x)))+x)-x)^x)^x

What do I win?

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"Remember: There are only three kinds of people - those who can count and those
who can't."
- Vampyra
Nov 13 '05 #2
"Matt" <jr********@hotmail.com> wrote in message
news:ba**************************@posting.google.c om...
Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


isPow2 = x && !( (x-1) & x );

See http://www.caam.rice.edu/~dougm/twiddle/
for some related info.

hth
--
http://ivan.vecerina.com
http://www.brainbench.com <> Brainbench MVP for C++


Nov 13 '05 #3
jr********@hotmail.com (Matt) writes:
Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


We're not here to do your homework for you.

--
Keith Thompson (The_Other_Keith) ks*@cts.com <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"
Nov 13 '05 #4
isPow2 = x && !( (x-1) & x );


Algorithm:
If x is a power of two, it doesn't have any bits in common with x-1, since it
consists of a single bit on. Any positive power of two is a single bit, using
binary integer representation.

This means that we test if x-1 and x doesn't share bits with the and operator.

Of course, if x is zero (not a power of two) this doesn't hold, so we add an
explicit test for zero with xx && expression.

Negative powers of two (0.5, 0.25, 0.125, etc) could share this same property
in a suitable fraction representation. 0.5 would be 0.1, 0.250 would be 0.01,
0.125 would be 0.001 etc.

jacob
Nov 13 '05 #5
Joona I Palaste <pa*****@cc.helsinki.fi> wrote in message news:<bl**********@oravannahka.helsinki.fi>...
Matt <jr********@hotmail.com> scribbled the following:
Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


((((x&&!(x&(x-!!x)))+x)-x)^x)^x

What do I win?

hi Joona,

i know this works because i just tested it .. but help me understand
the algoritm please ..

Thanks and Regards
A.
Nov 13 '05 #6
Matt wrote:

Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


true_or_false = a_number > 0;

(For example, 3.14159 ~= 2 ** 1.65149.)

--
Er*********@sun.com
Nov 13 '05 #7
In <64*************************@posting.google.com> ai*******@sapient.com (Aishwarya) writes:
Joona I Palaste <pa*****@cc.helsinki.fi> wrote in message news:<bl**********@oravannahka.helsinki.fi>...
Matt <jr********@hotmail.com> scribbled the following:
> Give a one-line C expression to test whether a number is a power of 2.
> No loops allowed.


((((x&&!(x&(x-!!x)))+x)-x)^x)^x


i know this works because i just tested it .. but help me understand
the algoritm please ..


Had you engaged your brain, you'd have easily noticed that one ^x cancels
the other and that -x cancels the +x, so you're left with

x&&!(x&(x-!!x))

Now, !!x is an obfuscated way of writing 1, when you know that x cannot
be zero (it was already tested), so, we're left with:

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

The tricky bit is x&(x-1) which actually clears the least significant
bit that happens to be set. If the original number was a power of two,
it had only one bit set, so the result of x&(x-1) must be zero in such
cases.

The rest should be obvious.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 13 '05 #8
In <lz************@cts.com> Keith Thompson <ks*@cts.com> writes:
jr********@hotmail.com (Matt) writes:
Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


We're not here to do your homework for you.


OTOH, the solution is far too tricky for a homework assignment. It
requires a bit of knowledge that has precious little to do with C
programming.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 13 '05 #9
Aishwarya wrote:
Joona I Palaste <pa*****@cc.helsinki.fi> wrote in message news:<bl**********@oravannahka.helsinki.fi>...

....
((((x&&!(x&(x-!!x)))+x)-x)^x)^x


i know this works because i just tested it .. but help me understand
the algoritm please ..


+x -x does nothing, ^x ^x does nothing.

remains:
x && !(x & (x - !!x))

!!x ist alway 1, because x can't be 0 at this point.

remains:
x && !(x & (x - 1))

Jirka

Nov 13 '05 #10
On 9/28/2003 1:21 PM, Matt wrote:
Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


if (!(x%2)) {
puts("x is a power of 2");
}

Regards,

Ed.

Nov 13 '05 #11
Ed Morton wrote:
On 9/28/2003 1:21 PM, Matt wrote:
Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


if (!(x%2)) {
puts("x is a power of 2");
}


Are you implying that 42 is a power of 2 and 43 is not?
BTW: It's a three-liner and no C expression at all. ;-)

Jirka

Nov 13 '05 #12


On 9/29/2003 10:44 AM, Jirka Klaue wrote:
Ed Morton wrote:
On 9/28/2003 1:21 PM, Matt wrote:

Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


if (!(x%2)) {
puts("x is a power of 2");
}

Are you implying that 42 is a power of 2 and 43 is not?
BTW: It's a three-liner and no C expression at all. ;-)

Jirka


I had intended !(x%2) to be the expression, the rest was demonstrating using it.
I'll go back to sleep now.... wake me next time you want to know if a number is
a multiple of 2 rather than a power of 2. Sorry 'bout that.

Ed.

Nov 13 '05 #13
Joona I Palaste <pa*****@cc.helsinki.fi> wrote:

((((x&&!(x&(x-!!x)))+x)-x)^x)^x

What do I win?


Nothing. What if x is negative? What if it's not an integer? What if
the original poster provided a complete specification of the problem? :-)

-Larry Jones

I kind of resent the manufacturer's implicit assumption
that this would amuse me. -- Calvin
Nov 13 '05 #14
Eric Sosman <Er*********@sun.com> wrote in message news:<3F***************@sun.com>...
Matt wrote:

Give a one-line C expression to test whether a number is a power of 2.
No loops allowed.


true_or_false = a_number > 0;
(For example, 3.14159 ~= 2 ** 1.65149.)


Why stop there? C99 has complex types. ;)

--
Peter
Nov 13 '05 #15
Ed Morton wrote:
On 9/28/2003 1:21 PM, Matt wrote:
Give a one-line C expression to test whether a number is a
power of 2. No loops allowed.


if (!(x%2)) {
puts("x is a power of 2");
}

^^^^^^^^^^^^
even

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 13 '05 #16
Da*****@cern.ch (Dan Pop) wrote in message news:<bl**********@sunnews.cern.ch>...
...
Now, !!x is an obfuscated way of writing 1, when you know that x cannot
be zero (it was already tested)


this is exactly what i got stuck in :-) i should have guessed it ...
thanks for the explanation though :-)
Nov 13 '05 #17
"jacob navia" <ja*********@jacob.remcomp.fr> wrote in message news:<bl**********@news-reader5.wanadoo.fr>...
isPow2 = x && !( (x-1) & x );


Algorithm:
If x is a power of two, it doesn't have any bits in common with x-1, since it
consists of a single bit on. Any positive power of two is a single bit, using
binary integer representation.

This means that we test if x-1 and x doesn't share bits with the and operator.

Of course, if x is zero (not a power of two) this doesn't hold, so we add an
explicit test for zero with xx && expression.


Few Mathematicians say any positive integer raised to the power minus
infinity is 0. That is,
n (pow) (-infinity) = 0

IOW, 2 (pow) 3 = 8, 2 (pow) 2 = 4, 2 (pow) 1 = 2, 2 (pow) 0 = 1,
and, 2 (pow) (-infinity) = 0.

Because of this religious reason, I would just write my macro as
(without 0 check)
#define ISPOWOF2( n ) ( ! ( n & (n-1) ) )

But, someone here in CLC told me that the above macro won't work all
the time. I know, it won't work for float; I know the necessity of
additional paranthesis for n. But, I couldn't see any other reasons.
Anybody have any good comments? TIA

---
"Silence is the only right answer for many wrong questions" --
G.K.Moopanaar, Indian Politician
http://guideme.itgo.com/atozofc/ - "A to Z of C" Project
Email: rrjanbiah-at-Y!com
Nov 13 '05 #18

This discussion thread is closed

Replies have been disabled for this discussion.

By using this site, you agree to our Privacy Policy and Terms of Use.