两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中，任意两个数之间汉明距离的总和。
示例:
输入: 4, 14, 2
输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
注意:
数组中元素的范围为从 0到 10^9。
数组的长度不超过 10^4。
初始的思路：
任意两个数之间汉明距离，直接使用两个循环，找出两个数，然后使用这两个数字进行异或计算。将得到的结果求二进制中存在1的数量，依次累加得到结果。
func totalHammingDistance(nums []int) int {
if len(nums) <= 1 {
return 0
}
result := 0
for i:=0;i<len(nums);i++{
for j := i+1;j<len(nums);j++{
xorRes := nums[i] ^ nums[j]
tmp := getBinaryOneCount(xorRes)
result = result + tmp
}
}
return result
}
func getBinaryOneCount(num int)int{
result := ""
count := 0
for num>1{
a := num % 2
if a == 0 {
result = "0" + result
}else if a == 1{
count++
result = "1" + result
}
num = num / 2
}
if num == 0 {
result = "0" + result
}else if num == 1{
count++
result = "1" + result
}
return count
}
结果：解题思路正确，但是会超时
基本思想
左移：向左移动n位，则增加2^n倍。在二进制中相当于向右部分添加n个零
9 << 2
9:1001
结果：36:100100
右移：向右移动n位，则降低2^n倍。在二进制中相当于向左部分减少n位
9 << 2
9:1001
结果：2:10
这道题想要减少运行时间，可以通过找规律解决
在计算汉明距离的时候，我们考虑的是同一位比特位上的值是否不同，而不同比特位之间是互不影响的。
对于数组nums中的某个元素val，若其二进制的第i位为1，我们只需要统计nums中有多少个元素的第i位为0，就可以计算出val与其他元素在第i位上的汉明距离之和。
若长度为n的数组的nums的所有元素的第i位的所有二进制的第i位共有c个1，n-c个0，则这些元素在二进制的第i位上的汉明距离之和为：c*(n-c)。然后将所有位的汉明距离累加，即可得到总体的汉明值。
所有位如何确定呢？因为题目给出元素的最大值不操作109，也就是说不大于230，所以最大的元素最多占用30位。
如何求每一位是否位1呢？计算公式位：（val >> i)&1，这里的i从0开始。
9：1001
9 >> 0 = 1001 & 1 = 1 第一位为1
9 >> 1 = 100 & 1 = 0 第二位为0
实现方式为：
func totalHammingDistance(nums []int)int{
if len(nums) <= 1{
return 0
}
// 因为10^9不大于2^30，因此可以假设有30位
result := 0
n := len(nums)
for i:=0;i<30;i++{
// 计算总共在第i位的有1的数量和0的数量，然后相互组合：n * (len(nums)-n)得到的结果为该位置的结果
tmp := 0
for _,val := range nums { // 从0开始右移表示，从第一位开始移动。一开始不移动，然后移动1位整个二进制就会减少一位，也就相当于第二位
tmp += val >> i & 1
}
// 所有位数不同组合的结果，总和
result += tmp * (n-tmp)
}
return result
}