2

少し反転を試みています。単純な実装は理解していますが、パフォーマンスのために、ルックアップ テーブルを作成し、そのテーブルを使用してビット反転を見つけることでビットを反転する必要があります。したがって、私のプログラムはルックアップ テーブルを作成します。ビットサイズ N の場合、テーブルを使用して、指定されたビットのビット反転を見つけます。

たとえば、bitSize = 9 で num = 6 (00000110) の場合

reverse(num,bitSize) は 11000000 である 192 を返します

int lookup(int num, int bitSize)
{
    return table[bitSize][num]; // == reverse(num,bitSize);
}

これはルックアップ関数がどのように見えるかだと思います.テーブルを構築することは可能だと言われましたが、方法がわかりません.誰かがこのテーブルを構築する方法を説明できますか?

32 ビットだけでなく、指定されたbitSizeに対してこのテーブルを構築する方法を探していることを明確にしたいだけです。 .html#BitReverseTable

ご協力ありがとうございました、

編集: どちらのソリューションも機能しますが、j_random_hacker のメモリ最適化のおかげで、kmkaplan のソリューションの方が効率的です。

4

2 に答える 2

2

12ビットテーブルの場合：

int table[1<<12]; // or 4096
int i;

for (i=0;i<4096;i++) table[i] = my_straight_forward_bitreverse(12,i);

次に、他のビット長の問題を解決する必要があります。
配列intテーブル[12][4096]があります。これは約90％が空いているです。

または持っている

int table12[4096], table11[2048], table10[1024] /* , ...*/ ;  
int *table[12]={ table1, table2, /*  ...  */ table12 };

int i, j;
for (j=0;j<12;j++) 
  for (i=0;i<1<<j;i++) table[j][i]=my_straight_forward_bitreverse(j+1,i);
于 2012-11-21T09:46:19.870 に答える
1 
#include <stdio.h>
#include <stdlib.h>
int
main(int argc, char **argv)
{
  const int bitSize = atoi(argv[1]);

  printf("static unsigned int table[] = {");
  unsigned int i;
  for (i = 0; i < 1 << bitSize; i++) {
    if ((i & 7) == 0)
      printf("\n");
    unsigned int v = i;
    unsigned int r = 0;
    int s = bitSize;
    while (s--) {
      r <<= 1;
      r |= v & 1;
      v >>= 1;
    }
    printf(" 0x%x,", r);
  }
  printf("\n};\n"
         "unsigned int lookup(int num, int bitSize)\n"
         "{\n"
         "        return table[num] >> (%d - bitSize);\n"
         "}\n",
         bitSize
         );

  return 0;
}

編集: j_random_hacker メモリ最適化を実装します。

于 2012-11-21T10:50:04.937 に答える