位反转算法 通过5 * lgN次运算完成

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

位反转

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

算法说明

该算法用于将任意 $2^n$ 位数的数进行位反转。运算次数为5 * lg(N)次， 由所要反转的数的位数决定，例如要反转32位数，N = 32，那么运算次数为5 * lg(32) = 25次； 要反转8位数，N = 8，那么运算次数为5 * lg(8) = 15次。

位反转算法代码

unsigned int reverse(unsigned int x) { // swap odd and even bits x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1); // swap consecutive pairs x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2); // swap nibbles ... x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4); // swap bytes x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8); // swap 2-byte long pairs x = ( x >> 16 ) | ( x << 16); return x; }

算法来源

Bit Twiddling Hacks

算法计算过程

计算分为五个步骤，每个步骤有5次运算

1.x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1)

这行的代码就是以两个bit位一组，对调相邻的bit位，或者可以说是反转奇数位和偶数位的bit位。

2.x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2)

这行的代码就是以4个bit位为一组，分成左边两个bit位一段和右边两个bit位一段，然后这两段相互对调。

3.x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4)

这行的代码就是以8个bit位为一组，分成左边四个bit位一段和右边四个bit位一段，然后这两段相互对调，或者说是反转半字节的数。

4.x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8)

这行的代码就是以16个bit位为一组，分成左边八个bit位一段和右边八个bit位一段，然后这两段相互对调，或者说是反转一个字节的数。

5.x = ( x >> 16 ) | ( x << 16)

这行的代码就是高16bit与低16bit进行交换，或者说是反转两字节一组的数。

可以参照高效位反转算法的图解，原理相同。

拓展

可以用于将任意 $2^n$ 位数的数进行位反转，例如对代码稍加修改可以改成8位数的位反转。

[参考资料]

Bit Twiddling Hacks By Sean Eron Anderson

高效位反转算法

[Hacker’s Delight] 作者: Henry S. Warren Jr.