LeetCode 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, 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.method
转化为计算异或结果中1的个数
int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while (z) {
cnt += z & 1;
z >>= 1;
}
return cnt;
}
n & (n-1)可以去掉n最低位的1
int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while (z) {
z &= (z - 1);
cnt++;
}
return cnt;
}LeetCode 477. Total Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.
Example 1:
Input: nums = [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).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.method
假设4个数的某一位分别是：1 0 1 0，分别计算异或值为：1 0 1 1 0 1，所以汉明距离总和为4，可以看出是0的个数和1的个数的乘积，所以对每一位计算0和1的个数的乘积就行
int totalHammingDistance(vector<int>& nums) {
int res = 0;
for (int i = 0; i < 32; i++) {
int ones = 0;
for (auto n : nums) {
if (n >> i & 1) ones++; // 1的个数
}
res += ones * (nums.size() - ones); // 1的个数*0的个数
}
return res;
}
