Interview Question Hamming Distance

By Fatih KABAKCI

The problem is to figure out how many corresponding bits are different of given x and y. This is known as humming distance. Humming distance compares each corresponding bits of two value by looking if they are different. If so, then adds 1 to the value of humming distance.

Problem #461 - Hamming Distance

Description: The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       d   d

The above arrows point to positions where the corresponding bits are different.

Difficulty: Easy

Solution in Java

Shorter way

As known, XOR operation is a calculation that sets result to 1 if two corresponding bits are different. Thus, we can reach to the result directly by using XOR operation in Java. Then, what we need to do is basically counting number of 1 bits that gets us to the final point which is a humming distance.

public class Solution {
    public int hammingDistance(int x, int y) {
		int xORy = x ^ y;
        return Integer.bitCount(xORy);
    }
}

Long way

package com.fatihkabakci.Easy.HammingDistance;

/**
 * @author fkabakci
 * Problem Description: The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
 * 
 * Given two integers x and y, calculate the Hamming distance.
 * 
 * Solution:
 * 1. Find max and min.
 * 2. Get length of bits of the greater one.
 * 3. Get bits of both with the capacity of the greater one.
 * 4. Figure out the difference of bit positions.
 * 
 * Example:
 * 
 * Input: x = 1, y = 4
 * 
 * Output: 2
 * 
 * Explanation:
 * 1   (0 0 0 1)
 * 4   (0 1 0 0)
 *  	  d   d
 * Total: 2 
 * 
 * The above arrows point to positions where the corresponding bits are different.
 */

public class Solution {
	private int getBitLength(int number) {
		int i = 0;
		for (i = 0; i < 31 && number >= Math.pow(2, i); i++);
		return i;
	}

	private byte[] toBits(int number, int bitLength) {
		int capacity = getBitLength(number);
		if (bitLength < capacity) {
			bitLength = capacity;
			System.err.println("Attempt to override capacity !");
		}

		byte[] bits = new byte[bitLength];
		for (int i = bitLength; number > 0; i--) {
			bits[i - 1] = (byte) (number % 2);
			number = number / 2;
		}
		return bits;
	}

	public int hammingDistance(int x, int y) {
		int max = Math.max(x, y);
		int min = Math.min(x, y);

		int maxBitLength = getBitLength(max);

		byte[] bitsX = toBits(max, maxBitLength);
		byte[] bitsY = toBits(min, maxBitLength);

		int hammingDistance = 0;
		for (int i = 0; i < maxBitLength; i++)
			if (bitsX[i] != bitsY[i])
				hammingDistance++;

		return hammingDistance;
	}

	public static void main(String[] args) {
		int hammingDistance = new Solution().hammingDistance(1, 2);
		System.out.println(hammingDistance);
	}
}