什么是最快的方法来计数UInt32中的设置位 [英] What is the fastest way to count set bits in UInt32
本文介绍了什么是最快的方法来计数UInt32中的设置位的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
在不使用查找表的情况下,对UInt32
中的置位位数(即1的位数)进行计数的最快方法是什么?有没有办法计算O(1)
?
What is the fastest way to count the number of set bits (i.e. count the number of 1s) in an UInt32
without the use of a look up table? Is there a way to count in O(1)
?
推荐答案
与以下项重复: how-to-implementation-bitcount-using-only-bitwise-operators 或者 best-algorithm-计算32位整数中的设置位数
Is a duplicate of: how-to-implement-bitcount-using-only-bitwise-operators or best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer
有很多解决该问题的方法.我使用的是:
And there are many solutions for that problem. The one I use is:
int NumberOfSetBits(int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
这篇关于什么是最快的方法来计数UInt32中的设置位的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文