Reversing bits in Python

Python: ビットの逆転

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

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

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

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

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

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

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

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

>>> 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倍近く遅くなっていた。

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

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

>>> 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