我正在尝试做一些反转,我理解直接实现,但出于性能目的,我需要通过构建一个查找表并使用该表来查找位反转来反转位,所以我的程序将构建一个查找表中的位大小 N,然后它将使用该表来查找给定位的位反转。
例如,如果 bitSize = 9 且 num = 6 (00000110)
reverse(num,bitSize) 将返回 192,即 11000000
int lookup(int num, int bitSize)
{
return table[bitSize][num]; // == reverse(num,bitSize);
}
我认为查找函数应该是这样的,有人告诉我可以构建该表,但我不知道如何构建,有人可以解释如何构建该表吗?
我只是想澄清一下,我正在寻找一种方法来为给定的位大小构建此表,而不仅仅是 32 位,否则我会使用此方法: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
感谢您的帮助,
编辑: 两种解决方案都有效,但由于 j_random_hacker 的内存优化,kmkaplan 的解决方案更加高效。
最佳答案
#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++ - 位反转 : Generating Bit Reversal Lookup Table for N-Bits,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13489951/