|
在写leetcode网站的“”190. 颠倒二进制位”算法题时发现了这个方法的源码，于是有了如下研究成果。
大致思想原理
若要翻转一个二进制串，可以将其均分成左右两部分，再对划分出的左右部分各自进行划分左右，直至每部分只有一个元素
（对每部分递归执行翻转操作）
然后将左半部分拼在右半部分的后面，即完成了翻转
（例如12，左半放右半后面变为21就是翻转；1234，先划分左右，到各区域仅1个元素后开始返回，第一次返回2143，第二次返回4321，翻转完成）
由于左右两部分的计算方式是相似的，利用位掩码和位移运算，我们可以自底向上地完成这一分治流程。
对于递归的最底层（一位一组），我们需要交换所有奇偶位：
1、取出所有奇数位和偶数位；
2、将奇数位移到偶数位上，偶数位移到奇数位上。
类似地，对于倒数第二层（每两位分一组），按组号取出所有奇数组和偶数组，然后将奇数组移到偶数组上，偶数组移到奇数组上。以此类推。
需要注意的是，在某些语言（如 Java）中，没有无符号整数类型，因此对 n 的右移操作应使用逻辑右移。
更进一步解释
翻转原理：以1234为例子：翻转过来就是把最左侧的数和最右的数交换，然后向内进一层再重复交换直至内层只剩一个数或没有数。
而1234翻转得到4321，只看区域变化就是原先的左半部分和右半分交换了位置，先保留这条性质，如果只是这么交换得到的是3412，此时和正确的翻转有差异，因为左半区域和右半区域各自区域内没有进行左右交换。而把这个顺序逆过来，先对总区域划分到左右区域各只有一个元素，然后交换，再逐层往上交换，就是翻转原理。
代码节选（本质不变，为便于描述进行了轻微修改）：
public class Solution {
private static final int M1 = 0x55555555;
private static final int M2 = 0x33333333;
private static final int M4 = 0x0f0f0f0f;
private static final int M8 = 0x00ff00ff;
public int reverseBits(int n) {
n = n >>> 1 & M1 | (n & M1) << 1;
n = n >>> 2 & M2 | (n & M2) << 2;
n = n >>> 4 & M4 | (n & M4) << 4;
n = n >>> 8 & M8 | (n & M8) << 8;
return n >>> 16 | n << 16;
}
}
代码原理：
各行原理相同，以 n = n >>> 1 & M1 | (n & M1) << 1; 为例：执行顺序为
含义为将 n >>> 1 & M1 的结果和 (n & M1) << 1 的结果进行 | 运算，然后赋值给 n
n >>> 1 & M1 意为将 n >>> 1 的结果和 M1 做 & 运算，| 运算右侧的同理
第一行代码的效果：每两位互换
(n & M1) << 1：取奇位数并左移一位
（因为M1只有奇数位才使1，而&运算规定只有两1的才能为1，而偶数为全为0会使二者运算结果只保留奇数位的原值，偶数位全为0）
n = n >>> 1 & M1：右移一位再取奇位数
（相当于把(n & M1) << 1没取到的偶数位都取到了）
二者做 | 运算，假设原数据为123456（为方便描述瞎取的，6为最低位），则左侧结果为204060，右侧结果为010305，二者做或运算（含1为1），正好左侧为0的位置右侧处不为0，运算完正好是两两换位，肉眼也能看出。
第二行代码：| 运算符左半部分效果：每四位，后两位移到前两位。右半部分效果：每四位，前两位移到后面两位
(n & M2) << 2：4位之中取前两位左移两位（与第一行的同理）
(i >>> 2) & 0x33333333 : 右移两位取前两位（与第一行的同理）
第三行代码：原理同第二行，每四位交换了一下
(n & M4) << 4：取前4位左移4位
n = n >>> 4 & M4：右移4位取前4位
第四行同理，这里略
|