ビット演算

ビット演算
〜 アルゴリズムとデータ構造及び演習 〜
２進数
計算機のデータはすべて２進数で扱われる
最上位ビットを MSB (Most Significant Bit)、最下位
ビットを LSB (Least Significant Bit) と呼ぶ。
0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 0 1 0
↑
↑
MSB
LSB
整数として見ると上の例は(10進数で)10
3
2
×1+
2
2
×0+
1
2
×1+
0
2
× 0 = 10
ビット演算
２進データを０と１のビットの列（ビットパターン）
と⾒て、これに対する操作を⾏う。
整数値に逐⼀還元して考える必要はない。
C⾔語には、ビットパターンを操作するための演算
⼦が⽤意されている。
• ビットごとの積(AND)
• 和(OR)、排他的論理和(XOR: exclusive OR)
• 否定(NOT)
• シフト演算
どんな時にビット演算が必要か (1)
OSや周辺機器とやりとりするデータは、１ワード内
にビット単位で情報が格納されていることがある。
• 例：UNIXの stat() が返すファイル情報の⼀部
1 0 0 0 0 0 0 １ 1 0 １ 0 0 １０ 0
rwx rwx rwx
ファイルの種類
他人のアクセス
グループ内のアクセス
set user id
所有者のアクセス
set group id
sticky bit
どんな時にビット演算が必要か (2)
ビット単位で表現されたデータを扱う場合。例えば、
画像データは数ビットで１画素を表すことがある。
通信のための符号化や圧縮、暗号化の処理はビット
の列に対して処理を⾏う。
⼀般に、ビット演算は四則演算よりも⾼速なため、
計算の⼀部を（可能なら）ビット演算で置き換える
ことがある。
８進数、16進数
２進数そのままでは扱いにくいので、プログラムでは８
進数や16進数として表記する。
C⾔語では、037 のように数値を０から書き始めると８
進数になる。16進数は 0xa1 のように 0x を先頭に付け
る（a-f、A-F はどちらでもよい）。
ビットを３つずつまとめると８進数、４つずつまとめる
と16進数になる。
0
0
0
4
C
3
8
A
0 0 0 0 0 0 0 0 0 0 0 0 0 １ 0 0 １１ 0 0 0 0 １ １ １ 0 0 0 1 0 1 0
0
0
0
0
1
1
4
1
6
1
2
ビットごとの論理積 “&”
Cの演算⼦では、２項演算⼦としての “＆”。
対応するビットごとに AND演算を⾏う。
0x0eca
0 0 0 0 1 1 1 0 1 1 00 1 0 1 0
&
0x0693
0 0 0 0 0 1 1 0 1 0 01 0 0 1 1
0x0682
0 0 0 0 0 1 1 0 1 0 00 0 0 1 0
複合代入: a &= 1 は a = a & 1 と同じ。
ビットごとの論理和 “|”
Cの演算⼦では、２項演算⼦ “｜”。
対応するビットごとに OR演算を⾏う。
0x0eca
0 0 0 0 1 1 1 0 1 1 00 1 0 1 0
|
0x0693
0 0 0 0 0 1 1 0 1 0 01 0 0 1 1
0x0edb
0 0 0 0 1 1 1 0 1 1 01 1 0 1 1
複合代入: a |= 1 は a = a | 1 と同じ。
ビットごとの排他的論理和 “^”
Cの演算⼦では、２項演算⼦ “^”。
対応するビットごとに XOR演算を⾏う。
0x0eca
0 0 0 0 1 1 1 0 1 1 00 1 0 1 0
^
0x0693
0 0 0 0 0 1 1 0 1 0 01 0 0 1 1
0x0859
0 0 0 0 1 0 0 0 0 1 01 1 0 0 1
複合代入: a ^= 1 は a = a ^ 1 と同じ。
ビットごとの論理否定 “~”
Cの演算⼦では、単項演算⼦ “〜”。
各ビットを反転する（0は1に、1は0になる）。
0x0693
0 0 0 0 0 1 1 0 1 0 01 0 0 1 1
0xf96c
１１１ １ 1 0 0 １ 0 1 １０ 1 １ 0 ０
シフト演算 (1)
ビットパターンを指定した桁数だけ左右にずらす。
n
左シフトを n 桁⾏うと、整数値としては 2 倍したのと同
n
じことになる（右シフトは 2 で割って余りを切り捨
て）。
C⾔語の演算⼦では、左シフト、右シフトはそれぞれ２項
演算⼦ “<<” と “>>”。
a = v << 1; /* v のビットパターンを左へ１ビット
シフトした値を a へ代入 */
複合代入: a <<= 1 は a = a << 1 と同じ。
シフト演算 (2)
左シフト
0x0693 << 2
0x1a4c
0 0 0 0 0 1 1 0 1 0 01 0 0 1 1
0 0 0 1 1 0 1 0 01 0 0 1 10 0
右シフト
0x0693 >> 4
0x0069
0 0 0 0 0 1 1 0 1 0 01 0 0 1 1
0 0 0 0 0 0 0 0 0 1 1 0 1 0 01
シフト演算 (3)
符号拡張
符号付き整数を右シフトする場合、MSB側
には符号ビットと同じビットが⼊れられる。
short a = 0x8693;
a >> 4
1 0 0 0 0 1 1 0 1 0 01 0 0 1 1
1 1 1 1 1 0 0 0 0 1 1 0 1 0 01
unsigned short b = 0x8693;
1 0 0 0 0 1 1 0 1 0 01 0 0 1 1
b >> 4
0 0 0 0 1 0 0 0 0 1 1 0 1 0 01
演算⼦の優先順位
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
( ) [ ] ‐> . 後置++ 後置‐‐
! ~ ++前置 ‐‐前置 *アドレス &アドレス sizeof
（型）
* / %
+ ‐
<< >>
< <= > >=
C言語のビット演算子の優先
== !=
順位は少々おかしい。
ビット積 &
ビット排他的論理和 ^
括弧を付けて分かりやすく書
ビット和 |
&&
くようにする。
||
?:
= += ‐= *= /= %= &= |= ^= <<= >>=
,
AND演算のよくある使い⽅(1)
特定のビット位置が０か１か（ビットが⽴ってい
るかどうか）を調べる
•
if (info & 0x20) { ...
infoの、右から6ビット⽬が１なら ...
•
if (s & 1) { ...
s が奇数なら ...
•
if ((s & 1) == 0) { ...
s が偶数なら ... /* 注意：括弧が必要 */
AND演算のよくある使い⽅(2)
特定のビット範囲だけ取り出す
0x0eca
0 0 0 0 1 1 1 0 1 1 00 1 0 1 0
&
0x00f0
0 0 0 0 0 ０ ０ ０ 1 １ １ 1 0 0 ００
0x00c0
0 0 0 0 0 ００ 0 1 １ 0 0 0 0 ０ 0
１を並べた部分だけ、元のデータと同じビット列に
なり、ほかは０になることが分かる。このようにし
て、必要な部分を指定するためのビットパターンを
「マスク」と呼ぶ。
AND演算のよくある使い⽅(3)
特定のビット範囲だけ０にする
0x0eca
0 0 0 0 1 1 1 0 1 1 00 1 0 1 0
&
0xff0f
１１１ １１１ １ １ ０ ０ ００ 1 1 1 1
0x0e0a
0 0 0 0 1 1 1 0 0 0 00 1 0 1 0
マスクの役割が (2)と逆になった場合。
OR演算のよくある使い⽅(1)
特定のビット範囲を１にする
0x0eca
0 0 0 0 1 1 1 0 1 1 00 1 0 1 0
|
0x0060
0 0 0 0 0 ０ ０ ０ 0 １ １ 0 0 0 ００
0x0eea
0 0 0 0 1 1 1 0 1１1 0 1 0 1 0
元のビットパターンが何であっても、マスクで１が
立っている部分は１になる。
OR演算のよくある使い⽅(2)
特定の範囲にビットパターンをセットする
0x0e0a
0 0 0 0 1 1 1 0 0 0 00 1 0 1 0
|
0x0060
0 0 0 0 0 ０ ０ ０ 0 １ １ 0 0 0 ００
0x0e6a
0 0 0 0 1 1 1 0 0１1 0 1 0 1 0
ビットパターンをセットしたい部分は、あらかじめ
０でクリアしておく必要がある。
XOR演算のよくある使い⽅
特定のビットだけ反転させる
0x0eca
0 0 0 0 1 1 1 0 1 1 00 1 0 1 0
^
0x0060
0 0 0 0 0 ０ ０ ０ 0 １ １ 0 0 0 ００
0x0eaa
0 0 0 0 1 1 1 0 1 0 10 1 0 1 0
マスクで0の部分はそのまま、１が立っている部分
は反転する（0は1に、1は0になる）。
マスクの作り⽅(1)
マスクの作り⽅はいくつも考えられる。
もちろん、nやmが決まって
いれば、定数を使えばよい。
0
そうでない場合の例。
...
n
m
0 1 ... 1 0
...
0
n
a = 1 << n;
0
...
0 1 0 ... 0
n
a = a ‐ 1;
a = a << m;
0
0
...
...
0 1 ... 1
n
m
0 1 ... 1 0
...
0
マスクの作り⽅(2)
四則演算を使わない作り⽅の例。
特定機種の整数のビット数
に依存しないで、右のよう
なマスクを作る例。
a = ~0;
m
1
...
1
10
...
...
0
1
m
a = a << m;
1
...
10
...
0
ビット演算を算術演算として使う
n
整数に対する 2 の乗算、除算の代わりにシフト
演算を使う
a * 256　⇔　a << 8
a / 128　⇔　a >> 7
n
整数を 2 で割った余りを求めるのに & を使う
a % 256　⇔　a & 255　⇔　a & 0xff
上記のような記述は慣⽤的に広く⽤いられている
n
2 で割った余りを求める
AND演算で下位nビットの範囲だけ取り出す
0x0aca
0 0 0 0 1 0 1 0 1 1 00 1 0 1 0
&
0xff
０ ０ ００ ０ ０ ０ ０ １１１ １ 1 1 1 1
0xca
0 0 0 0 0 0 0 0 1 1 00 1 0 1 0
図は、256 (28) で割った余りを求める例。
0x100 = 256
0 0 0 0 0 0 0 １００ 0 0 ０ 0 ０ 0
256の倍数は、上の白い部分が必ず０であることに注意。
整数を16進数で印字する例
void print_hex(int val)
{
static char hex[] = “0123456789abcdef”;
int i;
for (i = (sizeof(int) * 8 - 4);
i >= 0; i -= 4) {
putchar(hex[(val >> i) & 0x0f]);
}
}
まめ知識
ここはこう書くこともできる
“0123456789abcdef”[(val >> i) & 0x0f]
整数を16進数で印字する例（説明）
int型が2バイト（16ビット）で、val = 0x175a の時
i = (sizeof(int) * 8 - 4); = 12
val
0 0 0 1 0 1 1 1 0 1 01 1 0 1 0
val>>12
0 0 0 0 0 0 0 0 0 0 00 0 0 0 1
& 0xf = 1
val>>8
0 0 0 0 0 0 0 0 0 0 01 0 1 1 1
& 0xf = 7
val>>4
0 0 0 0 0 0 0 1 0 1 11 0 1 0 1
& 0xf = 5
val>>0
0 0 0 1 0 1 1 1 0 1 01 1 0 1 0
& 0xf = 10