我正在尝试进行一点反转,我了解简单的实现方式,但是出于性能目的,我需要通过构建查找表并使用该表来查找位反转来反转位,因此我的程序将构建一个查找表对于位大小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/