博文中会简要介绍Leetcode P0190题目分析及解题思路。

“Reverse Bits”这道题比较基础。根据题目的要求，每次得到原数最末尾的比特位的值，然后将原数整体向右移动一个比特位，直到移动32个比特位。每次得到末尾比特位的值后累加到最终返回值上即可。

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

• Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

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

以下是Java的题解代码实现。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        
        int res = 0;
        for (int itr=0; itr<32; ++itr) {
            res = res*2+(n&1);
            n >>= 1;
        }
        
        return res;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        
        uint32_t res = 0;
        for (int itr=0; itr<32; ++itr) {
            res = res*2+(n&1);
            n >>= 1;
        }
        
        return res;
    }
};