Leetcode 477

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

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

Input:[4,14,2] Output:6

题目要求数组的长度不超过 10^4。说明不能用 O^2 的时间复杂度的解法 , 所以461. 汉明距离的解法会超时

public int totalHammingDistance(int[] nums) {
        int ans = 0, n = nums.length;

        //10^9 < 2^30 ， 枚举到29位
        for (int i = 0; i < 30; ++i) {
            int c = 0;
            for (int val : nums) {
                //来取出其第 i 位的值 , 得出不同位
                c += (val >> i) & 1;
            }
            ans += c * (n - c);
        }
        return ans;
    }

461. 汉明距离的思路则为，利用异或同为0，异为1的特点，去算二进制位不同的数目

public int hammingDistance(int x, int y) {
        if (x == y) {
            return 0;
        }

    	//剩下的均为不同位
        int cnt = x ^ y, ans = 0;
        while (cnt != 0) {
            cnt &= cnt - 1;
            ans++;
        }

        return ans;
    }

还有一个汉明权重题191. 位1的个数

public int hammingWeight(int n) {
        int ret = 0;
        while (n != 0) {
            n &= n - 1; // n & (n - 1)消除二进制位最右边的一个1
            ret++;
        }
        return ret;
    }