Reversing bits in Python

Python: ビットの逆転

敢えて Hacker's Delight 的なことはせずに。

・bin(x)[2:] は、format(x, 'b') と書き直せることを知った。（しかし実行速度は遅かった・・・後述）
　つまり、10進数(int/long int)から2進数(string)への変換は以下でよい。

1 2 3 4

>>> format(100, 'b') '1100100' >>> format(100, '032b') '00000000000000000000000001100100'

・文字列反転のテクニック。

1 2 3 4

>>> 'abcdefgh'[::-1] 'hgfedcba' >>> print unicode('ほあんいんぜんいんあほ', 'sjis')[::-1]  # palindrome ほあんいんぜんいんあほ

・2進数(string)から10進数(int/long int)に戻すには、int のコンストラクタに base を指定すればよい。

1 2	>>> int('1100100', 2) 100

これらを踏まえたコード
非負整数 x (0 <= x < 2**n) に対して rightmost-bit から連続する n ビットを逆転
（ x >= 2**n の場合の動作は保証されない）
分かりやすくするため、最後に16進数で表示している。

1 2 3 4 5 6 7 8 9

>>> x, n = 1, 81 >>> '%x' % int(format(x, '0%db' % n)[::-1], 2) '100000000000000000000' >>> x, n = 2**80, 81 >>> '%x' % int(format(x, '0%db' % n)[::-1], 2) '1' >>> x, n = 2**81-1, 81 >>> '%x' % int(format(x, '0%db' % n)[::-1], 2) '1ffffffffffffffffffff'

将棋のビットボードを逆転させるとこのようになる。先手・後手の盤面逆転に使えそうだ。

反転前	反転後
--------* ----***-* *-----**- *---*-*-* *-**-***- *-***-*-- ***-*---- ***---*-- -*-------	-------*- --*---*** ----*-*** --*-***-* -***-**-* *-*-*---* -**-----* *-***---- *--------

ちなみに、10進数から2進数への変換処理がどちらが速いか計測してみたところ、
意外にも format は bin に比べて 2倍近く遅くなっていた。

1 2 3 4

>>> min(timeit.Timer("bin(2**81-1)[2:]").repeat(3)) 0.668876910333438 >>> min(timeit.Timer("format(2**81-1, 'b')").repeat(3)) 1.2742180919640305

ビット逆転のコードも書きなおしてみる。

1 2 3 4

>>> min(timeit.Timer("int(format(2**81-1, '0%db' % 81)[::-1], 2)").repeat(3)) 3.1991761522763795 >>> min(timeit.Timer("int(bin(2**81-1)[2:].zfill(81)[::-1], 2)").repeat(3)) 2.620784764544055