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 で 2 つのビットを定義し、次のレベルでさらに 2 つのビットを定義します。Ok：

最初の手がかりは、興味深い 0->2->1->3 シーケンスです。「なぜ？ 」と自問する必要があります。これは、構築に必要なビルディング ブロックです。2 進数の 0 1 2 3 は、00 01 10 11それぞれを逆にすると、00 10 01 110 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 番目の最上位 2 ビットが同じように増加することに注意してください (00 10 01 11) が、「列」についてです。

長さ 4 の行で配列を並べ替えることにした理由は、一度に 2 ビットが書き込まれ、2 ビットで 4 つのパターンを作成できることがわかったためです。

00 10 01 11次に、テーブルの残りの数 (合計 256 エントリ) を観察し続けると、テーブルを 16 列で並べると、3 番目の 2 ビットがシーケンスを持ち、列で並べると最後の 2 ビットが見つかることがわかります。 64の。

ここで、元のマクロ展開の 16 と 64 という数字がどこから来たのかを暗黙のうちに伝えました。

それが詳細であり、一般化する：再帰の最高レベルは最下位2ビットを生成し、中間の2つのレベルはそのことを行い、最低レベルは最上位2ビットを生成します。

于 2013-02-27T09:07:32.180 に答える
0

リバース ビット テーブルは、オフラインで生成される可能性のある定数の 1 つにすぎません。アンローリング マクロを使用して定義するアルゴリズムを見つけます。別の定数に対してそのようなアルゴリズムを見つけることはできません。したがって、とにかくいくつかのジェネレーター インフラストラクチャを維持する必要があります。

#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.incmakeで使用します。

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

かわいくてコンパクトなテーブルが届きます。

たとえば、 LZWSでの使用法を参照してください。

于 2018-12-05T20:58:31.757 に答える