位运算——n的二进制中有几个1
题目描述
给定一个长度为 n 的数列,请你求出数列中每个数的二进制表示中 1 的个数。
输入格式
第一行包含整数 n。
第二行包含 n 个整数,表示整个数列。
输出格式
共一行,包含 n 个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。
数据范围
1≤n≤100000,
0≤数列中元素的值≤10^9
输入样例
5
1 2 3 4 5
输出样例
1 1 2 1 2
注释版代码(两种)
第一种方法
#include<iostream>
using namespace std;
int main()
{
int n,count=0;
scanf("%d",&n);
for(int i=0;i<32;i++)//二进制最多32位,将32位依次往最后一位移
{
if((n>>i)&1==1)//然后将最后一位&1,若该位为1,那么&1的结果也是1
{
count++;//是1就就把出现1的次数加1
}
}
printf("%d",count);
return 0;
}
第二种方法
#include<iostream>
using namespace std;
int lowbit(int n)
{
return n&-n;//lowbit函数的作用是返回n的最后一位1
}
int main()
{
int n,count=0;
scanf("%d",&n);
while(n)//只要n不为n,说明里面还有1,就继续进行
{
n=n-lowbit(n);//找到n里面的最后一位1,然后count+1,然后将最后一位1减去再看看还有没有1
count++;
}
printf("%d",count);
return 0;
}