位反轉：爲N位生成位反轉查找表

我試圖做一點反轉，我理解直接實現，但爲了性能目的，我需要通過構建查找表並使用該表來反轉位以找到位反轉，所以我的程序將建立一個查找表的N位，然後它將使用該表來查找給定位的位反轉。位反轉：爲N位生成位反轉查找表

例如，如果bitSize = 9和num = 6（00000110）

反向（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

感謝您

編輯：這兩種解決方案都能正常工作，但由於j_random_hacker的內存優化，kmkaplan的解決方案效率更高。

來源

2012-11-21 Malkavian

是什麼阻止您使用直接執行來生成表？另請注意，32位數字的表格消耗16 GB。 –

居然沒什麼，我也想，我應該使用reverse（num，bitSize）來生成表，但是，我不知道如何生成表，我不太明白表的方法... – Malkavian

bitsize永遠不會超過12位，所以大小不是一個大問題，速度是。 – Malkavian

#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-21 10:50:04 kmkaplan

對於12位表：

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

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

然後，你必須解決其他位長的問題。
有一個數組int table [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-21 09:46:19

謝謝！我明天會試一試，並會讓你知道結果。 – Malkavian

位反轉：爲N位生成位反轉查找表

回答

相關問題