bit_reverse.py の技術ドキュメント

プログラムの動作

bit_reverse.py は、与えられた整数のバイナリ表現におけるビット列を反転する機能を提供するPythonスクリプトです。このプログラムは、以下の目的と機能を持っています。

目的: 特定の整数値のバイナリビット列の順序を逆転させること。これは、データ処理、暗号化、特定のアルゴリズム実装などの場面で必要となる場合があります。
主な機能:
- bit_reverse 関数を定義し、この関数が任意の整数値のビット列を反転します。例えば、0b110001 (10進数で49) を入力すると、0b100011 (10進数で35) が出力されます。
- コマンドライン引数としてバイナリ文字列（例: "110001"）を受け取り、それを整数値として解釈してビット反転処理を行います。
- コマンドライン引数が指定されない場合は、プログラムにハードコードされたデフォルト値 0b110001 (10進数で49) を使用します。
解決する課題: ビットの最下位から最上位への順序を逆転させたい場合に、簡単かつ動的にビット列を反転させる手段を提供します。

原理

bit_reverse.py の中核である bit_reverse 関数は、ビットシフトとビット論理演算を組み合わせてビット列を反転させます。この関数は、入力された整数値 val の最下位ビット (LSB) から順にビットを取り出し、それらを新しい整数値 ret の最下位ビットとして積み重ねていくことで、元のビット列が反転された結果を生成します。

アルゴリズムの動作は以下のステップで行われます。

ret (反転結果を格納する変数) を 0 で初期化します。
while ループを開始し、val が 0 になるまで繰り返します。
- v0 = val & 0b001: val の現在の最下位ビット (LSB) を抽出します。0b001 (10進数で1) とのビットAND演算により、LSBが1であれば 1、0であれば 0 が v0 に格納されます。
- ret = ret | v0: 抽出された v0 を ret の現在のLSBにセットします。これは、v0 が ret の最下位ビット位置に追加されることを意味します。
- val = val >> 1: val を1ビット右にシフトします。これにより、次のビットがLSBの位置に移動し、次のループで処理される準備ができます。
- if val == 0: break: val が 0 になった場合、すべてのビットが処理されたことを意味するため、ループを終了します。
- else: ret = ret << 1: val がまだ 0 でない場合、ret を1ビット左にシフトします。これにより、これまでに ret に格納されたビットが左に移動し、次の v0 のために ret のLSBが空けられます。

このプロセスにより、元の val のLSBが最終的な ret のMSB (最上位ビット) に近い位置に、元の val のMSBが最終的な ret のLSBに近い位置に配置され、ビット列の反転が実現されます。

例: val = 0b110001 (10進数で49) の場合

初期状態: val = 0b110001, ret = 0b0
1. v0 = 1. ret = 0b0 | 1 = 0b1. val = 0b11000. (val != 0 なので) ret = 0b1 << 1 = 0b10.
1. v0 = 0. ret = 0b10 | 0 = 0b10. val = 0b1100. (val != 0 なので) ret = 0b10 << 1 = 0b100.
1. v0 = 0. ret = 0b100 | 0 = 0b100. val = 0b110. (val != 0 なので) ret = 0b100 << 1 = 0b1000.
1. v0 = 0. ret = 0b1000 | 0 = 0b1000. val = 0b11. (val != 0 なので) ret = 0b1000 << 1 = 0b10000.
1. v0 = 1. ret = 0b10000 | 1 = 0b10001. val = 0b1. (val != 0 なので) ret = 0b10001 << 1 = 0b100010.
1. v0 = 1. ret = 0b100010 | 1 = 0b100011. val = 0b0. (val == 0 なので) ループ終了。

結果: ret = 0b100011 (10進数で35)

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

bit_reverse.py はPythonの標準ライブラリである sys のみを使用しており、追加の非標準ライブラリを必要としません。したがって、pip コマンドなどを使った特別なインストール作業は不要です。

必要な入力ファイル

このプログラムは、入力ファイルを必要としません。必要なデータ（ビット反転を行う整数値）は、以下のいずれかの方法で提供されます。

コマンドライン引数: プログラム実行時に、"110001" のようなバイナリ文字列として直接引数に与えることができます。この文字列は、内部で int(sys.argv[1], 2) を使って2進数として解釈されます。
プログラム内のデフォルト値: コマンドライン引数が提供されない場合、プログラムのソースコード内にハードコードされたデフォルト値 0b110001 (10進数で49) が使用されます。

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

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

出力される内容は以下の通りです。

入力された10進数 (Base 10 input: )
入力された2進数 (Base 2: )
ビット反転後の10進数 (reversed in Base 10 = )
ビット反転後の2進数 (reversed in Base 2 = )

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

bit_reverse.py をコマンドラインから実行する際の基本的な形式は以下の通りです。

python bit_reverse.py [バイナリ文字列]

python bit_reverse.py: 引数を指定しない場合、プログラム内のデフォルト値 0b110001 (10進数で49) が使用されます。
python bit_reverse.py <バイナリ文字列>: <バイナリ文字列> には、"10110" のような 0b プレフィックスを含まないバイナリ表現の文字列を指定します。この文字列が整数値として解釈され、ビット反転されます。

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

1. 引数を指定せずに実行する例

コマンドライン引数を指定しない場合、プログラムはデフォルト値 0b110001 (10進数で49) を使用してビット反転を行います。

python bit_reverse.py

実行結果:

Base 10 input:  49
Base 2: 110001
reversed in Base 10 = 35
         in Base 2  = 100011

説明: 入力値はデフォルトの 0b110001 (10進数で49) であり、そのビット列を反転した結果は 0b100011 (10進数で35) となっています。

2. 特定のバイナリ文字列を引数として指定して実行する例

"10110" というバイナリ文字列を引数として与える例です。これは10進数で22に相当します。

python bit_reverse.py 10110

実行結果:

Base 10 input:  22
Base 2: 10110
reversed in Base 10 = 13
         in Base 2  = 1101

説明: 入力値は 0b10110 (10進数で22) です。そのビット列を反転した結果は 0b01101 となり、先頭の 0 は表示されないため 0b1101 (10進数で13) と表示されます。