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 - 1Note: This question is the same as 2220: Minimum Bit Flips to Convert Number.
The key idea behind solving Hamming Distance is to determine how many bit positions differ between two integers. A clean way to achieve this is by using the XOR (^) bitwise operation. When two bits differ, XOR produces 1; when they are the same, it produces 0. Therefore, applying XOR to the two numbers highlights exactly the positions where they differ.
Once the XOR result is computed, the problem reduces to counting the number of set bits (1s) in that result. This can be done using standard bit counting techniques, such as repeatedly shifting bits or using the efficient Brian Kernighan’s algorithm, which removes the lowest set bit in each iteration.
Because integers typically have a fixed number of bits (e.g., 32 bits), the algorithm runs very quickly. The solution relies purely on bit manipulation and does not require additional data structures, making it both time and space efficient.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| XOR + Bit Counting | O(k) where k is the number of bits | O(1) |
| XOR + Brian Kernighan’s Algorithm | O(number of set bits) | O(1) |
Kevin Naughton Jr.
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.
Time Complexity: O(1) since integer size is fixed.
Space Complexity: O(1) because we use a constant amount of space.
1#include <stdio.h>
2
3int hammingDistance(int x, int y) {
4 int xor = x ^ y;
5 int count =
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Hamming Distance and similar bit manipulation problems are common in technical interviews, including FAANG companies. They test a candidate’s understanding of bitwise operations and ability to write efficient low-level logic.
The optimal approach uses the XOR operation to highlight differing bits between two integers. After computing the XOR, you simply count the number of set bits in the result using bit counting techniques such as Brian Kernighan’s algorithm.
XOR returns 1 when two corresponding bits are different and 0 when they are the same. This behavior directly matches the definition of Hamming Distance, which counts positions where the bits differ.
No special data structure is required for this problem. It relies purely on bit manipulation operations, making simple integer variables sufficient for computing the XOR and counting set bits.