汉明距离总和

问题描述（来源于LeetCode）

两个整数的 汉明距离指的是这两个数字的二进制数对应位不同的数量。

给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。

代码实现

暴力破解

class Solution:

    def totalHammingDistance(self, nums: List[int]) -> int:
        n=0
        i=0
        for i in range(len(nums)):
	        j=i+1
            for j in range(len(nums)):
                n+=bin(nums[i]^nums[j]).count("1")
        return n//2

复杂度分析

• 时间复杂度$O(n^2)$
• 空间复杂度$O(1)$
  由于时间复杂度过大，所以数据较大时效率很低，所以进行优化

优化算法1

优化思路，我们对所有数的每一位统计1和0的数量，那么这一位的汉明距离=l的数量$*$ 0的数量，遍历32位即可。

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        n=0
        for i in range(32):
            co=0
            for num in nums:
                if num&(1<<i):
                    co+=1
            n+=co*(len(nums)-co)
        return n

复杂度分析

• 时间复杂度$O(n)$
• 空间复杂度$O(1)$