What does the following function mystery() do?

1 2 3 |
bool mystery(unsigned int x) { return !(x & (x-1)); } |

Interviewer loves to ask bit operations questions, because it can be tricky and highly deceptive.

Here is the hint: Assume the bits of x is “101000”, then x-1 is “100111”. The transformation from x » x-1 is easy, the rightmost bit that is ‘1’ will be changed to ‘0’, and all the ‘0’ bits to the right will be changed to ‘1’. Therefore, when you do an & operation between them, the rightmost ‘1’ bit will turn to ‘0’.

An integer that is a power of two has exactly one bit that is ‘1’. Therefore, this function returns whether an integer is a power of two.

The fun does not stop here. Look out for my next post to discover more fun with bit operations!

EDIT: (A small bug fix)

Sharp readers might find that passing 0 into the function returns true (while 0 is not a power of two). In order to remedy this, use:

1 |
return x && !(x & (x-1)); |

If you are able to point this out during the interview, I’m sure the interviewer will be very impressed.

Fun with Bit Operations,
I think this post is wrong.

I think the mystery function tests if the number is of the form 2^n – 1 .

Can anyone please confirm ?

-1what is n in your comments? An iteration?

-1no, the post is fine

+1Pingback: Amazon interview preparation | What I learn, I blog !

Nice post.

Java version:

public static boolean checkPowerOfTwo(int num)

{

//excluse 0 and negative numbers

//especially 0. 0 & with any number will be 0.

if (num<=0)

{

return false;

}

if ((num & (num-1)) == 0)

{

return true;

}

return false;

}

0Why not just “return num & (num – 1) == 0”

+1Pingback: LeetCode | Technical interview solutions

Pingback: Map Manipulation: n & (n-1) - This is a ghost in the shellThis is a ghost in the shell