Another C Question

[cse-icons 0]

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 0]

So easy. #include <cmath>take a log of base 2 //don't remember the function, look it up on googleand take an integer test.That should do it

[cse-icons 0]

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

<{POST_SNAPBACK}>

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 0]

that's not hard either :rolleyes: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 0]

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 0]

Right, sorry, I'll post if I ever find out...So the solution set is:00000010000001000000100000010000001000000100000010000000ad infinitum

[yomi 0]

I think this is more easy:#define IS_2_POWER(X) (X==(~X)+1)

[osknockout 0]

#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)

#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 0]

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.

 

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)

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

42415[/snapback]

[osknockout 0]

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

[yomi 0]

Now I can give the correct one:

 

X==~(-X)+1

 

 

Hmm...

 

00000010 x

11111101 ~x

11111110 (~x)+1

11111110 ((~x)+1)|x

 

00000010 == 11111110?

 

I'll think about that formula again...

42694[/snapback]

[osknockout 0]

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.

[yomi 0]

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

 

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.

43345[/snapback]