c - 通过查找表了解位设置计数的位旋转技巧

Question

我正在阅读这里的 stanford bit twiddling hacks: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

对于使用查找表计算位集，我有 2 个问题: 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
   };