Velocity Reviews > test whether a number is a power of 2

# test whether a number is a power of 2

Matt
Guest
Posts: n/a

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

Joona I Palaste
Guest
Posts: n/a

 09-28-2003
Matt <(E-Mail Removed)> 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 ((E-Mail Removed)) ---------------------------\
| 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

Ivan Vecerina
Guest
Posts: n/a

 09-28-2003
"Matt" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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++

Keith Thompson
Guest
Posts: n/a

 09-28-2003
http://www.velocityreviews.com/forums/(E-Mail Removed) (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) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"

jacob navia
Guest
Posts: n/a

 09-28-2003

> 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

Aishwarya
Guest
Posts: n/a

 09-29-2003
Joona I Palaste <(E-Mail Removed)> wrote in message news:<bl79og\$2tv\$(E-Mail Removed)>...
> Matt <(E-Mail Removed)> 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.

Eric Sosman
Guest
Posts: n/a

 09-29-2003
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.)

--
(E-Mail Removed)

Dan Pop
Guest
Posts: n/a

 09-29-2003
In <(E-Mail Removed)> Keith Thompson <(E-Mail Removed)> writes:

>(E-Mail Removed) (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: (E-Mail Removed)

Dan Pop
Guest
Posts: n/a

 09-29-2003
In <(E-Mail Removed)> (E-Mail Removed) (Aishwarya) writes:

>Joona I Palaste <(E-Mail Removed)> wrote in message news:<bl79og\$2tv\$(E-Mail Removed)>...
>> Matt <(E-Mail Removed)> 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: (E-Mail Removed)

Jirka Klaue
Guest
Posts: n/a

 09-29-2003
Aishwarya wrote:
> Joona I Palaste <(E-Mail Removed)> wrote in message news:<bl79og\$2tv\$(E-Mail Removed)>...

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