字节的按位逆序 Reverse Bits

ゝ一世哀愁。 2023-07-06 11:41 17阅读 0赞

源自某公司的一道试题，问题很简单：

输入一个字节（8 bits），将其按位反序。  
也就是说如果输入字节的八个比特是“abcdefgh”，要得到“hgfedcba”。作为面试题或者笔试题，自然的，隐含了一个要求：效率尽可能高。  
这个问题还有一个扩展版本，或许网上见的更多些：输入的不是字节而是 32 位整数(DWORD)，将其按位反序。

实话说，有时候这种题目颇有些钻牛角尖了，考察程序员的能力需要这样吗？之所以为其加上标签“奇技淫巧”，也是表达一个意思：这类技术的用处并不广泛，相反，大多数时候根本用不上。为了优化代码效率算是最显然的理由，在最核心最瓶颈的代码部分用上这些招数倒也无可厚非，平时还是不要乱用的好。高爷爷（Donald Knuth，神书 TAOCP 的作者）也有句名言，“过早优化是万恶之源”（Premature optimization is the root of all evil）。不过，研究研究也没有太多坏处，至少可以开拓一下思路，锻炼一下脑力，学习一些优化的手法。或者运气好的话，还可以应付一下某道笔试题或面试题。

一个平凡的解法如下（这里输入是 UINT，字节的版本对应修改类型即可）：

?  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
typedef unsigned int UINT;  
UINT reverse\_bits(UINT input) \{  
    const UINT BITS\_OF\_BYTE = 8; // 每个字节多少比特  
    UINT result = 0;             // 结果存放在这里  
    // 以下循环处理每个比特  
    for (UINT i = 0; i < sizeof(input) \* BITS\_OF\_BYTE; i++) \{  
        // 取出输入的最后一位加入 result，其他位依次左移  
        result = (result << 1) | (input & 1);  
        input >>= 1;         // 右移抛弃掉最后一位  
    \}  
    return result;  
\}  
然而这个解法显然是低效的，首先处理一个 N 位整数需要循环 N 次，每次循环中，循环体内部是 4 条指令，循环变量的修改和条件跳转还有 2 条，也就是 6N 条指令。（赋值指令倒是可以忽略，因为这几个变量都不超过寄存器大小，可以被优化，一直存放在寄存器中）。字节按位反序这种“简单任务”都需要 48 条指令，实在是有些冗长。

那有没有指令数更少的解法呢，当然有！只是这些解法就不像平凡解法那么直白和易于理解了。

在网上看过比较多的一个解答是这么做的：

?  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
// 交换每两位  
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);  
// 交换每四位中的前两位和后两位  
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);  
// 交换每八位中的前四位和后四位  
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);  
// 交换相邻的两个字节  
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);  
// 交换前后两个双字节  
v = ( v >> 16             ) | ( v               << 16);  
以上代码是处理 32 位整数的。如果输入是字节的话，只需类似的三行就可以了，如下：

?  
1  
2  
3  
4  
5  
6  
// 交换每两位  
v = ((v >> 1) & 0x55) | ((v & 0x55) << 1); // abcdefgh -> badcfehg  
// 交换每四位中的前两位和后两位  
v = ((v >> 2) & 0x33) | ((v & 0x33) << 2); // badcfehg -> dcbahgfe  
// 交换前四位和后四位  
v = ( v >> 4        ) |  (v         << 4); // dcbahgfe -> hgfedcba  
而更长的输入当然也没问题，这个模式可以继续扩展，64 位、128 位……

这段代码的妙处在于，假设我们通过某个操作交换字节的两个位（例如将 a 与 h 交换），此时其他位并没有被这个操作影响，于是自然可以考虑将多个位的交换“并行”操作。所以就有了上面这个解法，中心思想是把各个位分成组，一次性交换所有两两相邻的组。然后再通过改变交换组的大小让每个位最终到达它需要去的地方。这个解法的交换尺度是从小到大，其实从大到小也可以，感兴趣的同学可以自己试试。

