258. Bit Distance
Two sensors each publish a status word: a non-negative integer whose binary digits are individual on/off flags. To see how differently the sensors are configured, count the binary positions at which the two words disagree, meaning one has a 1 where the other has a 0. A word that is shorter in binary is padded with leading zeros.
Given the integers x and y, return the number of differing bit positions. For example, 6 (0110) and 11 (1011) disagree in three positions. Your solution should need only O(1) extra space and time proportional to the number of bits.
Example 1
- Input:
- x = 93, y = 8
- Output:
- 4
- Explanation:
In binary 1011101 and 1000 differ in 4 positions.
Example 2
- Input:
- x = 1000, y = 24
- Output:
- 6
- Explanation:
In binary 1111101000 and 11000 differ in 6 positions.
Example 3
- Input:
- x = 4096, y = 4096
- Output:
- 0
- Explanation:
In binary 1000000000000 and 1000000000000 differ in 0 positions.
Constraints
0 ≤ x, y ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log max(x,y))
- Space
- O(1)