l*8
2 楼
old problem. you need 5 ">>", 10 "&" and 5 "+" but no branching
T*9
3 楼
看x&x-1多久到0
【在 s***e 的大作中提到】
: 怎样统计一个unsigned int中1的个数.
: 请教最有效的算法.
【在 s***e 的大作中提到】
: 怎样统计一个unsigned int中1的个数.
: 请教最有效的算法.
l*8
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;
}
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
5 楼
some explanations here
http://everything2.com/e2node/Counting%25201%2520bits
http://everything2.com/e2node/Counting%25201%2520bits
X*r
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);
然被问到了。
其实还有一种有效的方法：查表法，也可以查表和移位加相结合。
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
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.
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
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
相关阅读
能不能推荐一些用户体验做的比较好的iOS/Android应用？老中做不了hardcore engineering (转载)spark contributors寻IOS开发伙伴当年号称的PSD一家比一家烂，全是垃圾型startup。 (转载)请教版内的平板电脑硬件工程师一个问题Svn vs git常年混这版的工资沒有超过2０万的Flink可以contributejava 链表里面dummy node 一问？谢谢Linux Makefile: How to include cpp files in subfolder for (转载)为什么在windows 的 c++ ide codeblocks 上装个c++ package 这么麻烦？建议马工们有机会多搞信息安全、安全开发方面的东西 (转载)第三代编程语言基本特征都很相似最近在用clj干活。顺便看了看macro 倒吸一口冷气。hn首页文章，is heron killing storm?Gatech Online CS到底是不是很难？ (转载)Flink Sparks Next Wave of Distributed Data Processingapp过时了吧 下一波大发展估计是机器人用什么编程?有啥arm linux可以用的轻量js IDE吗？