难度: Medium
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
给你一个整数数组 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
示例 2：
输入：nums = [4,14,4] 输出：4
提示：
1 <= nums.length <= 1040 <= nums[i] <= 109运行时间: 67 ms
内存: 18.3 MB
class Solution:
def totalHammingDistance(self, nums: List[int]) -> int:
s, n = ''.join([format(i, 'b').rjust(30, '0') for i in nums]), len(nums)
return sum((c := s[i::30].count('1')) * (n - c) for i in range(30))
该题解的思路是将nums数组中所有数字转换为长度为30的二进制字符串，然后分别统计每一位上1的个数count，那么该位上0的个数就是n-count，其中n为nums数组的长度。对于任意两个数字，如果某一位一个为0一个为1，就会对汉明距离总和有1的贡献。因此每一位对总汉明距离的贡献是count*(n-count)，将所有30位的贡献相加就得到了最终结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def totalHammingDistance(self, nums: List[int]) -> int:
# 将所有数字转换为长度为30的二进制字符串
s = ''.join([format(i, 'b').rjust(30, '0') for i in nums])
n = len(nums)
# 遍历30个二进制位，统计每个位置1的个数并计算贡献
return sum((c := s[i::30].count('1')) * (n - c) for i in range(30))
选择30位来表示每个整数是因为在标准的LeetCode问题中，整数通常是32位的有符号整数。最大的32位整数是2147483647，它的二进制表示是'01111111111111111111111111111111'，这占用了31位。通常选择30位是为了确保所有的测试整数都能在这个长度内被完整表示，同时可以避免处理32位整数中的符号位。因此，这个长度与具体的输入数值范围有直接关系，确保不会因为整数的位数不足而造成信息的丢失或错误处理。
在二进制表示中，高位补零是常见的做法，用于保持所有数字的位数一致，以便进行位运算或其他处理。在汉明距离的计算中，高位的零对结果没有贡献，因为如果两个数字在某位都是0，那么在这一位的汉明距离贡献为0。因此，补零仅为了方便处理，并不会影响非零位上的汉明距离计算，保证了算法的正确性。
步长为30是根据整数的二进制字符串的长度确定的。由于每个整数被转换成了30位的二进制字符串，这意味着在整个字符串s中，每个整数的对应位都是相隔30位出现的。例如，第一个整数的第一位，第二个整数的第一位，以此类推，都是按照30位的间隔排列的。因此，使用步长30可以直接索引到每一位对应的所有整数的相同位，方便统计每一位上的'1'的数量。
直接统计每一位上0的数量是可行的，但在实现上，计算1的数量后直接用n减去1的数量可以更快得到0的数量，这样可以减少一次字符串遍历的成本。由于每一位上的数字只可能是0或1，所以知道了1的数量，0的数量自然是总数n减去1的数量。这种方法减少了计算量，提高了算法的效率。