1094: 有多少位是1

题目链接: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

 

上一篇:Proj EULibHarn Paper Reading: FuzzGen: Automatic Fuzzer Generation


下一篇:CF765F Souvenirs