477. Total Hamming Distance

time:O(30*n), n is nums array length

space:O(1)

// Hamming Distance - which the corresponding bits are different. so only count 0 and 1's count

class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        int res = 0;
        
        for (int i = 0; i < 30; i++) { // 10^9 < 2^30...恩...shif 0~29次 bit
            int c = 0;
            for (int num : nums) {
                c += (num >> i) & 1; // calculate, how many 1 in index i
            }
            // n-c is 0's count
            res += c*(n-c); // 1 and 0's combination is the result , add i bit (0~29), 30 times
        }
        return res;
    }
}