函数,C/C++中"/>
C语言popcount函数,C/C++中
__builtin_popcount()用于计算一个 32 位无符号整数有多少个位为1
Counting out the bits
可以很容易的判断一个数是不是2的幂次:清除最低的1位(见上面)并且检查结果是不是0.尽管如此,有的时候需要直到有多少个被设置了,这就相对有点难度 了。
GCC有一个叫做__builtin_popcount的内建函数,它可以精确的计算1的个数。尽管如此,不同于__builtin_ctz,它并没有被 翻译成一个硬件指令(至少在x86上不是)。相反的,它使用一张类似上面提到的基于表的方法来进行位搜索。这无疑很高效并且非常方便。
其他语言的使用者没有这个选项(尽管他们可以重新实现这个算法)。如果一个数只有很少的1的位,另外一个方法是重复的获取最低的1位,并且清除它。
查看引用来源
为了在 VC 上实现 __builtin_popcount (unsigned u) 的功能,自己写了两个函数,分别是 popcnt (unsigned u), popcount (unsigned u) 。
前者是通过清除 u 最低的 bit 1 ,直至 u 为 0 ,每次都为计数器加 1 。时间复杂度为 O (m) , m 为 bit 1 的个数。
后者是使用二分法,比较巧妙,跟踪调试一下就知道原理了。时间复杂度为 O (lg N) , N 为位数。
不过最高效的还是使用查表的方式来计算。
但是需要弄一个很大的表,不然随着位数的增长,查表的速度还是比不上二分法的速度。例如 64 位整数,保存 所有 8 位整数的结果 (256 个)。查表需要操作 8 次,而二分法需要 6 次而已。
测试代码如下:
// 计算一个 32 位无符号整数有多少个位为 1
#include
#include
using namespace std;
unsigned popcnt (unsigned u)
{
unsigned ret = 0;
while (u)
{
u = (u & (u - 1)); // 将 u 最右边的 1 清除
ret ++;
}
return ret;
}
unsigned popcount (unsigned u)
{
u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
return u;
}
int main ()
{
// 先测试一下函数是否正常工作
for (int i = 0; i <= 1000; i ++)
{
int k = popcnt (i);
cout << k << " ";
}
cout << endl;
for (int i = 0; i <= 1000; i ++)
{
int k = popcount (i);
cout << k << " ";
}
cout << endl;
// 比
更多推荐
C语言popcount函数,C/C++中
发布评论