位反转算法 容易理解的方法

位反转算法说明位反转算法代码32位数的位反转代码8位数的位反转代码 算法来源算法计算过程[参考资料]

位反转

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

算法说明

该算法用于任意位数的位反转。

位反转算法代码

32位数的位反转代码

unsigned int reverse(unsigned int v) { unsigned int r = v; // r是v的位反转数；这里保存下v的最低有效位 int s = sizeof(v) * 8 - 1; //用于计算最后需要额外移位的次数 for (v >>= 1; v; v >>= 1) { r <<= 1; r |= v & 1; s--; } r <<= s; //当v的最高位为零时移位 return r; }

8位数的位反转代码

unsigned char reverse(unsigned char v) { unsigned char r = v; // r是v的位反转数；这里保存下v的最低有效位 int s = sizeof(v) * 8 - 1; //用于计算最后需要额外移位的次数 for (v >>= 1; v; v >>= 1) { r <<= 1; r |= v & 1; s--; } r <<= s; //当v的最高位为零时移位 return r; }

算法来源

Bit Twiddling Hacks

算法计算过程

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

计算过程如下

r = v : r = abcdefgh s = sizeof(v) * 8 - 1 : s = 7 v >>= 1 : v = 0abcdefg r <<= 1 : r = bcdefghg s-- : s = 6 v >>= 1 : v = 00abcdef r <<= 1 : r = cdefghgf s-- : s = 5 v >>= 1 : v = 000abcde r <<= 1 : r = defghgfe s-- : s = 4 …… …… …… v >>= 1 : v = 0000000a r <<= 1 : r = hgfedcba s-- : s = 0 v >>= 1 : v = 00000000 r <<= s : r = hgfedcba

最后完成abcdefgh => hgfedcba的位反转操作

假设中途v为0的时候，跳出循环r <<= s 例如这个八位数为0000efgh，此时

v >>= 1 : v = 0000000e r <<= 1 : r = 0efghgfe s-- : s = 4 v >>= 1 : v = 00000000 r <<= s : r = hgfe0000

完成0000efgh => hgfe0000的位反转操作。

[参考资料]

Bit Twiddling Hacks By Sean Eron Anderson

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