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设置一个宏~!

发表评论