问个小问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

问个小问题

问个小问题# Programming - 葵花宝典

s*e2008-06-21 07:06

1 楼

怎样统计一个unsigned int中1的个数.
请教最有效的算法.

l*82008-06-21 07:06

2 楼

old problem. you need 5 ">>", 10 "&" and 5 "+" but no branching

T*92008-06-21 07:06

3 楼

看x&x-1多久到0

【在 s***e 的大作中提到】

: 怎样统计一个unsigned int中1的个数.
: 请教最有效的算法.

l*82008-06-21 07:06

4 楼

"看x&x-1多久到0" is in fact not so good because the loop has conditional
branches, and in the worst case the loop has 32 iterations.
Try this. Although it looks ugly, it's at least 4x faster than the "while(x){i++;x&=(x-1);}" method.
int countbit_fast(int x)
{
x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
x += (x >> 4);
x &= 0x0f0f0f0f;
x += (x >> 8);
x += (x >> 16);
x &= 0x3f;
return x;
}

M*82008-06-21 07:06

5 楼

some explanations here
http://everything2.com/e2node/Counting%25201%2520bits

X*r2008-06-21 07:06

6 楼

这个问题也太老了吧，N年前就流传开了，当时还在版上讨论过，在我被面试的时候居
然被问到了。
其实还有一种有效的方法：查表法，也可以查表和移位加相结合。

x){i++;x&=(x-1);}" method.

【在 l***8 的大作中提到】

: "看x&x-1多久到0" is in fact not so good because the loop has conditional
: branches, and in the worst case the loop has 32 iterations.
: Try this. Although it looks ugly, it's at least 4x faster than the "while(x){i++;x&=(x-1);}" method.
: int countbit_fast(int x)
: {
: x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
: x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
: x += (x >> 4);
: x &= 0x0f0f0f0f;
: x += (x >> 8);