位反转算法 愚蠢的方法

位反转算法说明位反转算法代码算法计算过程拓展[参考资料]

位反转

这里的位反转(Bit Reversal)，指的是一个数的所有bit位依照中点对换位置，例如0b0101 0111 => 0b1110 1010。也可以叫二进制逆序，按位逆序，位翻转等等。

算法说明

该算法用于将8bit数进行位反转。直接把数的所有bit位依照中点对换位置，过程直白，但是效率低。

位反转算法代码

unsigned char reverse(unsigned char x) { #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b))) union { struct { unsigned char bit0:1; unsigned char bit1:1; unsigned char bit2:1; unsigned char bit3:1; unsigned char bit4:1; unsigned char bit5:1; unsigned char bit6:1; unsigned char bit7:1; } bit; unsigned char byte; } num; num.byte = x; SWAP(num.bit.bit0, num.bit.bit7); SWAP(num.bit.bit1, num.bit.bit6); SWAP(num.bit.bit2, num.bit.bit5); SWAP(num.bit.bit3, num.bit.bit4); return num.byte; }

算法计算过程

非常直接的把数的所有bit位依照中点对换位置。

拓展

可以使用该位反转算法实现32位数的位反转。 代码如下：

unsigned char reverse(unsigned char x) { #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b))) union { struct { unsigned char bit0:1; unsigned char bit1:1; unsigned char bit2:1; unsigned char bit3:1; unsigned char bit4:1; unsigned char bit5:1; unsigned char bit6:1; unsigned char bit7:1; } bit; unsigned char byte; } num; num.byte = x; SWAP(num.bit.bit0, num.bit.bit7); SWAP(num.bit.bit1, num.bit.bit6); SWAP(num.bit.bit2, num.bit.bit5); SWAP(num.bit.bit3, num.bit.bit4); return num.byte; } unsigned int reverse_32(unsigned int x) { x = (reverse(x & 0xff) << 24)| (reverse(x >> 8 & 0xff) << 16)| (reverse(x >> 16 & 0xff) << 8)| (reverse(x >> 24 & 0xff) ); return x; }

[参考资料]

Bit Twiddling Hacks By Sean Eron Anderson