Please help me understand what this function is checking and returning

Code:`int isPower2 (int myInt) {`

return !(myInt>>31) & !!myInt & !(myInt & (myInt+(~1+1)));

}

Printable View

- 10-02-2012xbossFunction return
Please help me understand what this function is checking and returning

Code:`int isPower2 (int myInt) {`

return !(myInt>>31) & !!myInt & !(myInt & (myInt+(~1+1)));

}

- 10-02-2012laserlight
The function name may give a clue. Test it with various input and see what you get. Then examine the code and see how it tallies with your observations.

- 10-02-2012Click_heretypo
I'm assuming you have 32 bit integers - My guess is:

Code:`return !(myInt>>31) & /* Is not negative */`

!!myInt & /* Is not zero */

!(myInt & (myInt+(~1+1))); /* Doesn't have more than 1 bit set */

- 10-02-2012poornaMoksha
- 10-02-2012Click_here
I'll explain that last part:

Code:`!(myInt & (myInt+(~1+1))`

~1+1 is the 2's complement of 1

This is equal to -1

for an unsigned int v (that is not 0)

v & (v - 1)

will clear the least significant bit set

consider this 4-bit example

let v = 0101

v-1 = 0100

& this with v = 0100

now consider v = 1100

v-1 = 1011

& this with v = 1000

For something to be a power of 2, only 1 bit is going to be set ->

So if you clear the LSB of the number (and it is the only bit set), you will end up with 0

and !0 = 1

- 10-02-2012oogabooga
This would normally be done on unsigned integers and is usually coded like this:

v && !(v & (v - 1)); // From "Bit Twiddling Hacks" website

But the OP's code is obviously trying to do it with restrictions.

Which reminds me of the similar problem a week or two ago. May as well post my solution to that here. Still, there's got to be something simpler.

Code:`#include <stdio.h>`

#include <limits.h>

int isitGreater(signed char x, signed char y) {

x = x ^ y;

y = (y ^ x ^ SCHAR_MIN) & (y ^ SCHAR_MAX);

x = x | x >> 4;

x = x | x >> 2;

x = x | x >> 1;

x = x & (SCHAR_MIN | ~(x >> 1));

return !!(x & y);

}

int main(void) {

signed char x = SCHAR_MIN, y = SCHAR_MIN;

do {

do {

if ((x > y) != isitGreater(x, y))

printf("Error: %d %d\n", (int)x, (int)y);

}while (y++ < SCHAR_MAX);

}while (x++ < SCHAR_MAX);

return 0;

}

Also allowed: return, parentheses, constants

Not allowed: local vars, casts, control statements other than return. - 10-03-2012Click_here
- 10-03-2012xboss
That's right Click_here. Suppose my input to this function is

int p = pow(2,n) -> where n is 1, 3, 5, 7, 9, 11, 13

and now I am calling the function below,

Code:`int s = isPower2 (p)`

int isPower2 (int myInt) {

return !(myInt>>31) & !!myInt & !(myInt & (myInt+(~1+1)));

}

What should I expect the function isPower2 is returning. What is going on within this function. Laserlight as you have mentioned I tested with various inputs and got result which was not convincing to at least me :( Let me share the result,

The returned result is listed below

1

1

1

1

1

1

1

1

0 all the way down

And if result of pow(2,n)

2

8

128

512

2048

8192

2147483647 all the way down

Let me describe the purpose of the program is to calculate Mersenne primes that are already lucky (lucky number --> 1, 3, 5, 7, 9, 11, 13). - 10-03-2012Nyah Check
form what i see its just bit manipulation tricks.. but with the double !! which i think cancels out in this case...

- 10-03-2012AndiPersti
- 10-03-2012xboss
Thanks for your reply and time AndiPesti. I know 1 is value for return true and 0 is false. I was trying to explain "laserlight" the o/p I am getting from function isPower2. I am not questioning on what function is returning but how the function decide if return is true or false based on the input I am throwing in? Above all, I must say thank you all for your precious time and effort reading and responding my thread.