s***e
发帖数: 793 | 1 怎样统计一个unsigned int中1的个数.
请教最有效的算法. |
l***8
发帖数: 149 | 2 old problem. you need 5 ">>", 10 "&" and 5 "+" but no branching |
T*****9
发帖数: 2484 | 3 看x&x-1多久到0
【在 s***e 的大作中提到】
: 怎样统计一个unsigned int中1的个数.
: 请教最有效的算法.
|
l***8
发帖数: 149 | 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**8
发帖数: 25 | |
X****r
发帖数: 3557 | 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);
|
t****t
发帖数: 6806 | 7 事实上本版精华区里就有....
http://www.mitbbs.com/bbsann2/computer.faq/Programming/algorithm/number_bit/%E5%AF%B9%E6%95%B0%E5%AD%97%E7%9A%84%E4%BD%8D%E6%93%8D%E4%BD%9C
【在 X****r 的大作中提到】
: 这个问题也太老了吧，N年前就流传开了，当时还在版上讨论过，在我被面试的时候居
: 然被问到了。
: 其实还有一种有效的方法：查表法，也可以查表和移位加相结合。
:
: x){i++;x&=(x-1);}" method.
|
l***8
发帖数: 149 | 8
It wastes two unnecessary "&" operations. Compare that with mine and you'll
see.
【在 M**8 的大作中提到】
: some explanations here
: http://everything2.com/e2node/Counting%25201%2520bits
|
