二进制数中1的个数
作者: | 更新日期:
二进制中1的个数有很多方法, 最后有些acm题为了考察这点, 更是把时间卡到必须用O(1)才能过的地步, 现在我们来看看这些算法. 最后再赠送一个你绝对没有见过的高效的算法.
本文首发于公众号：天空的代码世界，微信号：tiankonguse
![cover][]
前言
如果你是 acmer 的话, 可能说这个太简单了. 但是我最后写一个算法你肯定没有见过, 且复杂度O(1), 并且没有用空间换时间.
如果你是 acmer 的话, 顺便可以做做这道题. [codeforces 472 比赛 G 题][codeforces-472G]
如果你是 acmer 或想自己证明下面算法的话, 就看下面的文章, 其他人可以绕道看这篇文章[详解二进制数中1的个数][bit-count-more]
若干算法
这里假设计算的是 32位无符号整数吧.
暴力
最暴力的算法就是一位一位的判断, 复杂度O(32).
unsigned __countbits(unsigned x){
unsigned n=0;
while(n +=(x&1) , x >>= 1);
return n;
}
与1的个数有关
这个复杂度不好说, 因为复杂度就是1的个数, 而1的个数是不确定的.
基本原理是 x & (x-1) 可以把x的最低位 1置换成0.
unsigned _countbits(unsigned x){
unsigned n=0;
while(x && (++n , x&=x-1));
return n;
}
分治法
分治法的原理可以看这篇文章最上面的图片.
对于32 位整数, 需要至少5次才能算出来.
所以复杂度是 O(n).
uint countbits(uint x) {
uint mask[]= {0x55555555,0x33333333, 0x0F0F0F0F,
0x00FF00FF, 0x0000FFFF
};
for(uint i=0,j=1; i<5; i++,j<<=1) {
x=(x & mask[i]) + ((x>>j) & mask[i]);
}
return x;
}
打表法
计算机的世界里, 大家应该牢记：时间与空间永远是矛盾的, 当你时间足够的时候, 就可以去考虑能不能用空间换取时间.
但是32位整数太大, 空间太大, 怎么办呢？
于是有人发现我们可以打16位的表, 这样合起来就是32位了.
于是这个方法就出现了.
const int OneNumMax = 1<<16;
int oneNum[OneNumMax];
int init(){
for(int i = 1; i < OneNumMax; ++i) {
oneNum[i] = oneNum[i >> 1] + (i & 1);
}
return 0;
}
unsigned countbits(unsigned x) {
static int a = init();
return oneNum[x >> 16] + oneNum[x & ((1 << 16) - 1)];
}
你想不到的算法
很多人看到这也就没有其他方法了.
先看代码
int bitCount ( unsigned n ) {
unsigned tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
return ( (tmp + (tmp >> 3) ) & 030707070707) % 63;
}
看完了自己想吧, 周末了, 我的笔记本还没有修好, 周末只能玩手机, 没时间写了, 下周一补上说明吧.
详细的讲解见这里 [详解二进制数中1的个数][bit-count-more]
<完> [bit-count-more]: https://github.tiankonguse.com/blog/2014/11/16/bit-count-more.html [codeforces-472G]: https://github.tiankonguse.com/blog/2014/10/04/codeforces-472G.html [cover]: http://tiankonguse.com/lab/cloudLink/baidupan.php?url=/1915453531/3526593306.png
本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。
