477. Total Hamming Distance

477. Total Hamming Distance

The Hamming distance between 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.

My Solutions:

因为int总共有32位，对每一个数，都做一个最后一位xor 1的操作。比如全部都是0，那么返回的结果也是0。如果只有一个是1，那么返回的结果会是len-1，因为对这个1来说，有len-1次组合。

class Solution {
   public int totalHammingDistance(int[] nums) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            count += getHaming(nums, i);
        }
        return count;
    }

    private int getHaming(int[] arr, int i) {
        int len = arr.length;
        int count = 0;
        for (int n : arr) {
            count += (n >> i) & (0x01); // n往右移i位，并且和1做xor计算
        }
        return count * (len - count);
    }
}