Fun with Bit Operations

What does the following function mystery() do?

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:

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

VN:F [1.9.22_1171]
Rating: 4.6/5 (16 votes cast)
Fun with Bit Operations, 4.6 out of 5 based on 16 ratings

9 thoughts on “Fun with Bit Operations

  1. Anurag Gupta

    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 ?

    VA:F [1.9.22_1171]
    -1
  2. Pingback: Amazon interview preparation | What I learn, I blog !

  3. KK KK

    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;
    }

    VN:F [1.9.22_1171]
    0
  4. Pingback: LeetCode | Technical interview solutions

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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*