leetcode-190-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 as 00111001011110000010100101000000).

分析

又一道位操作的题目。位操作总是显得比较像奇技淫巧，所以，先写一个常规版本，再搜索学习一下咯~

解决方案1(C++)

这个算是最常规的版本的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        uint32_t num[32];
        
        for(int i = 0; i < 32; i++) {
            num[i] = (n>>i) & 1;
        }
        uint32_t temp = 1;
        for(int i = 31; i >= 0; i--) {
            result += num[i]*temp;
            temp = temp<<1;
        }
        return result;
    }
};

当然这段代码可以优化，取得最末位的数后，直接移到最高位

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for(int i = 0; i < 32; i++) {
            result += ((n>>i)&1)<<(31-i);
        }
        return result;
    }
};

在article.leetcode.com看到了一种分治法的思路，交换的方式可以参考归并排序的做法，如：

1
2
3
4
5
6
7
      01101001
    /         \
   0110      1001
  /   \     /   \
 01   10   10   01
 /\   /\   /\   /\
0 1  1 0  1 0  0 1

先两两交换，相邻的两个两个交换，四个四个交换……
代码是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        assert(sizeof(n) == 4); // special case: only works for 4 bytes (32 bits).
        n = ((n & 0x55555555) << 1) | ((n & 0xAAAAAAAA) >> 1);
        n = ((n & 0x33333333) << 2) | ((n & 0xCCCCCCCC) >> 2);
        n = ((n & 0x0F0F0F0F) << 4) | ((n & 0xF0F0F0F0) >> 4);
        n = ((n & 0x00FF00FF) << 8) | ((n & 0xFF00FF00) >> 8);
        n = ((n & 0x0000FFFF) << 16) | ((n & 0xFFFF0000) >> 16);
        return n;
    }
};

于是，复杂度从O(n)变成了O(log(n))，优化是优化了，然而工程上大概不会写这种代码，因为，，，代码是写给人看的←_←

解决方案2(Python)

在Python中就有各种函数啦 

1
2
3
4
5
6
7
class Solution(object):
    def reverseBits(self, n):
        """
        :type n: int
        :rtype: int
        """
        return int(bin(n).lstrip('0b').zfill(32)[::-1],2)

相关问题

(E) Number of 1 Bits

题目来源