宏生成4位查询表

Question

下面是位反转的查询表(8位)

  static const unsigned char BitReverseTable256[256] = 
{
  #   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
  #   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
  #   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
      R6(0), R6(2), R6(1), R6(3)
};

下面的链接解释了it.But背后的算法，我没有完全理解它。Look-up table for 8 bit reversal

我想要类似的4位反转的宏，这样我就可以理解8位。有没有人可以提供相同的宏4位反转。

谢谢,

Answer 1

对于4位整数，您的查找表的大小为16，即pow(2, 4)。我将从手动枚举开始，这样我们就可以找出是否存在模式：

Integer  Binary Representation  Reverse Binary Representation   Reverse Value

0            0000                        0000                        0
1            0001                        1000                        8
2            0010                        0100                        4
3            0011                        1100                        12
4            0100                        0010                        2
5            0101                        1010                        10
6            0110                        0110                        6
7            0111                        1110                        14
8            1000                        0001                        1
9            1001                        1001                        9 
10           1010                        0101                        5
11           1011                        1101                        13
12           1100                        0011                        3
13           1101                        1011                        11
14           1110                        0111                        7
15           1111                        1111                        15

请注意，在Reverse Binary Representation列中，最左边(最重要的2位)以相同的方式增加，即每四次增加一次00 10 01 11。

同样，请注意，在Reverse Binary Representation列中，最右侧(最低有效的2位)也采用相同的模式，即00 10 01 11，但一次使用四次。

这些数字，0 1 2 3，以二进制表示，是00 01 10 11，如果您反转每个数字：00 10 01 11，您将得到0 2 1 D21！

0 2 1 3将是构建块，我们将使用以下等式进行推广：

n、n + 2 * 4、n + 1 * 4、n + 3 * 4

提示:尝试使用上面的等式导出列Reverse Value。例如，前四个值派生自n=0

0         = 0
0 + 2 * 4 = 8
0 + 1 * 4 = 4
0 + 3 * 4 = 12

我很久没有写过C语言了，但我想你应该会有(我会纠正)：

static const unsigned char BitReverseTable[16] = 
{
     define R2(n) n, n + 2*4, n + 1*4, n + 3*4
     R2(0), R2(2), R2(1), R2(3)
};

在Python中：

def R2(n, FOUR_BIT_LUT):
    FOUR_BIT_LUT.extend([n, n + 2 * 4, n + 1 * 4, n + 3 * 4])


def LOOK_UP(FOUR_BIT_LUT):
    return (
        R2(0, FOUR_BIT_LUT),
        R2(2, FOUR_BIT_LUT),
        R2(1, FOUR_BIT_LUT),
        R2(3, FOUR_BIT_LUT),
    )


FOUR_BIT_LUT = list()
LOOK_UP(FOUR_BIT_LUT)

print(FOUR_BIT_LUT) # [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

然而，基于宏的解决方案对于4位可能是过度杀伤力。你可以只初始化一个反向值的数组。

无论如何，我真的希望这能帮助你理解这个模式。