Please help me understand what this function is checking and returning
Code:int isPower2 (int myInt) { return !(myInt>>31) & !!myInt & !(myInt & (myInt+(~1+1))); }
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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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 */
Fact - Beethoven wrote his first symphony in C
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
Last edited by Click_here; 10-03-2012 at 12:00 AM.
Fact - Beethoven wrote his first symphony in C
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.
The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss
Last edited by Click_here; 10-03-2012 at 12:24 AM.
Fact - Beethoven wrote his first symphony in C
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.