逆向每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);