Tag Archives: binary

Hamming Distance (Leetcode 22)

This is another question and solution from the archive. I think this is a nice educational question, but not a great interview question. It’s an OK interview question. I tagged this “vocabulary” because Hamming distance, and the tools (that I think are) the right ones to solve this are less things you gain insight about over time, and instead things you learn. Some observations:

  1. The final punchline involves the XOR operator (^), which can be understood in a few ways. One way is seeing it as a symmetric-difference operator (or something like that), where the two integers are bitsets. So the result is a third bitset, that contains all those elements that were in exactly 1 of the two original bitsets. This sounds like what we want!
  2. The missing piece is being able to count the 1s in that resulting set. The vocab to use here is “popcount”, which is either a hardware instruction or — if you’d like — a simple enough loop.
class Solution {
public:
    int popcount(int x) {
        int count = 0;
        while (x) {
            if (x % 2) {
                count++;
            }
            x >>= 1;
        }
        return count;
    }
    int hammingDistance(int x, int y) {
        return popcount(x^y);
    }
};