位反转算法

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

位反转

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

算法说明

该算法用于将任意 $2^n$ 位数的数进行位反转。运算的时间复杂度是O(lg(N))。与位反转算法 通过5 * lg(N)次运算完成相比，这个算法的优点是常数在过程中计算，可以减少内存占用。

位反转算法代码

32位数的位反转代码

unsigned int reverse(unsigned int v) { unsigned int s = sizeof(v) * 8; // bit size; must be power of 2 unsigned int mask = ~0; while ((s >>= 1) > 0) { mask ^= (mask << s); v = ((v >> s) & mask) | ((v << s) & ~mask); } return v; }

8位数的位反转代码

unsigned char reverse(unsigned char v) { unsigned char s = sizeof(v) * 8; // bit size; must be power of 2 unsigned char mask = ~0; while ((s >>= 1) > 0) { mask ^= (mask << s); v = ((v >> s) & mask) | ((v << s) & ~mask); } return v; }

算法来源

Bit Twiddling Hacks

算法计算过程

用8位数的位反转计算过程举例。

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

计算过程如下

v :v = abcdefgh s = sizeof(v) * 8 :s = 8 mask = ~0 :mask = 0xFF s >>= 1 :s = 4 s > 0 mask ^= (mask << s) :mask = 0x0F mask ^= (0xFF << 4) mask ^= (0xF0) mask = 0xFF^0xF0 mask = 0x0F v = ((v >> s) & mask) | ((v << s) & ~mask) v = ((abcdefgh >> 4) & 0x0F) | ((abcdefgh << 4) & ~0x0F) v = (0000abcd & 0x0F) | (efgh0000 & 0xF0) v = 0000abcd | efgh0000 v = efghabcd s >>= 1 :s = 2 s > 0 mask ^= (mask << s) :mask = 0x33 mask ^= (0x0F << 2) mask ^= (0x3C) mask = 0x0F^0x3C mask = 0x33 v = ((v >> s) & mask) | ((v << s) & ~mask) v = ((efghabcd >> 2) & 0x33) | ((efghabcd << 2) & ~0x33) v = (00efghab & 0x33) | (ghabcd00 & 0xCC) v = 00ef00ab | gh00cd00 v = ghefcdab s >>= 1 :s = 1 s > 0 mask ^= (mask << s) :mask = 0x55 mask ^= (0x33 << 1) mask ^= (0x66) mask = 0x33^0x66 mask = 0x55 v = ((v >> s) & mask) | ((v << s) & ~mask) v = ((ghefcdab >> 1) & 0x55) | ((ghefcdab << 1) & ~0x55) v = (0ghefcda & 0x55) | (hefcdab0 & 0xAA) v = 0g0e0c0a | h0f0d0b0 v = hgfedcba s >>= 1 :s = 0 s = 0 v = hgfedcba

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

[参考资料]

Bit Twiddling Hacks

高效位反转算法

位反转算法 通过5 * lg(N)次运算完成

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