Chapter 29

ビット演算

整数に対する演算として,今までに四則演算を紹介しました.しかし整数には他にも様々な演算が用意されています.整数を 2 進法として捉えることで,可能な演算の幅が広がります.

ビット表現

整数は,コンピュータの内部で 2 進法を使って表現されているという話をしました.このことについてもう少し詳しく説明します.

10 進法

多くの人が普段使っているのは 10 進法です. n 桁の 10 進法においては,ある整数 x があったときに,

x = a_{n - 1}\cdot10^{n - 1} + a_{n - 2}\cdot10^{n - 2} + a_{n - 3}\cdot10^{n - 3} + \cdots + a_2\cdot10^2 + a_1\cdot10 + a_0

(ただし a_{n - 1}, a_{n - 2}, a_{n - 3}, \ldots, a_0 はいずれも 0 以上 10 未満の整数)として, a_{n - 1}, a_{n - 2}, a_{n - 3}, \ldots, a_0 の並びで x を表現します.また, a_01 の位, a_110 の位, a_210^2 の位,……, a_i10^i の位,……, a_{n - 1}10^{n - 1} の位といいます.

たとえば, x = 519n = 4 であれば,

519 = 0 \times 10^3 + 5 \times 10^2 + 1 \times 10 + 9

なので, 10^3 の位は a_3 = 010^2 の位は a_2 = 510 の位は a_1 = 11 の位は a_0 = 9 となります.

a_{n - 1}, a_{n - 2}, a_{n - 3}, \ldots, a_0 の並びで表せる x の値の範囲は, 0 以上 10^n 未満です.反対に, 0 以上 10^n 未満の任意の整数 x に対して, a_{n - 1}, a_{n - 2}, a_{n - 3}, \ldots, a_0 の決め方がただ 1 通り存在します.

2 進法

一方,コンピュータの中で用いられるのは 2 進法です. n 桁の 2 進法においては,ある整数 x があったときに,

x = b_{n - 1}\cdot2^{n - 1} + b_{n - 2}\cdot2^{n - 2} + b_{n - 3}\cdot2^{n - 3} + \cdots + b_2\cdot2^2 + b_1\cdot2 + b_0

(ただし b_{n - 1}, b_{n - 2}, b_{n - 3}, \ldots, b_0 はいずれも 0 以上 2 未満の整数)として, b_{n - 1}, b_{n - 2}, b_{n - 3}, \ldots, b_0 の並びで x を表現します.また, b_01 の位, b_12 の位, b_22^2 の位,……, b_i2^i の位,……, b_{n - 1}2^{n - 1} の位といいます.

たとえば, x = 25n = 8 であれば,

25 = 0 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2 + 1

なので, 2^7 の位は b_7 = 02^6 の位は b_6 = 02^5 の位は b_5 = 02^4 の位は b_4 = 12^3 の位は b_3 = 12^2 の位は b_2 = 02 の位は b_1 = 01 の位は b_0 = 1 となります.

b_{n - 1}, b_{n - 2}, b_{n - 3}, \ldots, b_0 の並びで表せる x の値の範囲は, 0 以上 2^n 未満です.反対に, 0 以上 2^n 未満の任意の整数 x に対して, b_{n - 1}, b_{n - 2}, b_{n - 3}, \ldots, b_0 の決め方がただ 1 通り存在します.

符号なし整数型

n ビットの符号なし整数型では, n 桁の 2 進法をそのまま用います.たとえば 8 ビット符号なし整数型 u8 において 25 は 00011001 と表されます. println! マクロの {:b} を使うと, 2 進法での表現を出力することができます( b は binary の頭文字です).

fn main() {
    println!("{:08b}", 25_u8);
}
標準出力
00011001

よって, n ビット符号なし整数型で表せる範囲は 0 以上 2^n 未満となります.

u8 での表現
0 00000000
1 00000001
2 00000010
\vdots \vdots
2^8 - 1 = 255 11111111

符号付き整数型

n ビットの符号付き整数型では,負の数を扱うために 2^n を法とする合同式を考えます.

たとえば 8 ビット符号付き整数型 i8-25 を表すことを考えます. 0 以上 2^8 未満の整数のうち, 2^8 を法として -25 と合同なのは 2^8 - 25 = 231 です. 231 を 2 進法で表すと 11100111 となります.これが, i8 における -25 の表現です.

fn main() {
    println!("{:08b}", -25_i8);
    println!("{:08b}", 231_u8); // 同じ
}
標準出力
11100111
11100111

n ビット符号付き整数型では, -2^{n - 1} 以上 0 未満の整数を,このように 2^{n - 1} 以上 2^n 未満の整数に置き換えてから表します.よって, 2^{n - 1} 以上 2^n 未満の整数は表現できなくなり, 0 以上の整数のうち表現できるのは 2^{n - 1} 未満だけになります.

