Hamming Distance

发表于 | 分类于 | |

461. 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, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

1
2
3
4
5
6
7
8
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.

题目大意

汉明距离，两个二进制数不相等的位的个数。

解题思路

按位异或，求得不相等的位。
遍历，按位与求其个数。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    func hammingDistance(_ x: Int, _ y: Int) -> Int {
        var xor = x^y
        var count = 0
        while xor != 0 {
            xor = (xor - 1) & xor
            count += 1
        }
        return count
    }
}

477. Total Hamming Distance

题目描述

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

题目大意

计算数组内所有数值的汉明距离。

解题思路

由题目例子看:

1
2
3
4
>14: 1110
>4 : 0100
>2 : 0010
>

第一列的汉明距离是2，第二列的汉明距离是2，第三列的汉明距离是2，第四列的汉明距离是0。

1
2
3
4
5
>14: 1110
>10: 1010
>2 : 0010
>1 : 0001
>

第一列的汉明距离是4，第二列的汉明距离是3，第三列的汉明距离是3，第四列的汉明距离是3。
记每一列的1的个数为count，可得规律：(nums.count - count) * count

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    func totalHammingDistance(_ nums: [Int]) -> Int {
        var ans = 0
        for i in 0..<32 {
            var count = 0
            for num in nums {
                count += (num >> i & 1)
            }
            ans += (nums.count - count) * count
        }
        return ans
    }
}
0%