leetcode筆記：Reverse Bits

leetcode筆記：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).

二. 題目分析

題目的要求比較簡單，輸入一個32位的無符號整數，根據其二進制表示，輸出與其二進制相對稱的無符號整數。題目也給出了一個例子。

該題使用基本的位運算即可解決，當然網上也提出了一種很巧妙的方法，其中對於位運算有這樣的一種方法，將數字的位按照整塊整塊的翻轉，例如32位分成兩塊16位的數字，16位分成兩個8位進行翻轉，以此類推。

對於一個8bit數字abcdefgh來說，其處理過程如下：

abcdefgh -> efghabcd -> ghefcdab -> hgfedcba

進一步的論述，抄送網上的解釋：

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) {
        uint32_t result = 0;
        if (n == result) return result;
        int index = 31; // 初始時n的最低位需要右移31位到最高位
        while (n)
        {
            result |= (n & 0x1) << index; // 取n的最低位，並右移到高位
            --index; // 右移位數，保持對稱
            n >>= 1; 
        }
        return result;
    }
};

// 另一種巧妙的做法
/*
0x55555555 = 0101 0101 0101 0101 0101 0101 0101 0101
0xAAAAAAAA = 1010 1010 1010 1010 1010 1010 1010 1010
0x33333333 = 0011 0011 0011 0011 0011 0011 0011 0011
0xCCCCCCCC = 1100 1100 1100 1100 1100 1100 1100 1100
*/
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t x = n;
        x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
        x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
        x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
        x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
        x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
        return x;
    }
};

四. 小結

實現該題的要求不難，但是精彩的做法讓人大開眼界。