動機

神奇的位元操作

Problem

Reverse bits of a given 32 bits unsigned integer.

Note:

  • Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

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

 

Example 1:

Input: n = 00000010100101000001111010011100Output:    964176192 (00111001011110000010100101000000)Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: n = 11111111111111111111111111111101Output:   3221225471 (10111111111111111111111111111111)Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

 

Constraints:

  • The input must be a binary string of length 32

Sol1: reverse by bit

就一般的reverse

class Solution:
    def reverseBits(self, n: int) -> int:
        n = list(format(n,'b').zfill(32))
        for i in range(16):
            tmp = n[i]
            n[i] = n[31-i]
            n[31-i] = tmp
        return int(''.join(n),2)

Sol2: reverse by byte

在ref中有在不用shift的byte reverse，因為變成byte，所以可能會看過重複的

進而可以用記憶法!!

這真的很有趣，在bit下就不能用記憶法，但是如果包成byte就可以用記憶法了，有趣!!

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        ret, power = 0, 24
        while n:
            ret += self.reverseByte(n & 0xff) << power
            n = n >> 8
            power -= 8
        return ret

    # memoization with decorator
    @functools.lru_cache(maxsize=256)
    def reverseByte(self, byte):
        return (byte * 0x0202020202 & 0x010884422010) % 1023

Sol3: divide & conquer

切兩半，再交換，藉著在每個分區都做一樣的事

不過因為是固定32位，所以可以直接用shift

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        n = (n >> 16) | (n << 16)
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
        return n

Sol4: push

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = 0;
        for (int i=0; i<31; i++, n >>= 1, ret <<= 1) {
                ret = ret | (n&1);
        }
        if (n)
            ret = ret | (n&1);
        return ret;
    }
};

Ref

Bit Twiddling Hacks