DSA problem
Hamming Distance
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.
The key insight is that two bits differ exactly when their XOR is 1. Therefore, computing x ^ y produces an integer whose set bits mark every position where x and y disagree. The Hamming distance is then simply the number of set bits (the population count) in that XOR result.
For example, given x = 1 (binary 0001) and y = 4 (binary 0100), the differing positions are the first and third bits, so the Hamming distance is 2.
Examples
Example 1
Input:
x = 1, y = 4Output:
2Explanation: 1 is 0 0 0 1 and 4 is 0 1 0 0 in binary. The bits differ at index 0 and index 2, giving a distance of 2.
Example 2
Input:
x = 3, y = 1Output:
1Explanation: 3 is 0 0 1 1 and 1 is 0 0 0 1 in binary. Only the bit at index 1 differs, so the distance is 1.
Constraints
- 0 <= x, y <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.