【位运算经典应用】 求二进制逆序
本文我们来讲讲二进制的经典应用-求二进制的逆序。本文的重点除了算法本身外，还有<<和>>>的神奇应用。
leetcode中有道具体的题目-Reverse Bits，题目很简单，给你一个32位无符号整数，比如43261596（00000010100101000001111010011100），返回964176192（00111001011110000010100101000000）。
常规解法
因为题目要求中不去除前导0，所以toString()方法英雄无用武之地了，常规解法只能一位位枚举。我们从低到高位枚举n的二进制码，然后将低位提到高位来表示逆序后的二进制码。
代码很简单：
var reverseBits = function(n) { var ans = 0; for(var i = 31; i >= 0; i--) { ans |= (n & 1) << i; n >>= 1; } return ans >>> 0;};前面都很好理解，return ans >>> 0可能会引起你的注意，这也正是文章开头所说的>>>的神奇应用。
假设我们把n=1带入程序，将n用二进制码表示：
0000 0000 0000 0000 0000 0000 0000 0001for循环运行完后，得到ans的二进制码为：
1000 0000 0000 0000 0000 0000 0000 0000但是对于JavaScript而言，它的32位二进制码的第一位总是符号位，所以上面的二进制码所表示的数是-2147483648。现在问题来了，在JavaScript如何把一个signed的32位整数转成一个unsigned的32位整数？ 答案就是>>>0。于是程序也就很好理解了。
var a = -2147483648; // 1000 0000 0000 0000 0000 0000 0000 0000 signedconsole.log(a >>> 0); // 2147483648 unsigned位运算解法
我们以12345为例（假设16位无符号整数，32位类似）：
0011000000111001将它逆序后得到新的二进制码：
1001110000001100转换为十进制后，为39948。
第一步：每2个为一组，组内高低位交换
00 11 00 00 00 11 01 10第二步：每4个为一组，组内高低位交换
1100 0000 1100 1001第三步：每8个为一组，组内高低位交换
00001100 10011100第四步：每16个为一组，组内高低位交换
10001110000001100那么如何用程序来表示呢？譬如第一步中，我们如何快速从0011000000111001转为00 11 00 00 00 11 01 10呢？
将奇数位提取出来：
0_1_0_0_0_1_1_0_ 空隙中用0填补（这里为了视觉效果，用了字母）：
0a1a0a0a0a1a1a0a将偶数位同样提取：
_0_1_0_0_0_1_0_1空隙处用0填补（这里为了视觉效果，用了字母）：
a0a1a0a0a0a1a0a1将奇数位右移一位，再将偶数位左移一位，相加，即得到结果：
00a1a0a0a0a1a1a00a1a0a0a0a1a0a100011000000110110取x的奇数位并将偶数位用0填充代码实现就是 x & 0xAAAA（1010101010101010），取x的偶数位并将奇数位用0填充代码实现就是 x & 0x5555（0101010101010101）
因此第一步用代码实现就是：
x = ((x & 0xAAAA) >> 1) | ((x & 0x5555) << 1);之后的代码实现也是类似，我们用C++来解Reverse Bits：
class Solution { public: uint32_t reverseBits(uint32_t n) { n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1); n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4); n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8); n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16); return n; }};高级语言或者说有unsigned int32的语言，这样也就可以了。但是蛋疼的是JavaScript是没有的，我们还是可以用>>>来进行运算，从而达到操作符号位的效果。
完整代码：
var reverseBits = function(n) { n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1); n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2); n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4); n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8); n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16); return n >>> 0;};效率之高，看图说话。
最后再次总结下，JavaScript虽然没有unsigned int32，虽然位运算过程中第一位始终是符号位，但是并不代表JavaScript不能操纵unsigned int32的整数，因为有如下两大利器能实现unsigned32位整数和signed32位整数之间的转换：
var a = -2147483648; // 1000 0000 0000 0000 0000 0000 0000 0000 signedconsole.log(a >>> 0); // 2147483648 unsignedvar a = 4294967295; // 1111 1111 1111 1111 1111 1111 1111 1111 unsignedconsole.log(a << 0); // -1 signed当然具体情境还要具体分析。
