位反转算法 4次运算

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

位反转

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

算法说明

该算法用于将8bit数进行位反转。算法用到了64bit乘法运算。算法通过4次运算完成位反转操作。与通过3次运算完成位反转操作算法相比，没有了取模运算。

位反转算法代码

unsigned char reverse(unsigned char x) { x = ((x * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32; return x; }

算法来源

Devised by Sean Anderson, July 13, 2001.

Bit Twiddling Hacks

算法计算过程

用abcdefgh表示一个8bit数的8个bit位。

计算分为四个步骤

1.x * 0x80200802ULL

x乘以0x80200802ULL

2.(x * 0x80200802ULL) & 0x0884422110ULL

步骤一的结果和0x0884422110ULL进行与操作

3.((x * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL

步骤二的结果乘以0x0101010101ULL

4.x = ((x * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32

步骤三的结果右移32位

最后完成从abcdefgh到hgfedcba的位反转操作。

拓展

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

unsigned char reverse(unsigned char x) { x = ((x * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32; return x; } 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 位反转算法 通过3次运算完成 [Hacker’s Delight] 作者: Henry S. Warren Jr.