【アルゴリズムを学ぼう】#5 基本的なプログラムを作ってみる 4

　増井 敏克著「Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量」で勉強しています。

　だいぶご無沙汰になってしまいました。仕事のプロジェクトの追い込みで色々アレヤコレヤが出てきて毎日午前様で瀕死の状態でした。ブラック企業なのです。

　今回は、本書のColumnの一つの「ビット演算」をやっていきます。

　「ビット演算」というのは、ビット単位で演算していくことを言います。代表的なビット演算には次のようなものがあります。

* ビット反転（NOT）

* 論理積（AND）

* 論理和（OR）

* 排他的論理和（XOR）

　ビット反転は、論理否定ともいわれ、各ビットに対して０は１に、１は０に変換します。例えば、10010の場合は01101となります。

　Pythonでは上の桁が無限に０で埋められていると考えるため、ビット反転すると左側の桁が無限に１で埋められることになり、結果としてビット反転すると正負が反転します。0･･･010010　→　1･･･101101

　論理積は2つの同じ長さのビット列において、同じ位置のビットごとにAND演算をします。つまり、両方とも１の場合は１、いずれかが０の場合は０に変換します。

1010

AND 　1100

＝＝＝＝＝＝＝

1000

　論理和は2つの同じ長さのビット列において、同じ位置のビットごとにOR演算をします。つまり、両方とも０の場合のみ０、いずれかが１の場合は１に変換します。

1010

OR 1100

＝＝＝＝＝＝＝

1110

　排他的論理和は2つの同じ長さのビット列において、同じ位置のビットごとにXOR演算をします。つまり、両方とも同じ場合は０、異なる場合は１に変換します。

1010

XOR 1100

＝＝＝＝＝＝＝

0110

上述のようなビット単位での演算の他に、左右に各ビットを移動する「シフト演算」というものがあります。左に移動するものを「左シフト」、右に移動するものを「右シフト」といいます。

　左シフトは全ての桁を指定された数だけ左に移動させ、一番右の空いた位置には０が入ります。

　２進数で考えると、１ビット左シフトすると２倍、２ビット左シフトすると４倍、３ビット左シフトすると８倍になります。

↓３ビット左にシフト（右端を0で埋める）

print('左1シフト: ' + str(bin(a << 1)))print('左1シフト: ' + str(bin(a << 1)))

0110 （10進数だと6）

0110000 （10進数だと48）

　逆に、右シフトは全ての桁を指定された数だけ右に移動します。１ビット右シフトする度に1/2になります。

↓１ビット右にシフト（右端は切り捨てる）

0110 （10進数だと6）

011 （10進数だと３）

Colaboratoryで実行した結果です。PDFにするまでもないので、ここに貼り付けておきます。

【コード】

a = 0b10010 #0bは２進数を示す接頭辞

b = 0b11001

#ビット反転

print('ビット反転: ' + str(bin(~a)))

#論理積

print('論理積: ' + str(bin(a & b)))

#論理和

print('論理和: ' + str(bin(a | b)))

#排他的論理和

print('排他的論理和: ' + str(bin(a ^ b)))

#左１シフト

print('左1シフト: ' + str(bin(a << 1)))

#右2シフト

print('右2シフト: ' + str(bin(a >> 2)))

【実行結果】

論理積: 0b10000

論理和: 0b11011

排他的論理和: 0b1011

左1シフト: 0b100100

右2シフト: 0b100