Leetcode 190 @ Reverse Bits

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?

刚一看到题目，都没反应过来reverse一个bit啥意思，其实就是和reverse string一个意思，把一个32位 unsigned integer的二进制表示首位反过来，reverse。一旦理解了题意，那么题目就简单了。取个res = 0，每次都看n的最低位是0 or 1，如果是0， 就给res左移一位，如果是1，就左移一位，加上1，相当于把n的bit value给了res, 之后n再右移一位。

res不断左移，n不断右移，共32位，所以for loop 32次，这样完成后就正好是reverse的。

题目的follow up说优化，我觉得我这个已经挺好的了，也没占额外内存，时间复杂度也就是扫一遍。我不太喜欢那种one liner，秀syntax，很不straight forward。我的逻辑是，在优化performance的前提下，让代码的可读性尽量高，最好一眼就能读出这段代码在做什么。

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