[LeetCode] Reverse Bits

1Reverse bits of a given 32 bits unsigned integer.

For example, given input 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?

解题思路1

做法与字符串转化为整形类似，只不过这里是二进制，而且是从右边开始处理。

实现代码1

//Runtime：10 ms
#include <iostream>
#include "inttypes.h"
using namespace std;

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        int i = 32;
        while(i--)
        {
            result = result * 2 + (n & 0x1);
            n >>= 1;
        }

        return result;
    }
};

int main()
{
    Solution s;
    cout<<s.reverseBits(43261596)<<endl;
    return 0;
}

解题思路2

在思路1的基础上解除对机器上uint32_t长度的依赖

实现代码2

//Runtime：9 ms
#include <iostream>
#include "inttypes.h"
using namespace std;
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        uint32_t i;
        for(i = 1; i != 0; i <<= 1)
        {
            result <<= 1;
            result |= (n & 0x1);
            n >>= 1;
        }

        return result;
    }
};

解题思路3

通过直接对无符号整型数字的位进行交换来解题

实现代码3

//Runtime：10 ms
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t i;
        uint32_t x = sizeof(x) * 8; //uint32_t的位数
        for(i = 0; i < x / 2; i++)
        {
            swapBit(n, i, x - i - 1);
        }

        return n;
    }

    void swapBit(uint32_t& n, uint32_t i, uint32_t j){
        uint32_t lo = (n >> i) & 0x1; 
        uint32_t hi = (n >> j) & 0x1;
        if (lo ^ hi) //第i位和第j位不相等
        {
            //0 ^ 1 = 1
            //1 ^ 1 = 0，从而达到交换目的
            n ^= ((1U << i) | (1U << j));
        }
    }
};