逆向每4位在32位的int

Question

反向每隔各4比特位，例如：

0101 1011 1100 0110 becomes 
1010 1101 0011 0110 

另：

1010 1100 0101 1100 becomes 
0101 0011 1010 0011 

我可以認爲如下扭轉所有32位：

unsigned int reverseBits(unsigned int num) 
{ 
    unsigned int count = sizeof(num) * 8 - 1; 
    unsigned int reverse_num = num; 

    num >>= 1; 
    while(num) 
    { 
     reverse_num <<= 1;  
     reverse_num |= num & 1; 
     num >>= 1; 
     count--; 
    } 
    reverse_num <<= count; 
    return reverse_num; 
} 

但是如何解決上述問題呢？

Answer 1

你可以把算法complete bit-reversal，並刪除了幾個步驟，讓你只用：（未測試）

x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1); // swap odd/even bits 
x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2); // swap groups of 2 

顯然，這假設無符號整數爲32位。

Answer 2

使用類似於每次4位運行的代碼，將每個反向半字節轉換爲最終結果。

你可以有1個版本的代碼提取&的取代的4位（4位隨着每次迭代移動），並調用不同版本，需要一個4位值&反轉那些4位每次運行（通過將count設置爲3，我相信）。

Answer 3

1.查找表反轉半字節。所述i個元素給出的i半字節反轉的版本，其中i是一個無符號字節：

static const unsigned char lut[] = { 
    0x00, 0x08, 0x04, 0x0C, 0x02, 0x0A, 0x06, 0x0E, 
    0x01, 0x09, 0x05, 0x0D, 0x03, 0x0B, 0x07, 0x0F, 
    0x80, 0x88, 0x84, 0x8C, 0x82, 0x8A, 0x86, 0x8E, 
    0x81, 0x89, 0x85, 0x8D, 0x83, 0x8B, 0x87, 0x8F, 
    0x40, 0x48, 0x44, 0x4C, 0x42, 0x4A, 0x46, 0x4E, 
    0x41, 0x49, 0x45, 0x4D, 0x43, 0x4B, 0x47, 0x4F, 
    0xC0, 0xC8, 0xC4, 0xCC, 0xC2, 0xCA, 0xC6, 0xCE, 
    0xC1, 0xC9, 0xC5, 0xCD, 0xC3, 0xCB, 0xC7, 0xCF, 
    0x20, 0x28, 0x24, 0x2C, 0x22, 0x2A, 0x26, 0x2E, 
    0x21, 0x29, 0x25, 0x2D, 0x23, 0x2B, 0x27, 0x2F, 
    0xA0, 0xA8, 0xA4, 0xAC, 0xA2, 0xAA, 0xA6, 0xAE, 
    0xA1, 0xA9, 0xA5, 0xAD, 0xA3, 0xAB, 0xA7, 0xAF, 
    0x60, 0x68, 0x64, 0x6C, 0x62, 0x6A, 0x66, 0x6E, 
    0x61, 0x69, 0x65, 0x6D, 0x63, 0x6B, 0x67, 0x6F, 
    0xE0, 0xE8, 0xE4, 0xEC, 0xE2, 0xEA, 0xE6, 0xEE, 
    0xE1, 0xE9, 0xE5, 0xED, 0xE3, 0xEB, 0xE7, 0xEF, 
    0x10, 0x18, 0x14, 0x1C, 0x12, 0x1A, 0x16, 0x1E, 
    0x11, 0x19, 0x15, 0x1D, 0x13, 0x1B, 0x17, 0x1F, 
    0x90, 0x98, 0x94, 0x9C, 0x92, 0x9A, 0x96, 0x9E, 
    0x91, 0x99, 0x95, 0x9D, 0x93, 0x9B, 0x97, 0x9F, 
    0x50, 0x58, 0x54, 0x5C, 0x52, 0x5A, 0x56, 0x5E, 
    0x51, 0x59, 0x55, 0x5D, 0x53, 0x5B, 0x57, 0x5F, 
    0xD0, 0xD8, 0xD4, 0xDC, 0xD2, 0xDA, 0xD6, 0xDE, 
    0xD1, 0xD9, 0xD5, 0xDD, 0xD3, 0xDB, 0xD7, 0xDF, 
    0x30, 0x38, 0x34, 0x3C, 0x32, 0x3A, 0x36, 0x3E, 
    0x31, 0x39, 0x35, 0x3D, 0x33, 0x3B, 0x37, 0x3F, 
    0xB0, 0xB8, 0xB4, 0xBC, 0xB2, 0xBA, 0xB6, 0xBE, 
    0xB1, 0xB9, 0xB5, 0xBD, 0xB3, 0xBB, 0xB7, 0xBF, 
    0x70, 0x78, 0x74, 0x7C, 0x72, 0x7A, 0x76, 0x7E, 
    0x71, 0x79, 0x75, 0x7D, 0x73, 0x7B, 0x77, 0x7F, 
    0xF0, 0xF8, 0xF4, 0xFC, 0xF2, 0xFA, 0xF6, 0xFE, 
    0xF1, 0xF9, 0xF5, 0xFD, 0xF3, 0xFB, 0xF7, 0xFF 
}; 

2.功能扭轉半字節。它適用的查找表，以無符號的4個字節的整數的每個字節：

0000 0000 0000 0000 0101 1011 1100 0110 
0000 0000 0000 0000 1010 1101 0011 0110 

0000 0000 0000 0000 1010 1100 0101 1100 
0000 0000 0000 0000 0101 0011 1010 0011 

1100 1010 1111 1110 1011 1010 1011 1110 
0011 0101 1111 0111 1101 0101 1101 0111 

該查找表被預先計算的這種方式（ideone）：

unsigned reverse_nibbles(unsigned i) { 
    return (lut[(i & 0xFF000000) >> 24] << 24) | 
     (lut[(i & 0x00FF0000) >> 16] << 16) | 
     (lut[(i & 0x0000FF00) >> 8] << 8) | 
     (lut[ i & 0x000000FF  ]  ); 
} 

試驗結果（ideone）：

#include <stdio.h> 

int main() { 
    unsigned i, j; 
    for (i = 0; i < 256; ++i) { 
    j = ((i & 0x01) << 3) | 
     ((i & 0x02) << 1) | 
     ((i & 0x04) >> 1) | 
     ((i & 0x08) >> 3) | 
     ((i & 0x10) << 3) | 
     ((i & 0x20) << 1) | 
     ((i & 0x40) >> 1) | 
     ((i & 0x80) >> 3); 
    printf("0x%02X, ", j); 
    if (((i + 1) % 8) == 0) 
     printf("\n"); 
    } 
    return 0; 
} 

Answer 4

我的回答掉每4位如下：

num = ((num&0F0F0F0F)<<4)|((num>>4)&0F0F0F0F);