位操作笔记 位计数算法 使用64位指令计算12位数

  • 时间:
  • 来源:互联网
  • 文章标签:

位计数算法 使用64位指令计算12位数

  • 位计数
  • 算法说明
  • 位计数代码
    • 位计数代码
  • 算法来源
  • 算法计算过程
  • [参考资料]

位计数

位计数(Counting bits set),指的是计算一个数里bit位置1的个数,例如一个8位数0xea = 0b1110 1010,位置1的个数为5。

算法说明

该算法用于计算最大为12位的数。这个算法需要在支持快速模除的64位CPU上才能达到高性能的效果。计算12位数的位置1的个数,只需要3次操作。

位计数代码

位计数代码

unsigned int count_12bit(unsigned int x)
{
    x =  (x * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

    return x;
}

算法来源

Bit Twiddling Hacks

算法计算过程

用mnop qrst uvwx表示一个12bit数的12个bit位。

一共只需要3次操作。

1.x * 0x1001001001001ULL
x乘以0x1001001001001ULL。
1

2.x * 0x1001001001001ULL & 0x84210842108421ULL
步骤一得到的数值再与0x84210842108421ULL。
2

3.((x & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f
步骤二得到的数值再取模运算0x1f,就是31,31 = 2 5 − 1 2^{5} - 1 251 ,相当于将每5bit的数合并在一起,从0-4,5-9,10-14,15-19,……。
3

最后得到结果,就是把每个bit的值相加,得到的数值就是数里bit位置1的个数。

[参考资料]

Bit Twiddling Hacks By Sean Eron Anderson

[Hacker’s Delight] 作者: Henry S. Warren Jr.

本文链接http://www.taodudu.cc/news/show-1782162.html