1. 7shi

    Posted

    7shi
Changes in title
+Python ビット演算 超入門
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,181 @@
+2進数に対して行うビット演算の初歩を説明します。説明にはPythonを使用します。
+
+# 2進数
+
+`0b`を付けて記述します。REPLで入力すると10進数に変換されます。
+
+```py
+>>> 0b101
+5
+```
+
+2進数に変換するには`bin()`を使います。
+
+```py
+>>> bin(5)
+'0b101'
+```
+
+## 16進数
+
+元の数値を16進数で記述すれば、16進数から2進数に変換できます。
+
+```py
+>>> bin(0x12)
+'0b10010'
+```
+
+16進数に変換するには`hex()`を使います。
+
+```py
+>>> hex(0b10010)
+'0x12'
+```
+
+# シフト
+
+桁をずらします。方向により左シフトと右シフトがあります。
+
+## 左シフト
+
+演算子`<<`です。指定した桁だけ左にずらして、空いたビットには0が入ります。
+
+右揃えに整形して例を示します。
+
+入力 |出力
+---------|----:
+bin(5<<0)|'0b101'
+bin(5<<1)|'0b1010'
+bin(5<<2)|'0b10100'
+bin(5<<3)|'0b101000'
+
+## 右シフト
+
+演算子`>>`です。指定した桁だけ右にずらして、最下位より先に押し出されたビットは消えます。
+
+右揃えに整形して例を示します。
+
+入力 |出力
+---------|----:
+bin(5>>0)|'0b101'
+bin(5>>1)|'0b10'
+bin(5>>2)|'0b1'
+bin(5>>3)|'0b0'
+
+## 掛け算と割り算
+
+2進数は桁が上がることに値が2倍になります。
+
+2進数 |10進数
+-----:|----:
+0b1 |1
+0b10 |2
+0b100 |4
+0b1000|8
+
+任意の数を1ビット左シフトするごとに2倍になります。
+
+入力1 |入力2 |出力
+------------|---------|----:
+bin(5*1) |bin(5<<0)|'0b101'
+bin(5*2) |bin(5<<1)|'0b1010'
+bin(5*2*2) |bin(5<<2)|'0b10100'
+bin(5*2*2*2)|bin(5<<3)|'0b101000'
+
+つまり$2^n$の掛け算はnビットの左シフトで表現できます。
+
+逆の理屈で$2^n$の割り算(切り捨て)はnビットの右シフトで表現できます。
+
+# 論理演算
+
+2進数の各桁に対する計算です。
+
+基本的な考え方は真偽値による処理で、1を真、0を偽と見なします。
+
+## 論理積
+
+演算子`&`です。両方が真(1)のときにしか成立(1)しないので、1桁だけ見れば掛け算となります。
+
+AND |掛け算|結果
+-----|------|:--:
+0 & 0|0 * 0 | 0
+0 & 1|0 * 1 | 0
+1 & 0|1 * 0 | 0
+1 & 1|1 * 1 | 1
+
+複数桁では繰り上がりなどを一切考えずに、桁ごとに独立して掛け算します。
+
+```text
+ 10010010
+&) 10100111
+----------
+ 10000010
+```
+
+Pythonで確認します。
+
+```py
+>>> bin(0b10010010 & 0b10100111)
+'0b10000010'
+```
+
+## 論理和
+
+演算子`|`です。どちらかが真(1)であれば成立(1)しますが、1桁だけ見れば足し算に似ていますが、計算結果は0以外はすべて1として扱います。
+
+<table><tr><th>OR</th><th>足し算</th><th>結果</th></tr><tr><td>0 | 0</td><td>0 + 0</td><td>0</td></tr><tr><td>0 | 1</td><td>0 + 1</td><td>1</td></tr><tr><td>1 | 0</td><td>1 + 0</td><td>1</td></tr><tr><td>1 | 1</td><td>1 + 1</td><td>2→1</td></tr></table>
+
+複数桁では繰り上がりなどを一切考えずに、桁ごとに独立して足し算します。0以外はすべて1とします。
+
+```text
+ 10010010
+|) 10100111
+----------
+ 10110111
+```
+
+Pythonで確認します。
+
+```py
+>>> bin(0b10010010 | 0b10100111)
+'0b10110111'
+```
+
+## ビットマスク
+
+ビットのうち必要な部分だけを取り出すとき、必要な部分だけを1にした数と`&`します。
+
+例: 101*110*から下位3ビットだけを取り出す
+
+```text
+ 101110
+&) 000111
+---------
+ 000110
+```
+
+### シフトとの併用
+
+途中のビットだけを抜き出したいときはシフトとマスクを併用します。
+
+例: 10*11*10から中央の2ビットだけを取り出す
+
+```py
+>>> bin((0b101110 >> 2) & 0b11)
+'0b11'
+```
+
+## ビットの合成
+
+複数の値を別々の位置に収めたいときはシフトと論理和を併用します。
+
+例: `101`と`110`を並べて1つの値にする
+
+```py
+>>> bin((0b101 << 3) | 0b110)
+'0b101110'
+```
+
+# おわりに
+
+よく使うビット演算は以上です。その他にもNOTや排他的論理和などありますが、必要に応じて覚えていけば良いでしょう。