Reverse Bits 续

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

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

Related problem: Reverse Integer

 

有了前面的python实现，再来考虑C更顺利一些

10        00……001010  前面有32  – len(bin) = 28个0

颠倒后 010100……00  后面有32 – len(bin) = 28个0

而如果要计算二进制的位数，可以通过十进制数字不停除以2，直到商为0，余数是二进制逆序位，而除法的次数也就是二进制位长度

正巧除法过程中，余数是二进制逆着的，那么计算颠倒后二进制的十进制数，实际上就是原除法顺着的余数来计算十进制，意思就是

10 % 2 = 0 本来低1位，颠倒后高1位

5 % 2 = 1 本来低2位，颠倒后高2位

2 % 2 = 0 本来低3位，颠倒后高3位

1 % 2 = 1 本来低4位，颠倒后高4位，此时商为0，length也是4

颠倒后十进制计算：0 * 2 ^ (32 – 1) + 1 * 2 ^ (32 – 2) + 0 * 2 ^ (32 – 3) + 1 * 2 ^ (32 – 4)

而32 – i中的 i 正好是递增的位数，不停除，然后将有效位计算出来求和即可

第一次提交

uint32_t reverseBits(uint32_t n) {
        int a;
        int length = 0;
        uint32_t sum = 0;
        while (n){
                ++length;
                a = n % 2;
                n = n >> 1;
                sum += a * foo(32 - length);
        }
        return sum;
}

int foo (int n){
        if (n == 0)
                return 1;
        else
                return 2 * foo(n - 1);
}

惊奇的是一次通过了

600 / 600 test cases passed.
Status: Accepted
Runtime: 6 ms

但是这里要注意返回类型，如果觉得32不好看，可以define设置一个宏~！