입력받은 모든 정수중 a번 비트에 1이 몇개 있는지 기록한다. 최대 100만이니까 0번 비트 ~ 19번 비트까지 기록하면 됨. 이제 각 비트별로 1의 개수 × 0의 개수 하면 합을 구할 수 있다!
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector<int> bcnt(20); // 각 자리수별로 1이 몇 개 있는지
for (int i = 0; i < 20; i++) {
for (int j = 0; j < n; j++) {
if (v[j]&(1<<i)) bcnt[i]++;
}
}
ll ans = 0;
for (int i = 0; i < 20; i++) {
ans += (1LL<<i)*bcnt[i]*(n-bcnt[i]);
}
cout << ans;
return 0;
}
수학 넘 어렵다.