牛客练习赛60A——大吉大利

网址：https://ac.nowcoder.com/acm/contest/4853/A

题目描述

给定n个整数，依次为a_1,a_2,...,a_n。求sum=a_i&a_j（i从一到n,j从一到n）“&”是二进制的与运算符。

输入描述:

第一行一个整数n.
第二行n个整数a_i.

输出描述:

一个整数表示上述求和式的答案.

输入

5
1 2 3 4 5

输出

33

备注:

1≤n≤1e5,0≤a_i≤1e8

题解:

这道题如果使用双重for循环是一定会超时的。这里的a_i不是负数比较好做，如果a_i可以是负数，那么这道题就不算签到题了。
首先将n个数都进行二进制讨论，例如看看二进制位从右数第三位上有多少个1，那么这一位的贡献就是个数个数(i<<3),将所有位的贡献加到一起，就是最后的结果。

AC代码：

#include<iostream>
#include<cmath>
using namespace std;
#define ll long long int
int main(){
    ll sum=0;
    ll n,a,b[50]={0};
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        for(int j=0;a;j++){
            if(a&1) b[j]++;
            a=a>>1;
        }
    } 
    for(int i=0;i<=40;i++){
    //    sum+=b[i]*b[i]*pow(2,i);
        sum+=b[i]*b[i]*(1<<i);
    }
    cout<<sum<<endl;
    return 0;
}

打卡第17天。过好每一天。