Problem
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note:
0 ≤ x, y < 231.
Example:
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.
Solution
Basic idea
Use XOR to solve this problem. 1 ^ 0 = 1, 1 ^ 1 = 0 ^ 0 = 0. If two bits are different, it will return 1 otherwise 0. So we can calculate x ^ y, transform to binary form, and then count the number of 1 as result. For example, x = 1, y = 4, then x ^ y = 5, which is ‘0101’ in binary form. There are two ‘1’ in ‘0101’.
Python implementation
|
|
Java implementation
|
|
Time complexity
O(1)
Space complexity
O(1)
Link
461. Hamming Distance
461. 汉明距离
(中文版) 算法笔记: 力扣#461 汉明距离
近期评论