我正在尝试进行一点反转,我了解简单的实现方式,但是出于性能目的,我需要通过构建查找表并使用该表来查找位反转来反转位,因此我的程序将构建一个查找表对于位大小N,然后它将使用该表查找给定位的位反转。

例如,如果bitSize = 9且num = 6(00000110)

reverse(num,bitSize)将返回192,即11000000

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

我认为这是查找函数的外观,有人告诉我可以构建表,但是我不知道如何创建,有人可以解释如何构建此表吗?

我只是想澄清一下,我正在寻找一种方法来针对给定的bitSize构建此表,而不仅仅是针对32位,否则我会使用此方法:
http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable

谢谢您的帮助,

编辑:
两种解决方案都可以工作,但km_plan的解决方案效率更高,这要归功于j_random_hacker的内存优化。

最佳答案

#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内存优化。

关于c++ - 位反转:为N位生成位反转查找表,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13489951/

10-14 18:39