What is Hamming distance?

In this article

1. Before you start
2. Why interviewers ask this
3. Hamming distance from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

Hamming distance is one of the smallest problems that test bit manipulation, so it appears as a warm-up in coding interview rounds; a typical pair of prompts is "the Hamming distance between two integers" followed by "now the total over all pairs in an array". The first version is quick, and the second separates candidates because the obvious solution is quadratic.

A weak answer loops over 32 bits by hand and never explains why it works. A strong answer says the exclusive-or marks the differing positions, counts the ones with a built-in, states the cost, and spots the per-bit trick for the all-pairs follow-up. Beyond interviews the idea is real engineering: the same distance describes how error-correcting codes are built and how bit-string fingerprints are compared. A warm-up like this is one part of a full interview loop.

Hamming distance from first principles

In plain words

Hamming distance

Hamming distance is the number of positions at which two sequences of the same length hold different symbols. It is zero only for identical sequences and counts substitutions only: it never counts a symbol that was inserted or deleted.

Hamming weight

Hamming weight is the number of non-zero symbols in a sequence; for a binary number it is the number of 1 bits, also called the population count. The Hamming distance of two binary numbers is the Hamming weight of their XOR, the bit-by-bit difference with no borrowing; ordinary subtraction does not work (2 minus 1 is 1, a single 1 bit, but 10 and 01 differ in both places).

Bitwise exclusive or

Bitwise exclusive or, written XOR and ^ in most languages, is the operation that compares two integers bit by bit and returns a 1 in each place where the two bits differ and a 0 where they match.

Think of two spelling tests on the same ten-letter word. Lay them side by side, tick every letter that does not match, and count the ticks: that count is the distance. The analogy breaks when a pupil leaves out a letter: a teacher marks one mistake, but the two words now have different lengths, so Hamming distance is not defined at all.

In one precise sentence, Hamming distance is the number of coordinates in which two same-length points differ. R. W. Hamming (1950) defined it that way, "the number of coordinates for which x and y are different", and noted it is the fewest edges you must walk between two corners of a cube.

Step 1: Count the positions where the symbols differ

For two equal-length strings, line them up and count the positions that do not match. The words "karolin" and "kathrin" differ in three positions, "karolin" and "kerstin" in three, and "kathrin" and "kerstin" in four¹. The binary strings 1011101 and 1001001 differ in two positions¹.

This is also where the common error lives. The SciPy 1.18.0 manual defines its hamming function as "the proportion of disagreeing components", so on the binary strings above it returns 0.2857, which is 2 out of 7, not 2¹. If an interviewer asks for the distance, the answer is the count; multiply the SciPy value by the length, or write the one-line count yourself.

Step 2: On integers, the XOR marks the differences

For two integers, the XOR has a 1 exactly in the places where their bits differ, so one operator does the whole comparison. The Python documentation lists x ^ y as the bitwise exclusive or of x and y. Take 1 and 4: in binary they are 001 and 100, and their XOR is 101, which has ones in the first and third places¹.

Nothing is looped. The operator works on all bits at once, which is why it is the standard first move. It also removes the need to convert to strings, which is slower and easy to get wrong for numbers of different lengths: a number with fewer binary digits is treated as if it had leading zeros.

Step 3: Count the 1 bits in the XOR

The Hamming distance of two integers is the number of 1 bits in a ^ b. The Python documentation describes int.bit_count(), added in version 3.10, as returning "the number of ones in the binary representation of the absolute value of the integer", also known as the population count. So (1 ^ 4).bit_count() is 2, and (3 ^ 1).bit_count() is 1¹.

Before that version the same count is bin(x).count("1"), which the documentation gives as the equivalent definition. Either way the cost is proportional to the number of bits, which for a fixed-size integer is a constant. If you must write the count yourself, repeatedly clearing the lowest set bit with n &= n - 1 runs once per 1 bit.

Step 4: For all pairs, count per bit position, not per pair

The total Hamming distance over every pair of numbers in a list is computed one bit position at a time. At a given position, if $k$ of the $n$ numbers have a 1 there, then $k$ times $n-k$ pairs differ at that position, and the total is the sum of that product over all positions. The brute-force loop checks every pair.

On the list 4, 14, 2 both methods give 6. On 1,000 random 31-bit numbers (seed 0) both give 7,741,931¹. The saving is large: 1,000 numbers have 499,500 pairs against 32,000 bit steps, and 100,000 numbers have 4,999,950,000 pairs against 3,200,000 steps¹. This is the follow-up a quadratic answer fails.

1 · Compare2 · XOR3 · Count ones4 · All pairsReplay

Step-by-step description

1. Count positions where the symbols differ.
2. XOR puts a 1 where two bits differ.
3. The bit count of the XOR is the distance.
4. Add k times n minus k for each bit position.

• The words karolin and kathrin differ in three positions.
• The XOR of 1 and 4 is 101, which has two ones, so their distance is 2.
• For all pairs, a position where k of n numbers have a 1 adds k times n minus k.

Worked example

Every row comes from the saved script¹. The pair 8 and 7 shows that the distance does not depend on how far apart the numbers are in value: they differ by 1, but 1000 and 0111 differ in all four bits.

For 4, 14 and 2 (0100, 1110 and 0010 in binary) and n = 3: bit 0 has k = 0, adding 0; bit 1 has k = 2 (14 and 2), adding 2 × 1 = 2; bit 2 has k = 2 (4 and 14), adding 2; bit 3 has k = 1 (14), adding 1 × 2 = 2. The total 0 + 2 + 2 + 2 = 6 matches the three pairs 4 and 14 (2), 4 and 2 (2), and 14 and 2 (2)¹.

