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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) since integer size is fixed.
Space Complexity: O(1) because we use a constant amount of space.
Hamming Distance • Kevin Naughton Jr. • 23,406 views views
Watch 9 more video solutions →Practice Hamming Distance with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor