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
Please help me understand what this function is checking and returning
Code:int isPower2 (int myInt) {
return !(myInt>>31) & !!myInt & !(myInt & (myInt+(~1+1)));
}
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.
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 */
I'll explain that last part:
So your function is returning -> if not 0 and not negitive and only one bit is set, the integer is a power of 2Code:!(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
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.
Allowed operators: = & | ^ ~ >> ! (OP allowed +)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.
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).
form what i see its just bit manipulation tricks.. but with the double !! which i think cancels out in this case...
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.