bit_reverse_compare.py 技術ドキュメント

プログラムの動作

bit_reverse_compare.py は、Pythonで符号なし整数のビット列を反転する複数のアルゴリズムを実装し、それらの実行速度を比較するためのプログラムです。

主な機能は以下の通りです。

ビット反転アルゴリズムの実装:
- ビット演算子（&, |, >>, <<）を使用してビット反転を行う bit_reverse 関数。
- 算術演算子（%, //, +, *）を使用してビット反転を行う bit_reverse_nobitop 関数。
- 算術演算子と複合代入演算子（+=, //=）を使用する bit_reverse_nobitop2 関数。
初期値の表示: コマンドライン引数で与えられた、またはデフォルトで設定された入力値を10進数と2進数で表示します。
反転結果の表示: 各アルゴリズムで計算されたビット反転結果を10進数と2進数で表示し、正しく動作していることを確認します。
パフォーマンス比較: 各ビット反転関数を指定された繰り返し回数実行し、それぞれの処理時間を計測・表示することで、アルゴリズム間の効率を比較します。

このプログラムは、ビット演算と算術演算のどちらがビット操作において効率的であるかという課題を解決するために役立ちます。

原理

ビット反転とは、与えられた数値の2進数表現において、ビットの並びを逆順にすることです。例えば、10110 (10進数の22) のビット反転は 01101 (10進数の13) となります。

本プログラムで実装されているビット反転アルゴリズムの基本的な考え方は以下の通りです。

入力された数値の最下位ビットを1ビットずつ取り出します。
取り出したビットを、結果となる数値の最上位ビットから順に配置していきます。

これをループで実現するために、以下の手順を繰り返します。

最下位ビットの抽出:
- bit_reverse 関数では、ビットAND演算 (val & 0b001) を用いて最下位ビットを抽出します。
- bit_reverse_nobitop および bit_reverse_nobitop2 関数では、剰余演算 (val % 2) を用いて最下位ビットを抽出します。
入力数値のシフト: 最下位ビットを取り出した後、次のビットを最下位にするために、入力数値を1ビット右にシフトします。
- bit_reverse 関数では、右シフト演算 (val = val >> 1) を使用します。
- bit_reverse_nobitop および bit_reverse_nobitop2 関数では、整数除算 (val = val // 2 または val //= 2) を使用します。
結果数値の構築: 取り出したビットを結果に加える前に、結果を1ビット左にシフトして新しいビットのためのスペースを確保し、その後取り出したビットを加えます。
- bit_reverse 関数では、左シフト演算 (ret = ret << 1) とビットOR演算 (ret = ret | v0) を使用します。
- bit_reverse_nobitop および bit_reverse_nobitop2 関数では、乗算 (ret = ret * 2 または ret *= 2) と加算 (ret = ret + v0 または ret += v0) を使用します。
終了条件: 入力数値が0になったらループを終了します。

数式で表現すると、ある整数 \(V\) が2進数で \(V = b_N 2^N + b_{N-1} 2^{N-1} + \dots + b_1 2^1 + b_0 2^0 = \sum_{i=0}^N b_i 2^i\) と表現される場合、そのビット反転された整数 \(V_{rev}\) は \(V_{rev} = b_0 2^N + b_1 2^{N-1} + \dots + b_{N-1} 2^1 + b_N 2^0 = \sum_{i=0}^N b_{N-i} 2^i\) となります。アルゴリズムはこの変換を効率的に実行するものです。

必要な非標準ライブラリとインストール方法

このプログラムはPythonの標準ライブラリである sys と time のみを使用しています。そのため、特別な非標準ライブラリをインストールする必要はありません。

必要な入力ファイル

bit_reverse_compare.py はファイル入力を必要としません。すべての入力はコマンドライン引数として直接プログラムに渡されます。

生成される出力ファイル

bit_reverse_compare.py は、実行によっていかなるファイルも生成しません。すべての処理結果は標準出力（コンソール）に直接表示されます。

コマンドラインでの使用例 (Usage)

bit_reverse_compare.py は以下の形式でコマンドラインから実行できます。

python bit_reverse_compare.py [2進数文字列] [繰り返し回数]

[2進数文字列]: ビット反転の対象となる数値を2進数表現の文字列で指定します。例えば、1101 のように指定します。この引数を省略した場合、プログラム内部で定義されているデフォルト値 0b1100011011000110110001101100011110001101100011011000110110001101 が使用されます。
[繰り返し回数]: パフォーマンス計測のための、各ビット反転関数を呼び出す繰り返し回数を整数で指定します。例えば、1000000 のように指定します。この引数を省略した場合、デフォルト値の 100000 が使用されます。

コマンドラインでの具体的な使用例

例1: デフォルト値での実行

コマンドライン引数を一切指定せず、プログラム内部のデフォルト値で実行します。

python bit_reverse_compare.py

実行結果（例）:

Base 10 input:  14389081559132205565
Base 2: 1100011011000110110001101100011110001101100011011000110110001101

by bitwise operation
reversed in Base 10 = 14389081559132205565
         in Base 2  = 1100011011000110110001101100011110001101100011011000110110001101
without bitwise operation
reversed in Base 10 = 14389081559132205565
         in Base 2  = 1100011011000110110001101100011110001101100011011000110110001101

Time for 100000 iterations
by bitwise operation     : 0.057864 s
by bitwise operation (list incl): 0.057929 s
without bitwise operation: 0.076848 s
without bitwise operation #2: 0.076935 s

説明: デフォルトの入力値 (大きな2進数) がビット反転され、その結果が10進数と2進数で表示されます。その後、各ビット反転関数を100,000回実行した際の処理時間が計測・比較されます。この例では、ビット演算を使用する bit_reverse 関数が算術演算を使用する方法よりも高速であることが示されています（時間は実行環境によって変動します）。

例2: 特定の2進数と繰り返し回数を指定して実行

入力値として 101101 (10進数の45) を、繰り返し回数として 1000000 を指定して実行します。

python bit_reverse_compare.py 101101 1000000

実行結果（例）:

Base 10 input:  45
Base 2: 101101

by bitwise operation
reversed in Base 10 = 53
         in Base 2  = 110101
without bitwise operation
reversed in Base 10 = 53
         in Base 2  = 110101

Time for 1000000 iterations
by bitwise operation     : 0.301234 s
by bitwise operation (list incl): 0.301298 s
without bitwise operation: 0.405678 s
without bitwise operation #2: 0.405789 s

説明: 入力された 101101 (10進数で45) がビット反転され、その結果である 110101 (10進数で53) が表示されます。繰り返し回数が1,000,000回に設定されているため、より長い時間計測が行われ、ビット演算と算術演算のパフォーマンス差が明確に比較されます。この結果も、ビット演算子を使用する bit_reverse が効率的であることを示唆しています。