题目:给定一个无符号整数x,求x的二进制表示中1的个数。
分析:
看到二进制,基本上就各种位运算的骚操作吧。
算法一:
最容易想到的,不断除2,并进行统计。
算法二:
如果已知大多数数据位是 0 的话,那么还有更快的算法,这个算法基于一个事实:x&(x-1)会消掉最后一个1。
算法三:
分治法,均分成两半,1的个数=左边1的个数+右边1的个数。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
// 时间复杂度: x的二进制位数
int count1(uint x)
{
int ret = 0;
while(x)
{
ret += (x&1);
x >>= 1;
}
return ret;
}
/*
时间复杂度:x的二进制中1的个数
每进行一次 x&(x-1) 就会消掉最后一个1,
所以 与 的次数就是1的个数
*/
int count2(uint x)
{
int cnt = 0;
while(x)
{
x = x & (x-1);
cnt++;
}
return cnt;
}
/*
分治法:
左边1个数 + 右边1的个数
出口:只有一个元素时
递归;当然也可以改成循环
*/
int count3(uint x, int len, uint mask)
{
if(len == 1) return x;
len >>= 1;
mask >>= len;
uint r = x & mask;
uint l = x >> len;
return count3(l, len, mask) + count3(r, len, mask);
}
int main()
{
int n;
int t = 5;
while(t--)
{
scanf("%d", &n);
printf("%d %d %dn", count1(n), count2(n), count3(n, 32, 0xffffffff));
}
return 0;
}
参考链接:https://www.cnblogs.com/csulennon/p/4224859.html
原文链接: https://www.cnblogs.com/lfri/p/12404965.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/193915
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!