通过查找表了解位集计数的位旋转技巧

Question

我正在阅读斯坦福大学的一些小技巧： http: //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

对于用查找表设置的位数进行计数，我有两个问题：1）

c = BitsSetTable256[v & 0xff] + 
BitsSetTable256[(v >> 8) & 0xff] + 
BitsSetTable256[(v >> 16) & 0xff] + 
BitsSetTable256[v >> 24]; 

这怎么是正确的呢。因此，该表包含为 256 个数字预先计算的位数 = 2^8。现在我们有一个 32 位数字来计算位集。v31..v24 v23...v16 v15...v8 v7..v0

我们需要做的就是在查找表中每8位查找一次

所以，它应该是

c = BitsSetTable256[v & 0x0F] + 
    BitsSetTable256[v>>8 & 0x0F] + 
    BitsSetTable256[v>>16 & 0x0F] +
    BitsSetTable256[v>>24]

我的观点是，我们应该使用 & 0x0F 而不是 FF 来获得 256 范围内的正确数字，对吗？

我在这里缺少什么？:( :(

2）另外，这个宏对于位集的相同位旋转黑客部分意味着什么

static const unsigned char BitsSetTable256[256] = 
{
 #   define B2(n) n,     n+1,     n+1,     n+2
 #   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
 #   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
 B6(0), B6(1), B6(1), B6(2)
};

你如何扩展这个？

谢谢

Answer 1

1. 不，该页面是正确的。 0x0F是二进制1111（十进制 15）- 设置了四位。 0xFF为二进制11111111（十进制255），设置8位。

2. 您可以在其上运行预处理器来查看（我进行了一些编辑以使其可读）：

   static const unsigned char BitsSetTable256[256] =
   {
       0, 0 +1, 0 +1, 0 +2, 0 +1, 0 +1 +1, 0 +1 +1, 0 +1 +2, 0 +1,
       0 +1 +1, 0 +1 +1, 0 +1 +2, 0 +2, 0 +2 +1, 0 +2 +1, 0 +2 +2,
       0 +1, 0 +1 +1, 0 +1 +1, 0 +1 +2, 0 +1 +1, 0 +1 +1 +1, 0 +1 +1 +1,
       0 +1 +1 +2, 0 +1 +1, 0 +1 +1 +1, 0 +1 +1 +1, 0 +1 +1 +2, 0 +1 +2,
       0 +1 +2 +1, 0 +1 +2 +1, 0 +1 +2 +2, 0 +1, 0 +1 +1, 0 +1 +1, 0 +1 +2,
       0 +1 +1, 0 +1 +1 +1, 0 +1 +1 +1, 0 +1 +1 +2, 0 +1 +1, 0 +1 +1 +1,
       0 +1 +1 +1, 0 +1 +1 +2, 0 +1 +2, 0 +1 +2 +1, 0 +1 +2 +1, 0 +1 +2 +2,
       0 +2, 0 +2 +1, 0 +2 +1, 0 +2 +2, 0 +2 +1, 0 +2 +1 +1, 0 +2 +1 +1,
       0 +2 +1 +2, 0 +2 +1, 0 +2 +1 +1, 0 +2 +1 +1, 0 +2 +1 +2, 0 +2 +2,
       0 +2 +2 +1, 0 +2 +2 +1, 0 +2 +2 +2, 1, 1 +1, 1 +1, 1 +2, 1 +1, 1 +1 +1,
       1 +1 +1, 1 +1 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +2, 1 +2 +1, 1 +2 +1,
       1 +2 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1,
       1 +1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +2,
       1 +1 +2 +1, 1 +1 +2 +1, 1 +1 +2 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2,
       1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +1, 1 +1 +1 +1,
       1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +2, 1 +1 +2 +1, 1 +1 +2 +1, 1 +1 +2 +2,
       1 +2, 1 +2 +1, 1 +2 +1, 1 +2 +2, 1 +2 +1, 1 +2 +1 +1, 1 +2 +1 +1,
       1 +2 +1 +2, 1 +2 +1, 1 +2 +1 +1, 1 +2 +1 +1, 1 +2 +1 +2, 1 +2 +2,
       1 +2 +2 +1, 1 +2 +2 +1, 1 +2 +2 +2, 1, 1 +1, 1 +1, 1 +2, 1 +1, 1 +1 +1,
       1 +1 +1, 1 +1 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +2, 1 +2 +1,
       1 +2 +1, 1 +2 +2, 1 +1, 1 +1 +1, 1 +1 +1, 1 +1 +2, 1 +1 +1, 1 +1 +1 +1,
       1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 
       1 +1 +2, 1 +1 +2 +1, 1 +1 +2 +1, 1 +1 +2 +2, 1 +1, 1 +1 +1, 1 +1 +1, 
       1 +1 +2, 1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +1,
       1 +1 +1 +1, 1 +1 +1 +1, 1 +1 +1 +2, 1 +1 +2, 1 +1 +2 +1, 1 +1 +2 +1,
       1 +1 +2 +2, 1 +2, 1 +2 +1, 1 +2 +1, 1 +2 +2, 1 +2 +1, 1 +2 +1 +1,
       1 +2 +1 +1, 1 +2 +1 +2, 1 +2 +1, 1 +2 +1 +1, 1 +2 +1 +1, 1 +2 +1 +2,
       1 +2 +2, 1 +2 +2 +1, 1 +2 +2 +1, 1 +2 +2 +2, 2, 2 +1, 2 +1, 2 +2, 2 +1,
       2 +1 +1, 2 +1 +1, 2 +1 +2, 2 +1, 2 +1 +1, 2 +1 +1, 2 +1 +2, 2 +2,
       2 +2 +1, 2 +2 +1, 2 +2 +2, 2 +1, 2 +1 +1, 2 +1 +1, 2 +1 +2, 2 +1 +1,
       2 +1 +1 +1, 2 +1 +1 +1, 2 +1 +1 +2, 2 +1 +1, 2 +1 +1 +1, 2 +1 +1 +1,
       2 +1 +1 +2, 2 +1 +2, 2 +1 +2 +1, 2 +1 +2 +1, 2 +1 +2 +2, 2 +1
       2 +1 +1, 2 +1 +1, 2 +1 +2, 2 +1 +1, 2 +1 +1 +1, 2 +1 +1 +1, 2 +1 +1 +2,
       2 +1 +1, 2 +1 +1 +1, 2 +1 +1 +1, 2 +1 +1 +2, 2 +1 +2, 2 +1 +2 +1,
       2 +1 +2 +1, 2 +1 +2 +2, 2 +2, 2 +2 +1, 2 +2 +1, 2 +2 +2, 2 +2 +1,
       2 +2 +1 +1, 2 +2 +1 +1, 2 +2 +1 +2, 2 +2 +1, 2 +2 +1 +1, 2 +2 +1 +1,
       2 +2 +1 +2, 2 +2 +2, 2 +2 +2 +1, 2 +2 +2 +1, 2 +2 +2 +2
   };