Burak Dede's Blog

Hamming Distance Problem - Leetcode

Problem

This is my approach to the solution of hamming distance problem from Leetcode. https://leetcode.com/problems/hamming-distance/description/

Seems like there is a thing called Hamming Distance and it is the total count of bits two integers different with their respective indexes. I first thing to think is how to access bits of number in your programming language. We can use shift operator and anding it with 1. This way lets say if we try to reach 5th bit we juse (x >> 5) & 1 we are shifting 5 bits so that we could get the 5th one to place where we can AND with 1 which mirror itself to result.

Looking at the problem since integer is 32bit with a simple loop we can check each bit and count differences.

public int hammingDistance(int x, int y) {
    int hamDistance = 0;
    for(int i = 0; i < 32; i++) {
        if(getBit(x, i) != getBit(y, i)) hamDistance++;
    }

    return hamDistance;
}

private int getBit(int x, int k) {
    return (x >> k) & 1;
}

Considering shifting generally single operation in modern cpus time complexity is O(max_number_of_bits)