Log inSign up
easyLeetCodeNot Started

Hamming Distance

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return the Hamming distance between them.

Example 1 · Example 1: Single Bit Difference:

Input: x = 1, y = 4
Output: 2
Explanation: 1 is 0001_2, 4 is 0100_2. Differ at bit 0 and bit 2. Distance = 2.

Example 2 · Example 2: Consecutive Integers:

Input: x = 3, y = 1
Output: 1
Explanation: 3 is 0011_2, 1 is 0001_2. Differ only at bit 1. Distance = 1.

Constraints:

  • 0 <= x, y <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the definition and applications of Hamming distance in coding theory.
  • Isolate differing bits via bitwise XOR.
  • Apply Brian Kernighan's algorithm for optimal Hamming weight calculation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Calculate number of bit mismatches between two integers.
  • Measure bitwise distance.
  • Hamming distance metric.

Algorithmic Decision Tree:

  • Compute diff = x ^ y.
  • Count 1s in diff using Kernighan's loop while diff > 0.

Connected Patterns:

Count Bits to Flip to Convert A to BNumber of 1 BitsCount Set Bits

1. 32-Bit Fixed Comparison

Intuition

Loop i from 0 to 31. If ((x >> i) & 1) != ((y >> i) & 1), increment count.

When to apply: Basic baseline.

Algorithm

  1. Step 1: Initialize count = 0.
  2. Step 2: Loop i from 0 to 31.
  3. Step 3: If ((x >> i) & 1) != ((y >> i) & 1), count++.
  4. Step 4: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int hammingDistanceBrute(int x, int y) {
6 int count = 0;
7 for (int i = 0; i < 32; ++i) {
8 if (((x >> i) & 1) != ((y >> i) & 1)) {
9 count++;
10 }
11 }
12 return count;
13}
14
15int main() {
16 cout << "Brute (1, 4): " << hammingDistanceBrute(1, 4) << endl; // 2
17 cout << "Brute (3, 1): " << hammingDistanceBrute(3, 1) << endl; // 1
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(32) = O(1)
  • Space complexity: O(1)

2. XOR with Shift & Add

Intuition

Calculate diff = x ^ y. In a loop while diff > 0, add diff & 1 to count and right-shift diff >>= 1.

When to apply: When avoiding full 32 iterations.

Algorithm

  1. Step 1: diff = x ^ y, count = 0.
  2. Step 2: While diff > 0: count += (diff & 1), diff >>= 1.
  3. Step 3: Return count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int hammingDistanceShift(int x, int y) {
6 int diff = x ^ y;
7 int count = 0;
8 while (diff > 0) {
9 count += (diff & 1);
10 diff >>= 1;
11 }
12 return count;
13}
14
15int main() {
16 cout << "Shift (1, 4): " << hammingDistanceShift(1, 4) << endl; // 2
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(log(x ^ y))
  • Space complexity: O(1)

3. Brian Kernighan's Algorithm on XOR

Intuition

Compute diff = x ^ y. Use diff &= (diff - 1) in each iteration to clear the lowest set bit. The loop runs in exactly k iterations, where k is the Hamming distance.

When to apply: Optimal canonical solution for Hamming distance.

Algorithm

  1. Step 1: diff = x ^ y, count = 0.
  2. Step 2: While diff != 0: diff &= (diff - 1), count++.
  3. Step 3: Return count.

Kernighan Popcount Trace for x = 1 (0001_2), y = 4 (0100_2)

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compute diff = x ^ y = 1 ^ 4 = 5 (binary 0101)
Visual state
Values and pointers at this exact step
pointers
S
0101
0
↑ initial diff
Check / comparison
diff = 5
Decision / next transition
diff > 0, proceed with Kernighan loop.
Why this step matters

Step 1: Compute diff = x ^ y = 1 ^ 4 = 5 (binary 0101). count = 0.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int hammingDistance(int x, int y) {
8 int diff = x ^ y;
9 int count = 0;
10 while (diff != 0) {
11 diff &= (diff - 1);
12 count++;
13 }
14 return count;
15 }
16};
17
18int main() {
19 Solution sol;
20 cout << "Optimal (1, 4): " << sol.hammingDistance(1, 4) << endl; // 2
21 cout << "Optimal (3, 1): " << sol.hammingDistance(3, 1) << endl; // 1
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(k) where k is differing bits <= 32
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — 32-Bit Fixed ComparisonO(32) = O(1)O(1)Compare bit i of x and y across all 32 positions.Fixed loop.
2.Better — XOR then Right ShiftO(log(x ^ y))O(1)Compute diff = x ^ y, shift right until diff == 0, adding diff & 1.Sequential shifting.
3.Optimal — Brian Kernighan's Algorithm on XOROptimalO(k) where k is differing bitsO(1)diff = x ^ y; while diff != 0: diff &= (diff - 1), count++.Hardware bit clearing.

Common Pitfalls & Crucial Edge Cases

Subtracting set bits

popcount(x) - popcount(y) is NOT Hamming distance. For example, 1 (01) and 2 (10) both have 1 set bit, but their distance is 2.

Looping infinitely on negative numbers

In languages with signed integers, ensure unsigned right shift >>> is used if shifting manually.

String conversion overhead

Converting both to binary strings and comparing characters is slow and unnecessary.

Crucial Edge Cases to Validate:

  • x == y — Numbers are identical; Hamming distance is 0.
  • x = 0, y = 2^31 - 1 — All 31 bits differ; Hamming distance is 31.
  • One bit difference (e.g. x = 1, y = 3) — Hamming distance is 1.
  • Powers of two differing — Distance is 2 if both are powers of two.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the one-liner immediately: popcount(x ^ y).
  2. Walk through Brian Kernighan's val &= (val - 1) loop step by step.
  3. Mention real-world applications: error-detecting codes, Hamming codes, cryptographic hashing, and genome sequence comparison.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What single bitwise operation identifies all positions where two integers differ?

2.How do you count the number of 1s in the resulting XOR value efficiently?

3.What is the time complexity to compute the Hamming distance of two 32-bit integers?

Back to DSA Sheet