LeetCode / Reverse Bits

ビット表現祭り。

https://leetcode.com/problems/reverse-bits/

Reverse bits of a given 32 bits unsigned integer.

Example 1:

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

Example 2:

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

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 signed integer type and should not affect your implementation, as the internal binary representation of the integer 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.

与えられたintegerに相当する32桁のビット表現を逆順にした際の、それに相当するintegerを返す問題です。
Javaではなんだか注意点があるようですが、、、僕はPythonista！関係ない！といつまで言ってられるか分かりませんが、スルーします。

解答・解説

解法1

Pythonでintegerを32桁のビット表現に変換するには、'{0:032b}'.format(n)と表記します。
変数nを32桁のビット表現に変換　→　逆順にソート　→　32桁のビット表現をintに戻す
という処理を行えばOKです。

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        return int('{0:032b}'.format(n)[::-1], 2)

解法2

ビット演算・シフト演算だけで行うことを考えると、以下のように書けます。

class Solution:
    def reverseBits(self, n):
        res = 0
        for _ in range(32):
            res = (res<<1) + (n&1) # res<<1:1桁だけ左にずらし、空いたビットに0が入る, n&1:下1桁の値だけ取り出す
            n>>=1 # n>>1: 1桁だけ右にずらし、押し出された下1桁のビットは消える
        return res

解法3

ビット・シフト演算を利用して、このように書くこともできます。

class Solution:
    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

途中16進数の表現が入っていますが、分かりやすく32ビットの2進数表現に直すと

0xff00ff00 : '11111111000000001111111100000000'
0x00ff00ff : '00000000111111110000000011111111'
0xf0f0f0f0 : '11110000111100001111000011110000'
0x0f0f0f0f : '00001111000011110000111100001111'
（以下略）

のようになっています。

つまり、まず上16桁と下16桁の位置を交換し、次に各々の上8桁と下8桁の位置を交換し、次に各々の上4桁と下4桁の位置を交換し、次に各々の上2桁と下2桁の位置を交換し、次に各々の上1桁と下1桁の位置を交換すると、全体を逆順にしたことになる、というものです。

簡単のために8桁で、各桁の値の移り変わりを見ると、以下のようになります。
abcdefgh -> efghabcd -> ghefcdab -> hgfedcba