class Solution {
public:
    // 1101
    // 0100
    // 1011
    // O(31n)

    int digit_1[32]; // 统计每个数位上1的个数
    int totalHammingDistance(vector<int>& nums) {
        int n = nums.size();
        for (auto x : nums) 
            for (int i = 0; i <= 31; i ++) 
                if (x >> i & 1) digit_1[i] ++;

        int res = 0;
        for (int i = 0; i <= 31; i ++ ) {
            res += digit_1[i] * (n - digit_1[i]);
        }
        return res;
    }
};