Bit Manipulation Interview Questions and Answers

Write a Java method that will return the number of bits that will need to be changed in order to convert an integer, X, into another integer, Y and vice versa. The method should accept two different integers as input. For example, if your method is passed the integers 12 and 16 then your method should return a 3 .

This problem may confuse you at first, but as always it’s best to break any problem down so that you can understand it better.




Let’s take a closer look at the example given to us. It says that for the input of a 12 and 16, the output of the method should be a 3. Since we are looking for the number of bits that will need to be changed, let’s convert 12 and 16 to binary to further understand this bit manipulation problem. The binary representation of 12 is 01100 and the binary representation of 16 is 10000. Comparing the binary representation of those two numbers, we can see that the first 3 digits are different, which means that to convert 12 to 16 or 16 to 12 we would have to change 3 numbers. And that is why the method that we write should output a 3. Hopefully that’s clear to you now.

So, now we know what we want to do, but the question is how do we actually do it? Here’s a hint: think of the common binary operators and see if you can come up with something that would help solve this problem.

Using the XOR operator to solve this bit manipulation interview question




The binary operator that is perfect for this exercise is the XOR operator. If you need a refresher on how that operator works you can read this: XOR in Java. This is because the XOR operator will return true when the binary digits being compared are different, but will return false when they are the same. So, if we just XOR the two numbers being passed in, the result of the XOR operation will be binary number that will have a binary 1 each and every time there is a different bit between the inputs x and y, and a binary 0 when the bits in the input x and y are the same. So, for example, if we XOR 1001 and 0101 the result of the XOR operation would be a 1100 because the 2 leftmost bits are different, so the result of XOR’ing those 2 bits would be a 1 but the 2 rightmost bits in our inputs are the same, so the result of XOR would be a 0.

The algorithm to solve the bit manipulation interview problem

So, the algorithm to solve this bit manipulation interview question would be:

First, XOR the two numbers being passed in – call them x and y – and then call the result Z.

Then, just count the number of binary 1’s in Z since that count represents the number of different bits in the two numbers x and y. In order to count the number of binary 1’s in Z, we can just take Z, and perform the binary AND operation with the number 1. When the result of that operation is a 1 then we know that the very last binary digit in Z is a 1. Then, we can shift Z by 1 bit and repeat until there is nothing left to shift – which is when Z is equal to 0.

Answer in Java to bit manipulation interview question

Here is the Java implementation of that algorithm and our final answer to this problem:

public static int findNumberOfBits(int x, int y)
{
int bitCount = 0;

int z = x ^ y;  //XOR x and y

while (z != 0)
{
  //increment count if last binary digit is a 1:
  bitCount += z & 1; 
  z = z >> 1;  //shift Z by 1 bit to the right
}

return bitCount;
}

The code above should be pretty self explanatory as long as you understand the simple algorithm that we used and read the comments in the code. Hopefully you learned something new from this interview question!

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • Chandrahas Muvvala

    Their time complexity is comparable to any other binary operator.

  • discussion on bit manipulation and interview questions at notes4geeks.com/main/bit/bit_manipulation.html

  • Gopinath M B

    Good explanation and I agree with Thomas …It should be unsigned right shift rather than signed right shift..
    >> will shifts to the right and append sign bit (0 if positive and 1 if negative) to the MSB.
    >>> will shifts to the left and always append ‘0’ to the MSB.

  • Hello, there is a mistake.
    You should use >>> operator instead of >>. Otherwise it won’t work with negative numbers. You’d have an infinite loop 🙂

    Thanks for this helpful post.

  • vinodh

    What would be run time of the above program? basically I am trying to figure out what would be the run time when only & and ^ operators are used?

  • Saurabh

    Thanks very simple and self explanatory.

  • abhinav

    nice post. helpful

  • Kamal

    nice example problem..!!