java program to count minimum number of bits required to convert a given number into another number

Question: Write a Java program 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.

Explanation: 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 . 

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.

Solution: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. 

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. 

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

Bit-wise and bit shift operations:

public class BitDiffernce {
    public  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;
    }

    public static void main(String args[]) {
        BitDiffernce bd = new BitDiffernce();
        System.out.println("No of bits needed to change are: "+
                   bd.findNumberOfBits(12, 46));        
    }
} 

You will get following output:

Output:                                                      
====================================================== 

No of bits needed to change are:2