477. Total Hamming Distance (Medium)

TheHamming distancebetween two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Input: 4, 14, 2
Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

1. Elements of the given array are in the range of 0 to 10^9
2. Length of the array will not exceed 10^4.

Solution 1: Brute Force O(n^2); O(1) TLE 这题面试必须演

    public int totalHammingDistance(int[] nums) {
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int xor = nums[i] ^ nums[j];
                int count = 0;
                while (xor != 0) {
                    count += xor & 1;
                    xor >>>= 1; //因为输入是非负数，所以可以不用无符号右移>>>，用>>即可
                }
                total += count;
            }
        }
        return total;
    }

Solution 2: Bit Manipulation O(n); O(1)

We can separate the calculation to do one bit at a time. For example, look at the rightmost bit of all the numbers in nums. Suppose that i numbers have a rightmost 0-bit, and j numbers have a 1-bit. Then out of the pairs, i * j of them will have 1 in the rightmost bit of the XOR. This is because there are i * j ways to choose one number that has a 0-bit and one that has a 1-bit. These bits will therefore contribute i * j towards the total of all the XORs.
Apply the algorithm to each bit (31 bits in total as specified in the problem), sum them together then we get the answer.

    public int totalHammingDistance(int[] nums) {
        int res = 0;
        int n = nums.length;
        for (int i = 0; i < 32; i++) { //计算数组中所有数在每一位的1的总数k，每位贡献k*(n-k)到最后结果。
            int bitCount = 0;
            for (int j = 0; j < n; j++) { //如果输入有负数，必须用>>>，用>>会在负数首位加1，然后死循环。
                bitCount += (nums[j] >> i) & 1; //因为输入是非负数，所以可以不用无符号右移>>>，用>>即可
            }
            res += bitCount * (n - bitCount);
        }
        return res;
    }