Fun with Bit Operations | LeetCode

What does the following function mystery() do?

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

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:

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

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

Read full article from Fun with Bit Operations | LeetCode