1. 7shi

    No comment

    7shi
Changes in body
Source | HTML | Preview
@@ -1,435 +1,435 @@
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桁だけ見れば足し算に似ていますが、計算結果の1以上はすべて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>
複数桁では繰り上がりを一切考えずに、桁ごとに独立して足し算します。計算結果の1以上はすべて1として扱います(2→1)。
```text
10010010
|) 10100111
-----------
10110111
```
Pythonで確認します。
```py
>>> bin(0b10010010 | 0b10100111)
'0b10110111'
```
## 排他的論理和 (XOR)
演算子`^`です。**片方だけ**が真(1)であれば成立(1)します(両立しない点が**排他的**)。2進数1桁だけ見れば繰り上りを捨てる足し算です(1+1=2=0b10 → 0)。
XOR |足し算|結果
-----|------|----
0 ^ 0|0 + 0 |0
0 ^ 1|0 + 1 |1
1 ^ 0|1 + 0 |1
1 ^ 1|1 + 1 |2→0
複数桁では繰り上がりを一切考えずに、桁ごとに独立して足し算します。
```text
10010010
^) 10100111
-----------
00110101
```
Pythonで確認します。
```py
>>> bin(0b10010010 ^ 0b10100111)
'0b110101'
```
同じ値で2回XORすると元の値に戻るという性質があります。
* `a ^ b ^ b` → `a`
```py
>>> bin(0b10010010 ^ 0b10100111 ^ 0b10100111)
'0b10010010'
```
元の値を消すこともできます。
* `a ^ b ^ a` → `b`
```py
>>> bin(0b10010010 ^ 0b10100111 ^ 0b10010010)
'0b10100111'
```
## 反転 (NOT)
演算子`~`です。0と1を逆にします。
Pythonでは上の桁が無限に0で埋められていると見なして、反転も上の桁が無限に1で埋められているという想定でマイナスを返します。
```py
>>> ~1
-2
```
この計算は `000...0001` → `111...1110` を意味しています。
後でANDとNOTの組み合わせで見るように、通常はビットだけに注目して具体的な数値(ここではマイナス)は意識しません。符号の考え方について興味がある方は次の記事を参照してください。
* [@7shi](https://twitter.com/7shi): [符号あり数値の直感的な考え方](http://qiita.com/7shi/items/6887e7939c0168a0eb21) 2014.10.8
※ 値だけに注目して `~x`→`-(x+1)` という式が紹介されることもあります。これを見てもビット反転の意味が分からないので、ここでは深く追求しません。
# 使用例
ビット演算は一部のビットだけを取り出すときなどによく使われます。
## ビットマスク
ビットのうち必要な部分だけを取り出すとき、必要な部分だけを1にした数とANDします。
例: 101<strong>110</strong>から下位3ビット(太字の部分)を取り出す。
```text
101110
&) 000111
---------
000110
```
### シフトとの併用
途中のビットだけを抜き出したいときはシフトとマスクを併用します。
例: 10<strong>11</strong>10から中央の2ビット(太字の部分)を取り出す。
```py
>>> bin((0b101110 >> 2) & 0b11)
'0b11'
```
### NOTとの併用
ANDと組み合わせてNOTを使う場合、NOTの結果がマイナスになることは気にしないで使えるということを示します。
NOTの計算結果をANDでマスクすれば、桁数を限定してマイナスを排除できます。
```py
>>> bin(~1 & 0b1111)
'0b1110'
```
この計算は2進数4桁に限定することで `0001` → `1110` という反転を示しています。
NOTはマスク値の作成に使うことが多く、その場合もマイナスのことは意識しません。
-例えば10<string>10</strong>10の中央の2ビット(太字の部分)だけを消したい場合、NOTを使うことで消したい部分に注目したコードとなります。
+例えば10<strong>11</strong>10の中央の2ビット(太字の部分)だけを消したい場合、NOTを使うことで消したい部分に注目したコードとなります。
```py
->>> bin(0b101010 & ~0b001100)
+>>> bin(0b101110 & ~0b001100)
'0b100010'
```
比較対象としてNOTを使わないコードを示します。残したい部分に注目しています。
```py
->>> bin(0b101010 & 0b110011)
+>>> bin(0b101110 & 0b110011)
'0b100010'
```
## ビットの合成
複数の値を別々の位置に収めたいときはシフトとORを併用します。
例: `101`と`110`を並べて1つの値に合成する。
```py
>>> bin((0b101 << 3) | 0b110)
'0b101110'
```
### ANDとの併用
合成したい箇所に既に別の値が入っている場合は、先にANDで消してからORします。
例: 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'
```
## 値の入れ替え
【注】実用性というより、知識としての紹介です。
多重XORの応用で、変数の値を交換するテクニックがあります。
* [XOR交換アルゴリズム - Wikipedia](http://ja.wikipedia.org/wiki/XOR%E4%BA%A4%E6%8F%9B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)
Pythonで確認します。
```py
>>> a = 12
>>> b = 34
>>> a, b
(12, 34)
>>> a = a ^ b
>>> b = a ^ b
>>> a = a ^ b
>>> a, b
(34, 12)
```
実用上はタプルを使った方が簡単です。
```py
>>> a, b = b, a
```
# 計算との関係
ビット演算ではある種の計算が代用できます。よく使われるものを取り上げます。
## 掛け算
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`
## 切り下げ
『下位nビットのクリア』は『$2^n$での切り下げ』に相当します。
例としてシフトによる$2^3=8$での切り下げを示します。右シフトで下位3ビットを押し出して、左シフトで元のビット幅に戻しています。
```py
>>> 15 >> 3 << 3
8
>>> 16 >> 3 << 3
16
>>> 17 >> 3 << 3
16
```
特定のビットを消すのはANDとNOTの組み合わせでも可能です。最初は分かりにくいかもしれませんが、シフトよりもこの方法がよく使われます。
```py
>>> 15 & ~0b111
8
>>> 16 & ~0b111
16
>>> 17 & ~0b111
16
```
`0b111`は`7`で、つまり`8-1`です。これは先に見た余りを求める方法にも出て来た関係です。
`~7` → `-8` の関係を使うと、8での切り下げを-8で表現できます。
```py
>>> 15 & -8
8
>>> 16 & -8
16
>>> 17 & -8
16
```
これを初めて見ると意味が分からないかもしれません。とりあえず「こういう式で表記することもある」とだけ認識しておけば良いです。