10

我在这里找到了查找表。该表生成为 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)
};
4

3 回答 3

14

首先发表评论：这种事情通常只在IOCCC中完成。像这样的代码不应该在生产环境中使用，因为它是不明显的。我之所以提到这一点是为了消除这样的错误印象，即这具有任何性能或空间优势，编译后的代码将包含与将 256 个数字直接写入数组时相同的（数量）字节。

好的，现在看看它是如何工作的。它当然是递归地工作的，在顶层 R6 定义两个位，然后在下一个定义两个位......但是细节如何？行：

你得到的第一个线索是有趣的 0->2->1->3 序列。你应该问自己“为什么？ ”。这是构建所需的构建块。二进制中的数字 0 1 2 3 是00 01 10 11，如果将每个数字反转：00 10 01 11即 0 2 1 3！

现在让我们看看我们希望表格做什么：它应该变成这样：

00000000 10000000 01000000 11000000 
00100000 10100000 01100000 11100000 
00010000 10010000 01010000 11010000
00110000 10110000 01110000 11110000 ...

因为您希望它将索引 0 映射到 0，索引 00000001 到 10000000 等等。

请注意，每个数字的最重要（最左边）2 位：00 10 01 11对于每一行！

现在请注意，每个数字的第二个最重要的 2 位以相同的方式增加（00 10 01 11），但对于“列”。

我选择将数组排序为长度为 4 的行的原因是，我们发现一次写入 2 位，2 位可以创建 4 个模式。

00 10 01 11如果您然后继续观察表格的剩余数字（总共 256 个条目），您将看到如果您在 16 列中对表格进行排序，则可以发现第 3 2 位具有序列，而在按列排序时可以找到最后 2 位64 个。

现在我含蓄地告诉你原始宏扩展中的数字 16 和 64 是从哪里来的。

这就是细节，概括地说：递归的最高级别生成最低有效 2 位，中间两级执行它们的操作，最低级别生成最高有效 2 位。

于 2013-02-27T09:07:32.180 回答
1

如果您正在使用 Python 并且碰巧在这里结束，这就是查找表的样子。尽管如此，Bernd Elkemann 的 解释仍然成立。

# Generating the REVERSE_BIT_LUT while pre-processing
# LUT is shorthand for lookuptable
def R2(n, REVERSE_BIT_LUT):
    REVERSE_BIT_LUT.extend([n, n + 2 * 64, n + 1 * 64, n + 3 * 64])


def R4(n, REVERSE_BIT_LUT):
    return (
        R2(n, REVERSE_BIT_LUT),
        R2(n + 2 * 16, REVERSE_BIT_LUT),
        R2(n + 1 * 16, REVERSE_BIT_LUT),
        R2(n + 3 * 16, REVERSE_BIT_LUT),
    )


def R6(n, REVERSE_BIT_LUT):
    return (
        R4(n, REVERSE_BIT_LUT),
        R4(n + 2 * 4, REVERSE_BIT_LUT),
        R4(n + 1 * 4, REVERSE_BIT_LUT),
        R4(n + 3 * 4, REVERSE_BIT_LUT),
    )


def LOOK_UP(REVERSE_BIT_LUT):
    return (
        R6(0, REVERSE_BIT_LUT),
        R6(2, REVERSE_BIT_LUT),
        R6(1, REVERSE_BIT_LUT),
        R6(3, REVERSE_BIT_LUT),
    )


# LOOK_UP is the function to generate the REVERSE_BIT_LUT
REVERSE_BIT_LUT = list()
LOOK_UP(REVERSE_BIT_LUT)

我正在努力在此处提供Sean在 Python中的小技巧的代码片段。

于 2020-04-26T12:22:02.980 回答
0

反向位表只是可能的离线生成常量之一。人们通过使用展开宏找到一种算法来定义它。不可能为另一个常数找到这样的算法。所以无论如何你都必须维护一些发电机基础设施。

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define BYTES_PER_LINE 16
#define BYTES_GLUE ", "
#define LINE_PREFIX "  "
#define LINE_TERMINATOR ",\n"

#define PRINT(string) fwrite(string, 1, sizeof(string), stdout)

static inline void print_reversed_byte(uint8_t byte) {
  uint8_t reversed_byte = 0;

  for (uint8_t bit_index = 0; bit_index < 8; bit_index++) {
    uint8_t bit_value = (byte >> bit_index) & 1;
    reversed_byte |= bit_value << (7 - bit_index);
  }

  printf("0x%02x", reversed_byte);
}

int main() {
  uint8_t index = 0;

  while (true) {
    if (index != 0) {
      if (index % BYTES_PER_LINE == 0) {
        PRINT(LINE_TERMINATOR);
        PRINT(LINE_PREFIX);
      } else {
        PRINT(BYTES_GLUE);
      }
    }

    print_reversed_byte(index);

    if (index == 255) {
      break;
    }
    index++;
  }

  return 0;
}

generated_constants.c.in在cmake中使用它：

const uint8_t REVERSE_BITS_TABLE[256] = {
  @CMAKE_REVERSE_BITS_TABLE@
};

您将收到漂亮紧凑的桌子。

例如，请参阅它在LZWS中的用法。

于 2018-12-05T20:58:31.757 回答