Hamming Distance — Editorial

Opening the reading…

Intuitionwhy XOR creates exactly the bits we need to count

A bit differs between x and y precisely when one value has 0 at that position and the other has 1. XOR has exactly this behavior: equal bits produce 0, while unequal bits produce 1. Therefore, x XOR y is a bit mask whose 1 positions are exactly the positions counted by the Hamming distance.

The remaining operation is to count the 1 bits in that mask. For example, 1 is 001 and 4 is 100, so their XOR is 101. That result contains two 1s, matching the two positions where the inputs differ. Leading zeroes do not matter because equal leading zeroes produce zeroes in the XOR result.

Approach

Compute x XOR y and store the result, because comparing the original values bit by bit would repeat the exact rule XOR already performs in one operation.

Count the 1 bits in the XOR result with the language's built-in population-count operation, because every 1 represents one differing bit and every 0 represents a matching bit.

Return that count directly, because no positions remain to inspect and the required answer is exactly the number of 1 bits.

Complexitythe integer width is fixed by the input type

MEASURE	BOUND	WHY
Time	O(w)	The XOR combines corresponding positions, and population count examines or processes those positions. Since w is fixed for int, this is also O(1) with respect to the input values.
Space	O(1)	Only the XOR result and the returned count are stored. No output container is needed, and the extra working memory does not grow with the values or with w.

Here w is the number of bit positions inspected; for a standard int under these constraints, w is 32.

Annotated solutionC++ · XOR plus built-in population count

CPPCompute the differing-bit mask with XOR, then count its 1 bits.

#include <algorithm>

using namespace std;

class Solution {
public:
    int hammingDistance(int x, int y) {
        int xorValue = x ^ y;
        return __builtin_popcount(xorValue);
    }
};

The two important lines have a strict relationship: XOR must happen before population count. Counting the 1 bits of x or y alone would measure set bits in one input, not positions where the two inputs disagree. The built-in operation returns the number of 1 bits in the mask, so its result is already the required distance.

The bit-clearing alternativea manual count when a built-in operation is unavailable

You can count the set bits without a built-in by repeatedly removing the lowest set bit. For any positive value, value - 1 changes its lowest 1 bit to 0 and changes lower zeroes to 1; ANDing the two values removes exactly that lowest 1 bit. The loop therefore runs once per set bit rather than once per bit position.

CPPClear one set bit per iteration using value &= value - 1.

#include <algorithm>

using namespace std;

class Solution {
public:
    int hammingDistance(int x, int y) {
        int value = x ^ y;
        int count = 0;

        while (value != 0) {
            value &= value - 1;
            ++count;
        }

        return count;
    }
};

This is not asymptotically better for fixed-width integers: the worst case still processes all w bit positions. It is a useful alternative when the language has no population-count function, and it can do less work when the XOR result contains only a few 1 bits. Here k is the number of 1 bits in the XOR result, so the loop takes O(k) time and O(1) extra space.