473,573 Members | 2,719 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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 21576
Matt <jr********@hot mail.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.hel sinki.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********@hot mail.com> wrote in message
news:ba******** *************** ***@posting.goo gle.com...
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********@hotm ail.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_Keit h) 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.hel sinki.fi> wrote in message news:<bl******* ***@oravannahka .helsinki.fi>.. .
Matt <jr********@hot mail.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************ *************@p osting.google.c om> ai*******@sapie nt.com (Aishwarya) writes:
Joona I Palaste <pa*****@cc.hel sinki.fi> wrote in message news:<bl******* ***@oravannahka .helsinki.fi>.. .
Matt <jr********@hot mail.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********@hot mail.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.hel sinki.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

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
8443
by: MJ | last post by:
Hi I have question about the C. I have a number X which is power of two X = 2 power n I need to find it using a Single C statement whether its a power of 2 or not I know that a number with power of 2 will have only one single bit as 1 and rest of the bit as 0. To check the bit I need to go through all the bits ones and check for the...
10
4919
by: David T. Ashley | last post by:
What is the most economical test in 'C' for "integer is a power of 2"? For example, something better than: void is_2_pow(int arg) { return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and so on */ ); }
20
10707
by: ravi | last post by:
Give a one-line C expression to test whether a number is a power of 2.
0
7705
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
8206
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
0
8077
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6426
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5601
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
3734
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
2224
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1316
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
1044
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.