Text description of the diagram

• 100,000 numbers have 4,999,950,000 pairs.
• Per-bit counting takes 3,200,000 steps for 100,000 numbers.

The same quantity measures how many errors a code survives. An error-correcting code is a set of allowed words chosen so that a corrupted word can be repaired, and its minimum distance is the smallest Hamming distance between any two allowed words. Hamming (1950) showed that the minimum distance between code points decides what a code can do: at least 2 detects any single error, and at least 3 corrects any single error, because a single error leaves the received word nearer to the right code point than to any other. The pattern continues: in his table a minimum distance of 4 gives single-error correction plus double-error detection, and 5 gives double-error correction (Hamming, 1950).

A code can spend its distance on detection or on correction: with minimum distance 5 it can correct 2 errors, or correct 1 and detect 3, or only detect 4. A seven-bit code with four data bits has 16 code words, and the minimum distance between any two of them is 3¹, so it can correct any single error, or, used only for detection, catch any 2 errors, but not both at once: a 2-bit error lands one bit away from a wrong code word, and a correcting decoder silently picks it¹.

Text description of the diagram

• Used only for detection, a minimum distance of d detects d minus 1 errors; used for correction, it corrects the whole number part of d minus 1 over 2.
• A minimum distance of 3 corrects 1 error and a minimum distance of 5 corrects 2.

The seven-bit code here is the standard (7,4) Hamming code, built from the usual generator matrix rather than copied from Hamming's paper.

Trade-offs and edge cases

Hamming distance is cheap and exact for same-length data, and a poor fit when the data is not that shape. The cases that matter:

• Different lengths. The distance is undefined. Wikipedia's entry on Hamming distance suggests the Levenshtein distance, which also counts insertions and deletions, for strings of different lengths.
• Fractions versus counts. The SciPy function returns a proportion of mismatched positions; the interview and the definition use the count.
• Negative integers. Python's bitwise operators act as if a number had infinitely many sign bits, and bit_count() counts the bits of the absolute value, so (-1 ^ 1).bit_count() is 1 although the 32-bit patterns of -1 and 1 differ in 31 places. Mask to the width first: ((a ^ b) & 0xFFFFFFFF).bit_count() gives 31¹. In a language whose integers are a fixed 32 bits, the XOR already has that width.
• Binary vectors. On 0/1 vectors, Hamming distance equals the Manhattan distance and the squared Euclidean distance; for 8-element vectors with three mismatches all three give 3¹.
• Packed flags. When fingerprints or feature flags are packed into integers, as in a machine learning coding round or a system design answer, the XOR trick compares them in one step.
• Not a similarity of meaning. Two words can differ in one position and mean opposite things; Hamming distance sees symbols, not meaning.

How to answer it in an interview

The spoken structure is: define it, name the XOR trick, state the cost, upgrade to the per-bit idea, then add the caveat.

Common mistakes

• "Hamming distance is the difference between the numbers" (wrong). 8 and 7 differ by 1 in value but in four bits (right: it counts differing bit positions, not value).
• "Convert both to strings and compare" (wrong). Binary strings of different lengths must be padded, and the loop is slower than XOR (right: XOR first, then count ones).
• "Use the SciPy value as the answer" (wrong). It is a proportion, 0.2857 for two mismatches in seven positions (right: multiply by the length or count directly).
• "Loop over all pairs for the total" (wrong). That is quadratic and fails on large inputs (right: count ones per bit position and multiply k by n minus k).
• "Hamming distance works for words of different lengths" (wrong). It is defined only for equal lengths (right: say Levenshtein distance for that case).

Follow-up questions

What is the difference between Hamming distance and Levenshtein distance?

Hamming distance counts only substitutions and needs equal lengths. Levenshtein distance also counts insertions and deletions, so it works on strings of different lengths.

How do you compute the total Hamming distance between all pairs in a list of numbers?

For each bit position, count the numbers with a 1 there, call it k, and add k times n minus k. The list 4, 14, 2 gives 6, and the method agrees with brute force on 1,000 random numbers.

Why does the Hamming distance need equal-length inputs?

It compares position by position, so there must be a partner for every position. With different lengths there is no natural alignment, which is the problem edit distances solve.

What is Hamming distance used for?

It describes how far apart code words are, which sets how many errors a code can detect or correct, as Hamming showed in 1950. It also compares binary fingerprints built so that similar items get similar bits, such as perceptual image hashes, because XOR and a bit count are fast; a small distance flags near-duplicates that a hash set, which finds only exact matches, would miss.

What changes for 64-bit or negative numbers?

Mask the XOR to the width, for example & 0xFFFFFFFF for 32 bits in Python, so negative numbers count the right bits. The per-bit loop then runs 64 times instead of 32.

Is Hamming distance the same as Manhattan distance?

On vectors of 0s and 1s, yes: both count the positions that differ. On general numbers they differ, because Manhattan distance adds up the size of each gap and Hamming distance only asks whether a position differs.

Sources

1. Error Detecting and Error Correcting Codes (R. W. Hamming), Bell System Technical Journal 29(2), pp. 147-160 — Bell System Technical Journal (scan at the Internet Archive, read 2026-10-26), 1 Apr 1950
2. Built-in types: bitwise operations on integers and int.bit_count (Python 3 documentation) — Python Software Foundation (page shows version only; read 2026-10-26), 26 Oct 2026
3. scipy.spatial.distance.hamming, SciPy v1.18.0 manual — SciPy (page shows version only; read 2026-10-26), 26 Oct 2026
4. Hamming distance (encyclopedia entry, used for the string examples) — Wikipedia (last edited 2025-11-04, pointer only), 4 Nov 2025