190 Reverse Bits

来源：Leetcode

原帖：https://leetcode.com/problems/reverse-bits/
            http://articles.leetcode.com/2011/08/reverse-bits.html

题目：
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).
Follow up:
If this function is called many times, how would you optimize it?

思路：

[1]. 使用swap trick，就是交换整数中i-th, j-th bit的位置。这个思路比较容易想到。

The XOR swap trick:
Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits. The trick is to implement a function called swapBits(i, j), which swaps the i^th bit with the j^th bit. If you still remember how XOR operation works: 0 ^ 0 == 0, 1 ^ 1 == 0, 0 ^ 1 == 1, and 1 ^ 0 == 1. We only need to perform the swap when the i^th bit and the j^th bit are different. To test if two bits are different, we could use the XOR operation. Then, we need to toggle both i^th and j^th bits. We could  apply the XOR operation again. By XOR-ing the i^thand j^th bit with 1, both bits are toggled.

代码：

 class Solution {  
 public:  
     void swap(uint32_t& n, int i, int j) {  
         int p_i = ((n >> i) & 1);  
         int p_j = ((n >> j) & 1);  
         if (p_i ^ p_j) {  
             n ^= ((1 << i) | (1 << j));  
         }  
     }  
   
     uint32_t reverseBits(uint32_t n) {  
         int bits = sizeof(n) * 8;  
         for (int i = 0; i < bits/2; i++) {  
             swap(n, i, bits - i - 1);  
         }  
         return n;  
     }  
 };  

[2] 考虑分治法，time complexity O(log(n)).

The divide and conquer approach:Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:

      01101001
        /         \
   0110      1001
    /   \         /   \
 01   10   10   01
 /\     /\     /\     /\
0 1  1 0  1 0   0 1

The first step is to swap all odd and even bits. After that swap consecutive pairs of bits, and so on… Therefore, only a total of log(n) operations are necessary. The below code shows a specific case where n == 32, but it could be easily adapted to larger n‘s as well.

代码：

 class Solution {  
 public:  
     uint32_t reverseBits(uint32_t n) {  
         assert(sizeof(n) == 4);  
         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;  
     }  
 };