Skip to main content
Talentd

Hamming Distance - Solution & Explanation

EasyBit Manipulation7 min readAsked at: Amazon, Meta, Google +1
Practice this problem

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:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

Example 2:

Input: x = 3, y = 1
Output: 1

 

Constraints:

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

 

Note: This question is the same as 2220: Minimum Bit Flips to Convert Number.

Approach Overview

Problem Overview: Hamming Distance measures how many bit positions differ between two integers. Given two numbers x and y, return the number of positions where their binary representations contain different bits.

Approach 1: XOR + Bit Counting (O(1) time, O(1) space)

The key observation is that the XOR operation highlights differing bits. When you compute x ^ y, every bit position where x and y differ becomes 1, and matching positions become 0. The task then reduces to counting how many 1 bits exist in the XOR result. You can iterate through the bits using bit shifts and check the least significant bit with num & 1, or use built‑in population count functions available in most languages. Since integers have a fixed bit width (usually 32 or 64 bits), the runtime is effectively constant.

This approach directly applies bit manipulation techniques. It is simple, efficient, and the most commonly expected answer during interviews. The algorithm performs one XOR operation followed by a small loop over the bits, making it both readable and optimal.

Approach 2: XOR + Brian Kernighan’s Bit Trick (O(k) time, O(1) space)

Instead of checking every bit, you can repeatedly remove the lowest set bit using the expression n = n & (n - 1). Each iteration clears one 1 from the XOR result. Count how many times this operation runs until the number becomes zero. The loop executes exactly once for each set bit, so the runtime is O(k), where k is the number of differing bits.

This technique is a classic optimization in bit manipulation and relies on properties of bitwise operations. It avoids scanning all 32 bits and becomes faster when the XOR result contains only a few set bits.

Recommended for interviews: Start with the XOR insight. Interviewers expect you to recognize that differing bits correspond to 1s in x ^ y. A straightforward bit count already achieves optimal constant time. Mentioning Brian Kernighan’s trick shows deeper familiarity with bit manipulation patterns and often earns extra points. Both approaches use O(1) space and operate within the fixed integer bit width.

Approach 1: Using XOR and Bit Manipulation

To calculate the Hamming distance between two numbers, the most efficient way is to use the XOR operation. The result of XOR operation between two numbers highlights the bits that are different. Once you have the XOR result, the task reduces to counting the number of 1s in the binary representation of this number, which indicates the number of differing bits, thus giving the Hamming distance.

The XOR operation x ^ y finds differing bits. We then count the set bits in the result by continuously shifting and checking the last bit using xor & 1. Count the number of 1s to get the Hamming distance.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) since integer size is fixed.
Space Complexity: O(1) because we use a constant amount of space.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using XOR and Bit Manipulation

Time Complexity: O(1) since integer size is fixed.
Space Complexity: O(1) because we use a constant amount of space.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
XOR + Bit CountingO(1)O(1)General case. Simple and readable solution using XOR and counting set bits.
XOR + Brian Kernighan’s AlgorithmO(k)O(1)When the XOR result has few set bits. Efficient bit trick that removes one set bit per iteration.

Video Solution

Hamming Distance | LeetCode 461 | C++, Java, Python • Knowledge Center • 15,399 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Hamming Distance easy or hard?
Hamming Distance is classified as an Easy problem. The main insight is recognizing that XOR reveals differing bit positions. Once that idea is clear, counting set bits completes the solution in a few lines of code.
Hamming Distance Python/Java solution
In Python, compute x ^ y and count set bits using bin(x ^ y).count('1') or bit operations. In Java, use Integer.bitCount(x ^ y). Both approaches run in constant time with O(1) space and rely on built-in bit counting utilities.
How to solve Hamming Distance in O(1)?
Compute x ^ y to identify the differing bit positions, then count the number of 1s in the result. Because integer size is fixed, the bit counting step runs in constant time. Many languages also provide built-in functions like popcount to compute the result efficiently.
What is the best approach for Hamming Distance?
The optimal approach uses XOR followed by counting the number of set bits. XOR highlights exactly the positions where two integers differ, turning the problem into a population count task. This solution runs in O(1) time because integers have a fixed bit width and uses O(1) extra space.
Is Hamming Distance asked at Google/Amazon/Meta?
Hamming Distance appears frequently in coding interviews at companies that test bit manipulation fundamentals. Variants or related questions have been reported in interviews at companies such as Amazon, Google, and Meta because they test understanding of XOR and bit counting techniques.
What data structure is used in Hamming Distance?
No specialized data structure is required. The solution relies on bitwise operations such as XOR, AND, and bit shifting. These operations are part of standard integer manipulation and fall under the bit manipulation category.
What is the time complexity of Hamming Distance?
Using the XOR approach, the time complexity is O(1) because at most 32 or 64 bits are processed depending on the integer type. If Brian Kernighan’s algorithm is used, the runtime becomes O(k), where k is the number of differing bits. Space complexity remains O(1).

Ready to solve this problem?

Practice Hamming Distance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of 1 Bits

Next

Total Hamming Distance