这种分组交换解法的指令数为 5 \* log2(N) - 2，比平凡解法的 6 \* N 完全不是一个数量级。在 N = 32 的时候，指令数是 23 : 192，8 倍多的提升，已经是很大的改善了。不过爱钻牛角尖的程序员们还是不满足，在 N = 8 也就是需要反序一个字节的情况下，这种解法用掉了 13 条指令，那有没有更少的？

请看下面这个堪称神作的解法（用了 64 位运算）：

?  
1  
2  
unsigned char b; // 要反转的字节  
b = (b \* 0x0202020202ULL & 0x010884422010ULL) % 1023;  
虽然已经反复看过这个解法，仍然为其中蕴涵的奇思妙想深深震撼。居然只用了三条指令！在这里试着讲解一下此方法具体是怎么做的。首先，用乘法将原字节复制成 5 份，并首尾相连的放入一个 64 位整数中；然后，用 & 操作取出特定的位。这两次操作的结果是，原字节的 8 个位被分别放置到 5 个“10位组”中的正确位置上（“正确”是指反转后应在的位置）。最后用一个“%1023”将这 5 个“10位组”叠加起来，便得到最终结果了！看下面列出的具体的计算过程更明白一些：

为了方便阅读，原字节位用大写字母，算式中的“0”用了字符“.”代替，希望这样看的更清楚。  
           ......1.......1.......1.......1.......1. // 0x0202020202  
\*                                          ABCDEFGH  
\---------------------------------------------------  
           ......H.......H.......H.......H.......H. // 尾巴上有个 0 别看漏了  
          ......G.......G.......G.......G.......G.  
         ......F.......F.......F.......F.......F.  
        ......E.......E.......E.......E.......E.  
       ......D.......D.......D.......D.......D.  
      ......C.......C.......C.......C.......C.  
     ......B.......B.......B.......B.......B.  
    ......A.......A.......A.......A.......A.  
\---------------------------------------------------  
    ......ABCDEFGHABCDEFGHABCDEFGHABCDEFGHABCDEFGH.  
&   ......1....1...1....1...1....1...1........1....  
\---------------------------------------------------  
    ......A....F...B....G...C....H...D........E.... (\*)注↓  
%   .....................................1111111111  
\---------------------------------------------------  
    .......................................HGFEDCBA

(\*)  
这里连在一起看不清楚，我们把它按 10 位一组分出来：  
    .........A  
    ....F...B.  
    ...G...C..  
    ..H...D...  
    .....E....  
看，这么一分组，原字节的每个位都在正确位置上（最高两位为零）。  
以上计算过程图来源 Log4think，有改动。感谢作者 Simon 的辛苦细致！

那么爱较真的同学肯定要说，这个计算过程勉强看懂了，但是还是有几个问题没有得到解释：

为什么要复制 5 份而不是 6 份或者 4 份？  
为什么尾巴上有个 0 ？  
为什么是 10 位一组叠加而不是 xx 位一组？  
为什么运算 %1023 的结果就是按 10 位一组叠加？  
好吧，试试解答如下：

为什么要复制 5 份而不是 6 份或者 4 份？  
这个问题的答案很直白：因为 4 份不够，怎么做也做不出足够的位来，不信你试试？而 6 份又太多了，不需要。  
需要对上面的论断给出证明的话，后面有。

为什么尾巴上有个 0 ？  
猜想这个解法的作者一开始是尝试使用 0x0101010101 作为乘数的。只是发现这样做等于浪费了最低位那一份字节拷贝（因为 8 个位全部原封不动，每个位都不在正确位置上），所以将乘数左移了一位，这样最后一份字节拷贝至少能拿到一个 e 处于正确位置上。事实上最多也只能拿到一个位，很容易验证。

为什么是 10 位一组叠加而不是 xx 位一组？  
首先，少于 8 位的分组当然不行，怎么也没法选出 8 个位来。按 8 位分组显然也不行，你会发现每一组都一样，只能选到同一个位。那么试试按 9 位一组再去选正确位置？你会发现 5 份拷贝不够。于是 10 位的分组已经是最小的分组了。  
那么比 10 位更大的分组会不会更好呢？要知道不管一开始左移一位还是几位再相乘，很显然最低那一组最多只能选出一个位，而剩下的每组最多选出两个位\[1\]，于是，选出 8 个位至少需要 5 组（严格的说，最高位的第 5 组可以不完整，因此至少需要 4 组 + 1 位）。  
既然 10 位分组是最小的分组而且只需要 5 组数字，那么这已经是最优的了。

