题目链接:http://oj.ecustacm.cn/problem.php?id=1094
时间限制: 1 Sec 内存限制: 256 MB
题目描述
把一个正数转成二进制数后,各位数字分别是0或1,请你编程统计有多少位是1。
如11的二进制数是1011,共有三位是1。
输入
输入有若干行,每行一个正整数,数字不超过10^18。
输出
对应输出二进制数的1的个数。
样例输入 Copy
11
1
721
样例输出 Copy
3
1
5
来源/分类
基础题 数论
题意:就是求一个二进制数有多少个一
思路:用简单好理解的直接转为二进制统计一的个数,或者用与运算来做。以下提供三种题解。
法一: 将原数字转为二进制,在此过程统计1的个数
这个方法不用多说,就是转换过程中多加个判断语句统计下即可
代码:
1 num=0; 2 long long m=n; // 法一: 将原数字转为二进制,在此过程统计1的个数 3 while(m!=0) 4 { 5 int t=m%2; 6 if(t==1) 7 num++; 8 m/=2; 9 } 10 cout<<num<<endl;
法二: 将原数字(二进制)一直往右移动 与 1 进行 与运算
举个例子,比如数字5,二进制表示为101(忽略前面的0),
101往不断右移,每次都与1进行与运算,如果结果等于1就说明存在一个1,直到移动64位后停止(因为题目给的数量级是:数字不超过10^18,所以用long long)然后统计个数就可以了
101(原数字,也就是右移0位后的数字)
001(1)
001 相与的结果等于1(num++)
---------------------------------------------------------
010 (右移1位后的数字)
001(1)
000 相与的结果不等于1
---------------------------------------------------------
001 (右移2位后的数字)
001 (1)
001 相与的结果等于1(num++)
---------------------------------------------------------
001再右移就变成000了(所以到这也就把所有的1统计完了)
000 (右移3位后的数字)
001 (1)
000 相与的结果不等于1
代码:
1 num=0; 2 for(int i=0; i<64; i++) // 法二: 将原数字(二进制)一直往右移动 与 1 进行 与运算 3 { 4 if(((n>>i)&1)==1) 5 num++; 6 } 7 cout<<num<<endl;
法三: 每次消掉最后面的那个1
这个很巧妙,就是让n=((n-1)&n),直到n==0停止,这个过程中每次就可以消掉最右边的那个1
还用5举例 101
101 (n)
100 (n-1)
100 相与的结果等于100,没跳出循环num++
然后n=100了
---------------------------------------------------------
100 (n)
011 (n-1)
000 相与的结果等于100,此时还没跳出循环num++
n=0了,跳出循环了,结束。
代码:
1 num=0; 2 while(n!=0) // 法三: 每次消掉最后面的那个1 3 { 4 n=((n-1)&n); 5 num++; 6 } 7 cout<<num<<endl;
完整代码:
1 #pragma GCC optimize(2) 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<map> 8 #include<stack> 9 #include<set> 10 #include<vector> 11 #include<queue> 12 #include<iomanip> 13 #include<bitset> 14 using namespace std; 15 int main() 16 { 17 long long n,x; 18 long long num=0; 19 while(cin>>n) 20 { 21 num=0; 22 long long m=n; // 法一: 将原数字转为二进制,在此过程统计1的个数 23 while(m!=0) 24 { 25 int t=m%2; 26 if(t==1) 27 num++; 28 m/=2; 29 } 30 cout<<num<<endl; 31 32 num=0; 33 for(int i=0; i<64; i++) // 法二: 将原数字(二进制)一直往右移动 与 1 进行 与运算 34 { 35 if(((n>>i)&1)==1) 36 num++; 37 } 38 cout<<num<<endl; 39 40 num=0; 41 while(n!=0) // 法三: 每次消掉最后面的那个1 42 { 43 n=((n-1)&n); 44 num++; 45 } 46 cout<<num<<endl; 47 48 } 49 return 0; 50 }
任取一种方法即可
加油!
共同努力!
Keafmd