反转比特位(文章最后有干货)【转】

转自：https://blog.csdn.net/wuxianglonghaohao/article/details/21602305

http://www.newhottopic.com/2014/03/20/reverse-bits/

把一个无符号整数的比特位反转顺序。

有很多种方法来实现这个。我们这里给出一个算法：通过异或运算来交换，然后用分治方法来优化它。

提示：

你怎么把第i个和第j个位置的bit给交换了呢？如果你能用异或来实现，试着给出算法。

异或交换的小技巧：

如果一共有n个bit，反转它可以通过最少n/2次交换，最多n次交换来完成。技巧就在于实现一个交换函数swapBits(i,j)，用来交换位置在i和j的两个bit。你应该还记得异或运算：0 ^ 0 == 0, 1 ^ 1 == 0, 0 ^ 1 == 1, 和 1 ^ 0 == 1。

我们只要在第i位和第j位的bit不同时交换就行了。我们用异或来检测这两位bit是否相同。然后我们还需要切换这两个位置的bit值，我们可以再次用异或来完成操作。通过异或，两个位置的值都可以被切换了。

1. typedef unsigned int uint;
2. uint swapBits(uint x, uint i, uint j) {
3. uint lo = ((x >> i) & 1);
4. uint hi = ((x >> j) & 1);
5. if (lo ^ hi) {
6. x ^= ((1U << i) | (1U << j));
7. }
8. return x;
9. }
11. uint reverseXor(uint x) {
12. uint n = sizeof(x) * 8;
13. for (uint i = 0; i < n/2; i++) {
14. x = swapBits(x, i, n-i-1);
15. }
16. return x;
17. }

（译者注：上面的其中一行代码：x ^= ((1U < < i) | (1U << j));是为了切换两个位置的bit值，可以看个例子：x = 1001，–> x ^= ((1U < < 1) | (1U << 3)) –> x = 1001 ^ (1010) –> x = 0011 ）

用这种异或方法来反转bit位的时间复杂度是O(n)，n是传入的无符号整数的比特位数。

分而治之：

记得归并排序是怎么做的吧？让我们看一下当n=8（一字节）时是怎么样的：

1. 01101001
2. / \
3. 0110 1001
4. / \ / \
5. 01 10 10 01
6. /\ /\ /\ /\
7. 0 1 1 0 1 0 0 1

第一步是交换所有奇数和偶数位置的bit。然后交换连续成对的bit，依此类推……

因此，一共只要log(n)次操作就能完成。

下面的代码展示了一个特定的当n==32时的例子——当然，它也能很简单的去适配当n更大时的情况。

1. uint reverseMask(uint x) {
2. assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits).
3. x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
4. x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
5. x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
6. x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
7. x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
8. return x;
9. }

小记：

这不是反转bit位的唯一方法，也不是效率最高的。你想要探索更多关于反转bit位的算法/灵感，请访问这里：Bit Twiddling Hacks（译者注：该链接里真的很多好东东）。

英文原文在这里。