The O(n) Club: Hamming Distance: When Your Bits Can’t Agree (And Why XOR is King)

The O(n) Club: Hamming Distance — When Your Bits Can’t Agree (And Why XOR is King)

⚡ TL;DR

How many bits do x and y disagree on? XOR them, then count the ones. Java does this in its sleep:

// Java: blink and you'll miss it
int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y);
}

🧠 How Devs Usually Mess This Up

Is it the “comparing decimal digits” club again? Sorry, friends—the Hamming distance cares about binary bits, not what your number looks like to humans. Also: if you ever reach for AND or OR, just don’t. XOR is the only one that throws a party for every disagreement between bits.

Bonus mistake: ignoring Java’s signed-ness—but unless you’re building an emulator for 1970s hardware, you can mostly relax.

🔍 What’s Actually Going On

Hamming distance is the number of bits that don’t line up between two numbers. Imagine two robots giving each other side-eye—each lit-up difference is a 1 in the XOR result.
So, x ^ y creates a number with 1s wherever the bits differ. Counting those 1s gives you the Hamming distance. You can hunt them manually, or you can invite Integer.bitCount() to count for you. (Choose wisely. You have coffee to drink.)

🛠️ PseudoCode

• XOR both numbers: int xor = x ^ y;
  Lights up a 1 wherever the bits are different.
• Count the ones with Java’s built-in: int distance = Integer.bitCount(xor);
  Let the magic happen under the hood.
• Manual fallback:
  

  int count = 0;
  while (xor != 0) {
      count += xor & 1;
      xor = xor >>> 1;
  }

  If you’re nostalgic or your coding test bans libraries.
• Return the count: That’s your answer. You can spend the saved time avoiding bugs elsewhere.

💻 The Code

// Fast and modern
int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y);
}
 // Manual labor edition
int hammingDistanceManual(int x, int y) {
    int xor = x ^ y;
    int count = 0;
    while (xor != 0) {
        count += xor & 1;
        xor = xor >>> 1; // unsigned!
    }
    return count;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Comparing decimal digits: Only Hamming distance if you like being wrong.
• Bitwise operator mistakes: XOR only. All others need not apply.
• Sign confusion: Negative numbers and unsigned shifts: use >>> for zero-fill if you’re looping.
• Time/Space: Java’s bitCount is O(1) for small ints; manual shifting is O(bits). Both eat almost no memory.

🧠 Interviewer Brain-Tattoo

“If you’re stuck comparing digits, your bits are crying in binary.”