Total Hamming Distance

题目描述

The Hamming Distance between two integers is the number of different digits between their binary representation. For example the hamming distance between 4(=01002) and 14(11102) is 2.

Given N integers, A1, A2, … AN, find out the total hamming distance of all pairs of them.

输入

The first line contains an integer N.

The second line contains N integers denoting A1, A2, … AN.

For 80% of the data: 1 <= N <= 1000

For 100% of the data: 1 <= N <= 100000 1 <= Ai <= 1000000000

输出

The total hamming distance

样例输入

3
1 2 3

样例输出

4

题意

输入一个n，接下来n个数，然后求这个n个数两两比较二进制位数不同的总和

思路

首先想到暴力n²枚举，优化思路变为 对于每一个二进制位，统计一下N个数中，有几个在这一位是0，有几个在这一位是1。假设有x个是0，y个是1，那么在这一位的产生的距离就是xy。如果我们把32个二进制位看成是常数，那么时间复杂度是O(N)的。

AC代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
#define bug(x) cout<<"bug-----"<<x<<endl
#define R(i,n) for(int i = 0; i < n; i++)
using namespace std;
const int mod= 1e9+7;
const int maxn = 110 +10;
LL a[33+10];
LL b[33+10];
int main(){
    //freopen("C:\\Users\\admin\\Desktop\\1.in","r",stdin);
    //freopen("C:\\Users\\admin\\Desktop\\1.out","w",stdout);
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        LL t;
        cin>>t;
        for(int i=0;i<=34;i++)
        {
            if(t&1)
            {
                a[i]++;
            }
            else
            {
                b[i]++;
            }
            t>>=1;
            //cout<<t<<endl;
        }
    }
    LL ans=0;
    for(int i=0;i<=34;i++)
    {
        ans+=a[i]*b[i];
    }
    cout<<ans<<endl;

    return 0;
}