i8 での表現 同じ表現の u8
-2^7 = -128 10000000 2^7 = 128
-127 10000001 129
-126 10000010 130
\vdots \vdots \vdots
-3 11111101 253
-2 11111110 254
-1 11111111 2^8 - 1 = 255
0 00000000 0
1 00000001 1
2 00000010 2
\vdots \vdots \vdots
2^7 - 1 = 127 01111111 2^7 - 1 = 127

また,この表を見ると,最上位ビット(一番左の桁)が 0 なら 0 以上の値, 1 なら負の値になっていることが分かります.

ビット演算

ビットごとの AND

bool 型の AND は,「どちらも true のとき true となる」演算でした.

一方, true を 1 , false を 0 に置き換えることで,整数 0 / 1 についても AND を考えることができます.このとき AND は「どちらも 1 のとき 1 となり,それ以外のとき 0 となる」演算となります.

型が同じ 2 つの整数値 xy について x & y と書くと,各ビットごとに AND 演算が行われます.たとえば型がともに i8x = -20y = -70 であれば,ビット表現はそれぞれ 1110110010111010 となるので, x & y はこの各ビットごとに AND 演算を行った結果,すなわち 10101000 となります.

たとえば最上位ビット(一番左の桁)に着目すると, x でも y でも 1 なので, x & y でも 1 になります.一方,下から 3 番目のビット(右から 3 桁目)に着目すると, x では 1 ですが, y では 0 なので, x & y では 0 になっています.

10101000i8 において -88 を表すので, -20 & -70 の結果は -88 ということになります.

fn main() {
    assert_eq!(-20_i8 & -70_i8, -88_i8);
}

ビットごとの OR

型が同じ 2 つの整数値 xy について x | y と書くと,各ビットごとに OR 演算が行われます.たとえば型がともに i8x = -20y = -70 であれば,

となります. 11111110i8-2 を表します.

fn main() {
    assert_eq!(-20_i8 | -70_i8, -2_i8);
}

ビットごとの XOR

型が同じ 2 つの整数値 xy について x ^ y と書くと,各ビットごとに XOR 演算が行われます.たとえば型がともに i8x = -20y = -70 であれば,

となります. 01010110i886 を表します.

fn main() {
    assert_eq!(-20_i8 ^ -70_i8, 86_i8);
}

ビット反転

整数値 x について !x と書くと,各ビットごとに NOT 演算が行われます.たとえば型が i8x = 25 であれば,

となります. 11100110i8-26 を表します.

fn main() {
    assert_eq!(!25_i8, -26_i8);
}

シフト演算

左シフト

左シフトは,ビットを「左にずらす」演算です.たとえば, i8 型の 100 を左に 2 ビットシフトすると, -112 になります:

x << y と書くと, x を左に y ビットシフトした値になります.

fn main() {
    assert_eq!(100i8 << 2, -112i8);
}

右シフト

右シフトは,ビットを「右にずらす演算」です.右シフトには >> 演算子を使います.左シフトと違って,右シフトは符号なし整数型と符号付き整数型の間で違いがあります.

論理シフト

符号なし整数型の右シフトでは,ビットを右にずらし,左には 0 を詰めます.たとえば, u8 型の 150 を右に 2 ビットシフトすると, 37 になります.

100101 の部分が右に 2 つ動き,空いた左の 2 桁には 0 が詰められています.これを,論理シフトといいます.

fn main() {
    assert_eq!(150_u8 >> 2, 37_u8);
}

算術シフト

符号付き整数型の右シフトでは,ビットを右にずらし,左には「もとの数の最上位ビット」を詰めます.

たとえば, i8 型の 5000110010 と表され,最上位ビットは 0 です.これを右に 2 ビットシフトすると

となります. 001100 の部分が右に 2 つ動き,空いた左の 2 桁には 0 が詰められています.

一方, i8 型の -5011001110 と表され,最上位ビットは 1 です.これを右に 2 ビットシフトすると

となります. 110011 の部分が右に 2 つ動き,空いた左の 2 桁には 1 が詰められています.

このように,左にもとの数の最上位ビットを詰めるような右シフトを,算術シフトといいます.

fn main() {
    assert_eq!(50_i8 >> 2, 12_i8);
    assert_eq!(-50_i8 >> 2, -13_i8);
}

シフト演算子 << >> についても,対応する複合代入演算子 <<= >>= があります.

演算子の優先順位

ここまでで出てきた各演算子を優先順位の高い順に並べると,次のようになります.

優先順位 演算子 結合順序
高い 負号 -
NOT 演算 !
参照 & &mut
参照外し *
単項
型変換 as 左結合
乗除算 * / % 左結合
加減算 + - 左結合
シフト演算 << >> 左結合
AND 演算 & 左結合
XOR 演算 ^ 左結合
OR 演算 | 左結合
比較 == != < > <= >= 非結合的
短絡評価 AND 演算 && 左結合
短絡評価 OR 演算 || 左結合
低い 代入 =
+= -= *= /= %=
&= |= ^= <<= >>=
右結合

負の数に付ける - やビット反転の ! は単項なので,結合順序がありません.また,比較演算子も a < b < c のように続けて書くことができないので結合順序がありません.