1. 这个结论可以证明。简单说就是，我们有逆序位序列（例如87654321...）和顺序位序列（例如12345678...），长度均为一个分组大小。两个序列逐位对应（8-1,7-2,...）。若在序数 (i, j) 处出现了第一次重合（也即 i mod 8 ≡ j），后面位的序数（一个增一个减）也要对 8 同余才能重合，也就是逆序的 i-4 与正序的 j+4，逆序 i-8 与正序 j+8，等等。注意到每一组最多只选低 8 位用来叠加，显然的无论 i,j 为多少，最多只可能有第 (i-4,j+4) 位和第 (i,j) 位这两个位能被选出。  
实际上，由于至少要 4 组 + 1 位，在 64 位限制下最大也只能 15 位分组。其实容易验证，10 位分组和 14 位分组是仅有的两种可行分组方式。

为什么运算 %1023 的结果就是按 10 位一组叠加？  
这是根据如下原理：% (2N - 1) 的结果，其实就是把这个数写成 2N 进制数再取各阶系数之和（严格的说只是同余），而写成 2N 进制数的各阶系数就是各个 N 位分组。从而，% (2N - 1) 的结果也就是按 N 个位分组叠加的结果。特别的，%1023 就是按 1024(210) 进制取各阶系数叠加，从而也就是 10 位分组的叠加。  
事实上，这个原理不需要非得是 2N 进制，我们还可以有更强的结论。对任何 X 进制我们都有：“任意整数N，其按X进制展开的各阶系数之和与N%(X-1)同余”。用公式表达即：

考虑整系数多项式 p(X) = aXn + bXn-1 + ... + z，有  
p(X) mod (X - 1) ≡ a + b + ... + z  
证明其实也很直白，设 Y = X - 1，代入上式既得。详细过程节约篇幅就不写了，有兴趣的同学可以去这里看，感谢 Simon 帮忙写出公式。

特别的，如果 X = 10，a..z 都是 \[0, 9\] 区间中的整数，p(X) 就是一个 10 进制数写成按阶展开，于是很容易得到下面这些速算技巧：

a. N mod 9 ≡ (N 的各位数字之和) mod 9 ≡ (N 的各位数字之和)的各位数字之和 mod 9 ... 以此类推  
b. 由上一条立刻可得，“N 能被 9 整除”等价于“N 的各位数字之和能被 9 整除”  
c. 特别的，由于 10 = 32 + 1，于是上面的两条速算技巧对 3 也成立，例如：3 的倍数其各位数字之和也是 3 的倍数  
这些东西相信每个人小学都学过，比刚才那个 1024 进制熟悉多了吧？:)

终于问题解答完毕。那么，再次隆重推荐我们刚才看到的，有如神助的“字节按位逆序”解法——只需要三条指令。如果非要说它有什么缺点，恐怕就是用了除法（取余），以及 64 位环境。

如果不用除法呢？如果只有 32 位呢？  
当然也有其他各种奇妙解法满足这些条件。其实本文中的几个算法都来自这里（英文），里面还有许许多多关于位操作的各种奇技淫巧，有兴趣的同学可以自行参观。

http://graphics.stanford.edu/~seander/bithacks.html

n = (n&0x55555555)<<1|(n&0xAAAAAAAA)>>1;  
     n = (n&0x33333333)<<2|(n&0xCCCCCCCC)>>2;  
     n = (n&0x0F0F0F0F)<<4|(n&0xF0F0F0F0)>>4;  
     n = (n&0x00FF00FF)<<8|(n&0xFF00FF00)>>8;  
     n = (n&0x0000FFFF)<<16|(n&0xFFFF0000)>>16;  
————————————————  
版权声明：本文为CSDN博主「maojudong」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/maojudong/article/details/6235274