Reverse Bits问题

Contact me

题目来源：

Reverse bits of a given 32 bits unsigned integer.

Example:

Input: 43261596
Output: 964176192

Explanation: 43261596 represented in binary as 00000010100101000001111010011100, 
             return 964176192 represented in binary as 00111001011110000010100101000000.

Follow up: If this function is called many times, how would you optimize it?

既然是翻转位，那么就要用到位运算了，我们计算下每一位转换后对应的位置就可以把结果写下来，直接上简单粗暴的写法：

uint32_t reverseBits(uint32_t n) {
    uint32_t m = 0;

    m |= (n & (0x01 << 0)) << 31;
    m |= (n & (0x01 << 1)) << 29;
    m |= (n & (0x01 << 2)) << 27;
    m |= (n & (0x01 << 3)) << 25;

    m |= (n & (0x01 << 4)) << 23;
    m |= (n & (0x01 << 5)) << 21;
    m |= (n & (0x01 << 6)) << 19;
    m |= (n & (0x01 << 7)) << 17;

    m |= (n & (0x01 << 8)) << 15;
    m |= (n & (0x01 << 9)) << 13;
    m |= (n & (0x01 << 10)) << 11;
    m |= (n & (0x01 << 11)) << 9;

    m |= (n & (0x01 << 12)) << 7;
    m |= (n & (0x01 << 13)) << 5;
    m |= (n & (0x01 << 14)) << 3;
    m |= (n & (0x01 << 15)) << 1;

    m |= (n & (0x01 << 16)) >> 1;
    m |= (n & (0x01 << 17)) >> 3;
    m |= (n & (0x01 << 18)) >> 5;
    m |= (n & (0x01 << 19)) >> 7;

    m |= (n & (0x01 << 20)) >> 9;
    m |= (n & (0x01 << 21)) >> 11;
    m |= (n & (0x01 << 22)) >> 13;
    m |= (n & (0x01 << 23)) >> 15;

    m |= (n & (0x01 << 24)) >> 17;
    m |= (n & (0x01 << 25)) >> 19;
    m |= (n & (0x01 << 26)) >> 21;
    m |= (n & (0x01 << 27)) >> 23;

    m |= (n & (0x01 << 28)) >> 25;
    m |= (n & (0x01 << 29)) >> 27;
    m |= (n & (0x01 << 30)) >> 29;
    m |= (n & (0x01 << 31)) >> 31;

    return m;
}

当然这里为了看的方便，没有计算0x01每次移位的值，可以计算出来，但是这里是最好的解法了吗？不过写成循环可不见得快，所以那不是我们考虑的。看下网上的解法：

uint32_t reverseBits(uint32_t n) {
    n = (n >> 16) | (n << 16);
    n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
    n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
    n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
    n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
    return n;
}

发现的确更胜一筹，这个做法作者也解释很清楚了：

abcdefgh -> efghabcd -> ghefcdab -> hgfedcba

非常棒，虽然这个题很简单，但是这个思路还是很不错的，二分的思想每次对半移动，题目也说了考虑多次调用如何优化，这个方法在多次调用肯定速度会有优势。

还有的写法是这样的(来源)：

var reverseBits = function (n) {
    var str = "00000000000000000000000000000000" + n.toString(2)
    var reverseStr = str.split("").reverse().slice(0, 32)
    var count = 0
    for (var i = 0; i < 32; i++) {
        count += (parseInt(reverseStr[i]) * Math.pow(2, reverseStr.length - 1 - i))
    }
    return count
}

这个速度明显很感人，比前面的写法会慢很多倍吧