Reverse bits of an unsigned integer.
将无符号整数按位反转
有几种方法可以实现一个无符号整数的按位反转。在此，我们设计一个使用异或交换（XOR swap）技巧的算法，然后使用分治法对其进行优化。
提示：
怎样实现第i位与第j位的对调？想想能否使用异或操作实现。
异或交换技巧：
按位反转可以通过将低n/2位与高位对换实现。技巧就是实现一个名为swapBits(i, j)的函数，将第i位与第j位对换。回忆一下异或运算的原理：0 ^ 0 == 0, 1 ^ 1 == 0, 0 ^ 1 == 1, and 1 ^ 0 == 1。
我们只需要在第i位与第j位不同时执行对换。判断两位是否相同可以使用异或运算（同0异1）。然后，我们需要对第i位与第j位取反。此时可以再一次使用异或操作。将第i位与第j位和1做异或即可实现位的取反。
typedef unsigned int uint;
uint swapBits(uint x, uint i, uint j) {
uint lo = ((x >> i) & 1);
uint hi = ((x >> j) & 1);
if (lo ^ hi) {
x ^= ((1U << i) | (1U << j));
}
return x;
}
uint reverseXor(uint x) {
uint n = sizeof(x) * 8;
for (uint i = 0; i < n/2; i++) {
x = swapBits(x, i, n-i-1);
}
return x;
}
分治法
还记得归并排序的原理吗？让我们看一个n == 8（一个字节）时的例子：
01101001
/ \
0110 1001
/ \ / \
01 10 10 01
/\ /\ /\ /\
0 1 1 0 1 0 0 1
第一步对换所有的奇数位和偶数位。之后再交换相邻的成对位，以此类推……
因而，总共只需要执行log(n)次操作。
下面的代码展示了当n == 32时的一个特例，但是对于更大的n值，修改一下代码也很容易实现。
注：log(32) = 5，因此当n = 32时，总计需要5次对换操作。
uint reverseMask(uint x) {
assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits).
x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
return x;
}
注意：
按位反转的实现方法不止这里提到的这些，并且这里的方法也不是最快的。了解更多的方法，可以参阅：Bit Twiddling Hacks.
原文链接：http://articles.leetcode.com/2011/08/reverse-bits.html
本文链接：http://bookshadow.com/weblog/2015/03/20/reverse-bits-unsigned-integer/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
