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.
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.
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.
Time Complexity: O(1) since integer size is fixed.
Space Complexity: O(1) because we use a constant amount of space.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Using XOR and Bit Manipulation | Time Complexity: O(1) since integer size is fixed. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| XOR + Bit Counting | O(1) | O(1) | General case. Simple and readable solution using XOR and counting set bits. |
| XOR + Brian Kernighan’s Algorithm | O(k) | O(1) | When the XOR result has few set bits. Efficient bit trick that removes one set bit per iteration. |
Hamming Distance • Kevin Naughton Jr. • 23,671 views views
Watch 9 more video solutions →Practice Hamming Distance with our built-in code editor and test cases.
Practice on FleetCode