宏-生成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)
};

下面的链接解释了其背后的算法。但是我并不完全理解它。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，但一次执行四次。

[二进制数字012 3，以000110 11表示，如果您将每个数字取反：001001 11，您会得到021 3！

[021 3应该是构建块，我们将使用以下公式进行概括：

n，n + 2 * 4，n + 1 * 4，n + 3 * 4

Hint：尝试使用上式导出列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位可能会过大。您可以只初始化一组反向值。

无论如何，我希望这能帮助您理解模式。