Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > test whether a number is a power of 2

Reply
Thread Tools

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.
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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++




 
Reply With Quote
 
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"
 
Reply With Quote
 
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


 
Reply With Quote
 
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.
 
Reply With Quote
 
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)
 
Reply With Quote
 
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)
 
Reply With Quote
 
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)
 
Reply With Quote
 
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Continuous beeps on my computer.. whether power on or off alkon Computer Information 2 07-21-2007 04:16 AM
to test whether a number is a power of 2 ravi C Programming 31 07-13-2007 04:27 PM
The while loop for calculating a power of a number less than another number? Erik the Red Ruby 4 07-29-2005 08:28 PM
how to find a number whether its a power of 2 or not MJ C Programming 11 04-29-2005 10:44 PM
test test test test test test test Computer Support 2 07-02-2003 06:02 PM



Advertisments