1. 7shi

    No comment

    7shi
Changes in body
Source | HTML | Preview
@@ -1,290 +1,315 @@
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進数の各桁に対する計算です。
基本的な考え方は真偽値による処理で、1を真、0を偽と見なします。
## 論理積 (AND)
演算子`&`です。**両方**が真(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'
```
## 論理和 (OR)
演算子`|`です。**どちらか**が真(1)であれば成立(1)します。1桁だけ見れば足し算に似ていますが、計算結果の0以外はすべて1として扱います(2→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'
```
## 排他的論理和 (XOR)
演算子`^`です。**片方だけ**が真(1)であれば成立(1)します(両立しない点が**排他的**)。1桁だけ見れば足し算に似ていますが、計算結果の1以外はすべて0として扱います(2→0)。
XOR |足し算|結果
-----|------|----
0 ^ 0|0 + 0 |0
0 ^ 1|0 + 1 |1
1 ^ 0|1 + 0 |1
1 ^ 1|1 + 1 |2→0
複数桁では繰り上がりなどを一切考えずに、桁ごとに独立して足し算します。1以外はすべて0とします。
```text
10010010
^) 10100111
----------
00110101
```
Pythonで確認します。
```py
>>> bin(0b10010010 ^ 0b10100111)
'0b110101'
```
同じ値で2回XORすると元の値に戻るという性質があります。
* `a ^ b ^ b` == `a`
```py
>>> bin(0b10010010 ^ 0b10100111 ^ 0b10100111)
'0b10010010'
```
# 使用例
ビット演算は一部のビットだけを取り出すときなどによく使われます。
## ビットマスク
ビットのうち必要な部分だけを取り出すとき、必要な部分だけを1にした数とANDします。
例: 101<strong>110</strong>から下位3ビット(太字の部分)を取り出す。
```text
101110
&) 000111
---------
000110
```
### シフトとの併用
途中のビットだけを抜き出したいときはシフトとマスクを併用します。
例: 10<strong>11</strong>10から中央の2ビット(太字の部分)を取り出す。
```py
>>> bin((0b101110 >> 2) & 0b11)
'0b11'
```
## ビットの合成
複数の値を別々の位置に収めたいときはシフトとORを併用します。
例: `101`と`110`を並べて1つの値に合成する。
```py
>>> bin((0b101 << 3) | 0b110)
'0b101110'
```
-## 間違い探し
+### ANDとの併用
-XORを使うと2つの数のうち異なるビットが分かります。
+合成したい箇所に既に別の値が入っている場合は、先にANDで消してからORします。
-```py:
->>> bin(0b11101011101110101 ^ 0b11101101101110101)
-'0b110000000000'
+: 101<strong>101</strong>の下位3ビット(太字の部分)を`011`に置き替える。
+
+```text
+ 101101
+&) 111000
+---------
+ 101000
+|) 011
+---------
+ 101011
+```
+
+Pythonで確認します。
+
+```py
+>>> bin(0b101101 & 0b111000 | 0b011)
+'0b101011'
```
-筆算形式にすると分かりやすいです。
+この手法は画像の生成で背景とキャラクターの合成にも使われます。
+
+## 間違い探し
+
+XORを使うと2つの数のうち異なるビットが分かります。
```text
11101011101110101
^) 11101101101110101
--------------------
00000110000000000
```
+Pythonで確認します。
+
+```py
+>>> bin(0b11101011101110101 ^ 0b11101101101110101)
+'0b110000000000'
+```
+
# 計算との関係
ビット演算ではある種の計算が代用できます。よく使われるものを取り上げます。
## 掛け算
2進数は桁が上がることに値が2倍になります。
2進数 |10進数|左シフト|計算
-----:|----:|----|----
0b1 |1|1 << 0|$2^0$
0b10 |2|1 << 1|$2^1$
0b100 |4|1 << 2|$2^2$
0b1000|8|1 << 3|$2^3$
つまり `1 << n` は $2^n$ と等しいです。
任意の数を1ビット左シフトするごとに2倍になります。
左シフト |掛け算 |出力
---------|------------|----:
bin(5<<0)|bin(5) |'0b101'
bin(5<<1)|bin(5*2) |'0b1010'
bin(5<<2)|bin(5*2*2) |'0b10100'
bin(5<<3)|bin(5*2*2*2)|'0b101000'
つまり『nビットの左シフト』は『$2^n$の掛け算』と同じ結果です。
## 割り算
逆の理屈で『nビットの右シフト』は『$2^n$の割り算(切り捨て)』と同じ結果です。
右シフト |割り算 |出力
---------|------------|----:
bin(45>>0)|bin(45) |'0b101101'
bin(45>>1)|bin(45/2) |'0b10110'
bin(45>>2)|bin(45/2/2) |'0b1011'
bin(45>>3)|bin(45/2/2/2)|'0b101'
## 割り算の余り
『$2^n$ による割り算の余り』は『$2^n-1$とのAND』に等しいです。
* `x % (2 ** n)` == `x & ((2 ** n) - 1)`
例: `x % 8` == `x & 7`
### 説明
これが成り立つ理由をなるべく直感的に説明します。
`0b110101`を3ビット右シフトするのは、$2^3=8$で割って切り捨てたのと等しいです。
```py
>>> bin(0b110101 >> 3)
'0b110'
>>> bin(0b110101 / 8)
'0b110'
```
このときにシフトで押し出された下位3ビット`101`が割り算の余りに相当します。`111`でマスクすると取り出せます。
```py
>>> bin(0b110101 & 0b111)
'0b101'
>>> bin(0b110101 % 8)
'0b101'
```
`0b111`は`7`で、つまり`8-1`です。これにより次の関係を確認しました。
* `x % 8` == `x & 7`
# おわりに
よく使うビット演算は以上です。
反転(NOT)もよく使いますが、符号が絡んで多少面倒なため、また機会があれば説明を書きたいと思います。