1094: 有多少位是1（求一个正整数二进制中1的个数）

题目链接1094: 有多少位是1

时间限制: 1 Sec 内存限制: 256 MB
题目描述
把一个正数转成二进制数后,各位数字分别是0或1，请你编程统计有多少位是1。
如11的二进制数是1011，共有三位是1。
输入
输入有若干行，每行一个正整数，数字不超过10^18。
输出
对应输出二进制数的1的个数。
样例输入 Copy
11
1
721
样例输出 Copy
3
1
5
来源/分类
基础题 数论

题意：就是求一个二进制数有多少个一
思路：用简单好理解的直接转为二进制统计一的个数，或者用与运算来做。以下提供三种题解。
 
法一： 将原数字转为二进制，在此过程统计1的个数
这个方法不用多说，就是转换过程中多加个判断语句统计下即可

代码：

num=0;
long long m=n;  // 法一： 将原数字转为二进制，在此过程统计1的个数
while(m!=0)
{ int t=m%2; if(t==1) num++; m/=2;
}
cout<<num<<endl;

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

 
法二： 将原数字（二进制）一直往右移动 与 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

代码：

num=0;
for(int i=0; i<64; i++) // 法二： 将原数字（二进制）一直往右移动 与 1 进行 与运算
{ if(((n>>i)&1)==1) num++;
}
cout<<num<<endl;

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

 
法三： 每次消掉最后面的那个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 相与的结果等于000，此时还没跳出循环num++
 n=0了，跳出循环了，结束。

代码：

num=0;
while(n!=0) // 法三： 每次消掉最后面的那个1
{ n=((n-1)&n); num++;
}
cout<<num<<endl;

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

完整代码：

#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<queue>
#include<iomanip>
#include<bitset>
using namespace std;
int main()
{ long long n,x; long long num=0; while(cin>>n) { num=0; long long m=n;  // 法一： 将原数字转为二进制，在此过程统计1的个数 while(m!=0) { int t=m%2; if(t==1) num++; m/=2; } cout<<num<<endl; num=0; for(int i=0; i<64; i++) // 法二： 将原数字（二进制）一直往右移动 与 1 进行 与运算 { if(((n>>i)&1)==1) num++; } cout<<num<<endl; num=0; while(n!=0) // 法三： 每次消掉最后面的那个1 { n=((n-1)&n); num++; } cout<<num<<endl; } return 0;
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
 

任取一种方法即可

加油！

共同努力！

Keafmd

本人博客园同文链接：牛哄哄的柯南

文章来源: keafmd.blog.csdn.net，作者：牛哄哄的柯南，版权归原作者所有，如需转载，请联系作者。

原文链接：keafmd.blog.csdn.net/article/details/107764077