首页 > 代码库 > 编程之美---确定二进制中1的个数
编程之美---确定二进制中1的个数
要实现输入一个十进制数，输出这个十进制数转化为二进制数后，‘1‘的个数，看起来题目不难，但是如何才能高效做到这一点呢？
test-1
对一个十进制数除以2，则对应的二进制数减少一位，除以2后，余数即为二进制减少那一位对应的值。
例如：
十进制数：7 （0111）
7%2=1，
7/2=3 （011）
十进制数：3 （011）
3%2=1，
3/2=1 （01）
十进制数：1 （01）
1%2=1，
1/2=0 （0）
得到‘1’的个数为3。
//test-1int fun_1(int n){ int sum=0; while(n) { if(n%2==1) { sum++; } n/=2; } return sum;}test-2
将二进制数按位右移同样可以达到除的效果，所以，可以按照如下这样做来得到‘1‘的个数。
//test-2int fun_2(int n){ int sum=0; while(n) { sum+=n&0X01; n>>=1; //右移 n=7, (0111)，每次向右移一位,向右移操作同样可以达到相除的目的 } return sum;}上面对n先和0X01按位与，如果n最低位为 1 ，则按位与的结果为1，sum+=1；
然后对n按位移位，继续判断。
PS:按位与、移位都是针对二进制数（也就是将十进制对应的二进制数）进行的。
test-3
对于以下这种情况，我们不想做多次移位，
例如：1024 （100 0000 0000）
如何高效的找到类似这种数字中，‘1‘的个数呢？
//test-3int fun_3(int n){ int sum=0; while(n) { n&=(n-1);//只计算n中‘1’的个数次 sum++; } return sum;}上述方法举例：
十进制数：12（1100）
第一次是：n=（1100）&（1011）；n=8；
第二次是：n=（1000）&（0111）；n=0；
即只进行n中‘1‘的个数次。
扩展题目：
给定两个正整数A与B，整数A与整数B二进制数表示中有多少位不同？
//A与B的二进制中有多少位不同#include<iostream>using namespace std;int fun(int n,int m){ int sum=0; while(n||m) { sum+=((0x01&n)^(0x01&m)); n>>=1; m>>=1; } return sum;}int main(){ int n,m; cin>>n>>m; int sum=fun(n,m); cout<<sum<<endl; system("pause"); return 0;}
编程之美---确定二进制中1的个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。