求数补码中1的个数
题目链接http://111.230.154.87/problem.php?cid=1005&pid=1
题目描述
有N个正整数的范围内请你输出这N个正整数的补码中存在有多少个1?
时间限制: 2 Sec 内存限制: 128 MB
输入
每一个输入文件只有一组测试数据
第一行为N,(1<=N<=2e6)
接下来有N个64位的正整数
保证测试文件所有数补码中1总数占的比率在10%左右
输出
输出补码中1的个数
样例输入
3 7 8 2
样例输出
5
如果直接暴力求解 每个数都一点一点的求 肯定会超时 这时候就要使用位操作中的与操作运算符&
&的作用是计算的时候按位计算,&两边操作数对应位上全为1时,结果的该位值为1。否则该位值为0
我们用&运算符来对n和n-1进行与操作 这将会把补码中的一个且只有一个1转换为0 下面用图来解释
可以看到 15补码中1的个数有4个而我们对15进行操作4次后15变为0 也就是说我们每次进行操作都会把15补码中的一个1转换为0 以此类推进行了多少次n&(n-1)并且把结果赋给n;操作 n的补码就有多少个1 因此我们用这种方法就可以节省90%的时间 具体代码如下
#include<iostream>
using namespace std;
int main(void)
{
long long N;
cin >> N;
long long ans=0;
while(N--)
{
long long a;
cin >> a; //输入要求的数字
while(a) //如果数字补码中还有1就继续循环
{
a=a&(a-1); //进行了一次n&(n-1)并且把值赋给n
ans++; //统计进行了多少次n&(n-1) 也就是统计有多少个1
}
}
cout << ans << endl;
return 0;
}
第一次写博客 请多谅解