/ Frequently Asked Questions

Calculate the Hamming Distance between two Integers

Problem Statement

Given two integers, calculate the hamming distance between them.


Solution Explanation

Hamming Distance between integers is defined as the number of indexes where the two bits differ.

For example, given integers x = 2 and y=5, the hamming distance between them is,

X    0 0 1 0
Y    0 1 1 0
HD   0 1 0 1    Total - 1  

As you see the integers 2 and 5 differ in only 1 bit position, so the hamming distance between them is 1. If you look at this, basically we are doing a XOR operation on each bit and returing the total value as hamming distance.

So, we can just do an XOR between the two given integers and do a bit count and return the value.

Below is the java implementation for hamming distance cacluclation between two integers,

public class HammingDistance {
    public static void main(String[] args){
        HammingDistance hd = new HammingDistance();
        System.out.println("Hamming distance between 2 and 5 is "+hd.hammingDistance(2,5));
    }
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        return Integer.bitCount(xor);
    }
}

Once we have the xor of the 2 integers, we need the number of 1's in the resultant binary version. To calculate that we use a inbuilt java method Integer.bitCount.

Alternatively, you can also manually calculate the bit count by continously right shifting the resultant xor value and doing an '&' with 1.

Below is the code to avoid using the inbuilt java method and find out the number of 1's,

public class HammingDistance {
    public static void main(String[] args){
        HammingDistance hd = new HammingDistance();
        System.out.println("Hamming distance between 2 and 5 is "+hd.hammingDistance(2,5));
    }
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int bitCount = 0;
        for(int i=0;i<32;i++){
            bitCount += (xor >> i) & 1;
        }
        return bitCount;
    }
}