Another C Question

cse-icons

Jan 10 2005, 12:01 PM

Hi Friends,

Here is another interesting C Problem.
The problem is to find whether an integer is a power of 2 or not.
This must be done in a single C statement.
I tried a little but have not figured it out as yet.

I have been thinking on the following lines:

I suppose it has something to do with bit manipulation coz.. all integers that are power of 2 will have only single 1 in binary form, we need to be able to count if it has only single one..

Is there ny way???

Thanx.

osknockout

Jan 10 2005, 10:16 PM

So easy.

#include <cmath>
take a log of base 2 //don't remember the function, look it up on google
and take an integer test.

That should do it

cse-icons

Jan 11 2005, 08:56 AM

QUOTE(osknockout @ Jan 10 2005, 10:16 PM)

So easy.

#include <cmath>
take a log of base 2 //don't remember the function, look it up on google
and take an integer test.

That should do it

Thanks. that is a good idea...
i'll check it out...
btw keep posted if u get an idea on how to do it without using built-in functions.

osknockout

Jan 11 2005, 10:24 PM

that's not hard either

Do a repeat x <= 1
{
number / 2;
x -= 1;
}

if x==1, then it's a power of two.

If you want optimization, well... specify.

cse-icons

Jan 13 2005, 06:10 AM

hi osknockout,

That is a simple solution any one wud think of as first option...
but the condition in the question is not satisfied here. i.e., "it shoud be determined in a single C Statement"

so what i mean is some other solution in a single C Statement which does not use built in function...
the solution u have give has more than that....

Regards.

osknockout

Jan 14 2005, 10:35 PM

Right, sorry, I'll post if I ever find out...

So the solution set is:
00000010
00000100
00001000
00010000
00100000
01000000
10000000
ad infinitum

yomi

Jan 22 2005, 05:31 AM

I think this is more easy:

#define IS_2_POWER(X) (X==(~X)+1)

osknockout

Jan 22 2005, 12:45 PM

QUOTE

#define IS_2_POWER(X) (X==(~X)+1)

Nice idea but...

00000010 = 2
11111101 = ~2
11111110 = ~2 + 1

x==(~X)+1?
don't think so.

Good attempt though

I've GOT IT! (Thanks yomi)

CODE

#define IS_POWER_2(X) (!(2 mod x))
(1 >= 2 mod x + 4 mod x + 8 mod x + 16 mod x + 32 mod x + 64 mod x
+ 128 mod x) /*adjust number of 2^x digits as necessary*/

Ok, I'll work on a more optimized formula for right now...

yomi

Jan 23 2005, 03:41 PM

oh, i made a mistake , think about this:
x==((~x)+1)|x

I am not very sure. But sure there is a simular way to achieve this operation with high performance.

QUOTE(osknockout @ Jan 22 2005, 12:45 PM)

Nice idea but...

00000010 = 2
11111101 = ~2
11111110 = ~2 + 1

x==(~X)+1?
don't think so.

Good attempt though

I've GOT IT! (Thanks yomi)

CODE

#define IS_POWER_2(X) (!(2 mod x))
(1 >= 2 mod x + 4 mod x + 8 mod x + 16 mod x + 32 mod x + 64 mod x
+ 128 mod x) /*adjust number of 2^x digits as necessary*/

Ok, I'll work on a more optimized formula for right now...

osknockout

Jan 23 2005, 06:29 PM

QUOTE

oh, i made a mistake , think about this:
x==((~x)+1)|x

Hmm...

00000010 x
11111101 ~x
11111110 (~x)+1
11111110 ((~x)+1)|x

00000010 == 11111110?

I'll think about that formula again...

Latest Entries

yomi

Jan 26 2005, 04:35 AM

-x, pls note,
00000100 x
11111100 -x

-x is (~x)+1, they are equal.
-x is not simply change the fist bit.

Sure I am not guessing, I have point out I have given the CORRECT one.

QUOTE(osknockout @ Jan 25 2005, 11:02 PM)

Hmm....

00000100 x
10000100 -x //Randall Hyde, art of assembly, signed numbers
01111011 ~(-x)
01111100 ~(-X)+1

01111100==00000100? Yomi, stop guessing

I think that works for 2 though.

osknockout

Jan 25 2005, 11:02 PM

QUOTE

Now I can give the correct one:

X==~(-X)+1

Hmm....

00000100 x
10000100 -x //Randall Hyde, art of assembly, signed numbers
01111011 ~(-x)
01111100 ~(-X)+1

01111100==00000100? Yomi, stop guessing

I think that works for 2 though.

ADD REPLY / Got an Opinion!	a humble request :-)	RAPID SEARCH!	Free Hosting	[X]
Express your Opinions, Thoughts or Contribute your information that might help someone here. Ask your Doubts & Queries to get answers.. "Together, We enlight each other!"	Register FREE for AD-FREE forum, Create your own topics, Ask Questions, track topics, setup subscriptions & notifications and Get a Free Website w/ Email and FTP.		500MB Space No Ads, CPanel, FTP, PHP, MySQL, EMails - 100% FREE