477. 汉明距离总和
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。
示例 1：
输入：nums = [4,14,2]
输出：6
解释：在二进制表示中，4 表示为 0100 ，14 表示为 1110 ，2表示为 0010 。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6
逻辑如下：
假设数组中有 c 个数字在第 i 位是 1。
那么必然有 n - c 个数字在第 i 位是 0（其中 n 是数组总长度）。
在第 i 位上产生的汉明距离贡献，就是 1 的个数与 0 的个数的乘积。
因为每一个 1 都可以和每一个 0 配对，产生一次距离。
公式：
贡献=c×(n−c)
class Solution {
public:int totalHammingDistance(vector<int>& nums) {int ans = 0;int n = nums.size();//题目为0 <= nums[i] <= 10^9，所以最多只需要遍历30位for (int i = 0; i < 30; i++) {int c = 0;for (int val : nums) {// (val >> i) & 1 : 将 val 右移 i 位，然后 & 1，取出第 i 位的值// (0 或 1)// c += ... : 如果是 1 就计数，如果是 0 就加 0c += (val >> i) & 1;}// 累加当前位的贡献：// c 是 1 的个数，(n - c) 是 0 的个数// 它们的乘积就是第 i 位上所有数字对产生的差异总数ans += c * (n - c);}return ans;}
};
补充：位运算符
>>右移运算符 将二进制位向右移动；a>>1相当于除以2<<左移运算符 将二进制位向左移动；a<<1相当于乘以2
<< (左移运算符)
规则：将二进制位全部向左移动若干位，高位丢弃，低位补0。
数学效果：相当于乘以 2^n（其中 nn 是移动的位数）。
示例：
int a = 5; // 二进制: 0101int b = a << 1; // 将 0101 左移一位变成 1010// b 的二进制是 1010，即十进制的 10// 5 << 1 等同于 5 * 2
>> (右移运算符)
规则：将二进制位全部向右移动若干位。
逻辑右移（针对无符号数）：高位补0，低位丢弃。相当于除以 2^n并向下取整。
算术右移（针对有符号数）：高位补符号位（0或1），低位丢弃。对于负数，这能保持其符号不变。
示例：
int a = 20; // 二进制: 10100int b = a >> 2; // 将 10100 右移两位变成 00101// b 的二进制是 00101，即十进制的 5// 20 >> 2 等同于 20 / 4 = 5//位运算比乘除法运算速度快得多，所以在追求极致性能的代码中（如嵌入式系统、算法竞赛），常用 << 1 代替 * 2，用 >> 1 代替 / 2。
- 易混点：
双箭头 (>>, <<)：操作的是二进制位，或者数据的流向（输入/输出）。
单箭头 (>, <)：比较的是数值大小，像天平一样哪边重（大）。