2の補数とバイト順
実装:
foundations/numbers// 実行:go test ./foundations/numbers/
負の数をビットでどう表すかには何通りも答えがあるが、計算機はほぼすべて2の補数を使う。読みやすさで選ばれたのではない。引き算を足し算にできて、回路が1つで済むからだ。代償は範囲の非対称で、いちばん小さい数だけ符号を反転できない。そしてバイトの並べ方は正しさでなく取り決めなので、境界を越えるときは必ず明示する。
この章で作るもの
負の数をビットでどう表すか。この問いには何通りも答えがある。
いちばん素直なのは、符号のビットを1本立てて、残りを絶対値にする形になる。人間が読むにはこれがいちばん分かりやすい。10進数で -42 と書くのと同じ構造で、符号と大きさが別々に書いてある。
もう1つ、全ビットを反転する形もある。これも分かりやすい。
だが実際の計算機は、そのどちらも使わない。ほぼすべてが2の補数を使う。
理由は読みやすさではない。引き算を足し算にできるからになる。a - b を a + (-b) として、まったく同じ回路で計算できる。符号を見て加算と減算を切り替える必要がない。表し方の美しさではなく、回路が1つで済むという都合で選ばれている。
そして、その都合には代償がついてくる。表せる範囲が非対称になり、いちばん小さい数の符号を反転できない。絶対値を取る関数が、たった1つの入力に対して答えを返せない。
ビット 2の補数 1の補数 符号と絶対値
0000 0 0 0
0001 1 1 1
...
0111 7 7 7
1000 -8 -7 -0 ←── ここから負
1001 -7 -6 -1
1010 -6 -5 -2
...
1110 -2 -1 -6
1111 -1 -0 -7
0 の表し方 1通り 2通り 2通り
範囲 -8..7 -7..7 -7..7
非対称 対称 対称
引き算を足し算にする(2の補数)
3 - 10 = 3 + (-10)
0011
+ 0110 ← -10 = 10 を反転して1を足したもの
------
1001 → -7 ✓ 同じ加算器で出た
はみ出しは2種類ある。同じ回路で、見る旗が違うだけ
200 + 100 符号なしとして → 繰り上がりが出る(壊れた)
符号つきとして → 壊れていない
100 + 100 符号なしとして → 繰り上がりは出ない
符号つきとして → 符号が反転した(壊れた)順に見ていく。
- 2の補数は回路の都合で選ばれた: 表し方の問題ではなく、引き算を足し算にする仕掛け
- 代償は非対称: 0 が1通りしかないぶん負が1つ多く、その1つは符号を反転できない
- バイト順は取り決め: 正しさの問題ではない。だから境界では必ず明示する
① 回路の都合で選ばれた
まず、3つの表し方を並べる:
// Width はビット幅。4 から 32 までを扱う。
type Width int
// Kind は負の数の表し方。
type Kind int
const (
// Twos は2の補数。負の数は「2^n から引いた値」で表す。
Twos Kind = iota
// Ones は1の補数。負の数は全ビットを反転して表す。
Ones
// SignMag は符号と絶対値。最上位を符号のビットにして、残りを絶対値にする。
SignMag
)
func (k Kind) String() string {
return [...]string{"2の補数", "1の補数", "符号と絶対値"}[k]
}
func mask(w Width) uint64 { return (uint64(1) << uint(w)) - 1 }
// signBit は最上位のビットだけが立った値を返す。
func signBit(w Width) uint64 { return uint64(1) << uint(w-1) }
// Encode は数 v を、表し方 kind の w ビットのビット列にする。
func Encode(v int64, w Width, kind Kind) uint64 {
m := mask(w)
switch kind {
case Ones:
if v < 0 {
return ^uint64(-v) & m // 絶対値の全ビット反転
}
return uint64(v) & m
case SignMag:
if v < 0 {
return (uint64(-v) & (m >> 1)) | signBit(w)
}
return uint64(v) & (m >> 1)
default: // Twos
return uint64(v) & m
}
}
// Decode はビット列を、表し方 kind の符号つきの数として読む。
func Decode(bits uint64, w Width, kind Kind) int64 {
bits &= mask(w)
neg := bits&signBit(w) != 0
switch kind {
case Ones:
if neg {
return -int64(^bits & mask(w))
}
return int64(bits)
case SignMag:
if neg {
return -int64(bits &^ signBit(w))
}
return int64(bits)
default: // Twos
if neg {
// 上位を全部1で埋めてから符号つきとして読む。
return int64(bits | ^mask(w))
}
return int64(bits)
}
}
// Zeros は 0 を表すビット列を、その表し方で何通りあるかを含めて返す。
//
// 2の補数だけが1通りになる。他の2つには「正の 0」と「負の 0」があり、
// 同じ数なのにビットが違うので、比較のたびに特別扱いが要る。
func Zeros(w Width, kind Kind) []uint64 {
switch kind {
case Ones:
return []uint64{0, mask(w)} // 全部 0 と 全部 1
case SignMag:
return []uint64{0, signBit(w)} // 符号ビットだけ立った 0
default:
return []uint64{0}
}
}
// Range は表せる範囲を返す。
//
// 2の補数だけが非対称になる。0 の表し方が1通りしかないぶん、負の側が1つ多い。
func Range(w Width, kind Kind) (min, max int64) {
half := int64(1) << uint(w-1)
switch kind {
case Twos:
return -half, half - 1
default:
return -(half - 1), half - 1
}
}Zeros が返す個数を見ると、違いが1つの数字に出る。1の補数と符号絶対値には 0 が2通りある。全部 0 のパターンと、符号だけが立ったパターン。同じ数なのにビットが違うので、比較のたびに「どちらの 0 か」を気にすることになる。等しいかどうかを調べるのに、ビットを比べるだけでは足りない。
2の補数には 0 が1通りしかない。テストで、幅 4 と 8 のすべてのビットパターンについて、書いて読めば元に戻ることと、0 の通り数が表し方ごとに違うことを固定した。
そして加算器がこうなる:
// Result は加算の結果と、2種類のはみ出し。
type Result struct {
Bits uint64
// Carry は符号なしとして見たときのはみ出し。最上位から繰り上がりが出たか。
Carry bool
// Overflow は符号つきとして見たときのはみ出し。符号が壊れたか。
Overflow bool
}
// Add は w ビットの加算を行う。
//
// 見どころは、はみ出しの判定が2つあることになる。同じビット列を符号なしと見るか
// 符号つきと見るかで、壊れる条件が違う。回路は同じで、どちらの旗を見るかだけが違う。
//
// 符号つきのはみ出しは「最上位への繰り上がり」と「最上位からの繰り上がり」が
// 食い違ったときに起きる。同じ符号どうしを足して符号が変わったとき、と言っても同じ。
func Add(a, b uint64, w Width) Result {
m := mask(w)
a &= m
b &= m
sum := (a + b) & m
carry := a+b > m
// 同じ符号どうしを足して、結果の符号が変わったら壊れている。
sameSign := (a^b)&signBit(w) == 0
flipped := (a^sum)&signBit(w) != 0
return Result{Bits: sum, Carry: carry, Overflow: sameSign && flipped}
}
// Neg は符号を反転する。全ビットを反転して1を足す。
//
// いちばん小さい数だけ、これが自分自身を返す。符号を反転した結果が範囲に
// 収まらないので、行き場がない。絶対値が取れない数がある、という歪みの正体になる。
func Neg(bits uint64, w Width) uint64 {
return (^bits + 1) & mask(w)
}
// Sub は減算を行う。引く数の符号を反転して足すだけで、加算と同じ回路になる。
// これが2の補数を選ぶ理由そのものになる。
func Sub(a, b uint64, w Width) Result {
r := Add(a, Neg(b, w), w)
// 引き算では、繰り上がりの意味が逆になる(借りが出なければ立つ)。
if b&mask(w) == 0 {
r.Carry = true
}
return r
}Sub の中身が Add(a, Neg(b)) だけになっている。これが2の補数を選ぶ理由そのものになる。引き算のための回路が要らない。符号を見て分岐する必要もない。テストで、いくつかの組で引き算と「補数を足す」が同じ結果になることを固定した。
1の補数だとこうはいかない。0 が2通りあるせいで、繰り上がりを下位に回し込む処理が要る。符号絶対値なら、符号を見てどちらが大きいかを判定してから、大きいほうから小さいほうを引くことになる。回路が増える。
Add にはみ出しの判定が2つあるのも見どころになる。同じビット列でも、符号なしと見るか符号つきと見るかで壊れる条件が違う。符号なしなら最上位から繰り上がりが出たかどうか、符号つきなら同じ符号どうしを足して符号が変わったかどうか。回路は同じで、どちらの旗を見るかだけが違う。
テストで、200 + 100 は符号なしとしては壊れるが符号つきとしては壊れないこと、100 + 100 はその逆になることを固定した。C で符号つきのオーバーフローが未定義とされているのは、この2つが別物だからだ。
② 代償は非対称
Range が返す範囲を見ると、2の補数だけが非対称になる。8ビットなら -128 から 127 で、負の側が1つ多い。0 の表し方が1通りしかないぶん、その1つが負に回っている。
この1つが、ずっと後まで尾を引く。
// SignExtend は幅を広げる。空いた上位を符号のビットで埋める。
func SignExtend(bits uint64, from, to Width) uint64 {
bits &= mask(from)
if bits&signBit(from) == 0 {
return bits
}
return (bits | ^mask(from)) & mask(to)
}
// ZeroExtend は幅を広げる。空いた上位を 0 で埋める。
//
// 符号つきの値にこちらを使うと、負の数が巨大な正の数になる。同じビット列でも
// 意味が違うので、広げ方は型で決まる。
func ZeroExtend(bits uint64, from, to Width) uint64 {
return bits & mask(from) & mask(to)
}
// ShiftRight は右にずらす。arithmetic なら符号のビットで埋め、そうでなければ 0 で埋める。
//
// 負の数を2で割りたいときは算術シフトが要る。論理シフトを使うと、
// 負の数が巨大な正の数になる。同じ「右にずらす」でも別の命令になっている。
func ShiftRight(bits uint64, n int, w Width, arithmetic bool) uint64 {
bits &= mask(w)
out := bits >> uint(n)
if arithmetic && bits&signBit(w) != 0 {
// 上から n ビットぶんを1で埋める。
out |= (mask(w) << uint(int(w)-n)) & mask(w)
}
return out & mask(w)
}いちばん小さい数の符号を反転すると、結果は範囲に収まらない。だから Neg は自分自身を返す。テストで、-128 を反転しても -128 のままになることを固定した。
絶対値を取る関数が、この1つの入力に対して正しい答えを返せない。負の値を返すか、例外を出すか、未定義にするかのどれかしかない。ハードウェアの都合が、そのまま言語の意味論に出てきている。
SignExtend と ZeroExtend の違いも、同じところから来る。幅を広げるとき、空いた上位を何で埋めるかは、そのビット列を符号つきと見るかどうかで決まる。同じビット列でも埋め方が違えば別の数になる。テストで、-1 を符号を保って広げれば -1 のまま、0 で埋めれば 255 になることを固定した。
右にずらす操作が2つあるのも同じ理由になる。負の数を2で割りたいなら、空いた上位を符号のビットで埋めなければならない。0 で埋めると、負の数が巨大な正の数になる。同じ「右にずらす」でも、機械語の命令としては別物になっている。
③ バイト順は取り決め
ここまでは1つの数をビットでどう表すかの話だった。もう1つ、その数をメモリに並べるときの順序という別の問題がある。
// PutLittle はビット列をバイトに分けて、下位のバイトから並べる。
func PutLittle(bits uint64, w Width) []byte {
n := int(w) / 8
out := make([]byte, n)
for i := 0; i < n; i++ {
out[i] = byte(bits >> uint(8*i))
}
return out
}
// PutBig は上位のバイトから並べる。通信で使う順序はこちらになる。
func PutBig(bits uint64, w Width) []byte {
n := int(w) / 8
out := make([]byte, n)
for i := 0; i < n; i++ {
out[i] = byte(bits >> uint(8*(n-1-i)))
}
return out
}
// GetLittle は下位のバイトから並んでいるとして読む。
//
// 途中で止めても意味が壊れないのが、この並びの取り柄になる。先頭の1バイトだけ
// 読めば、それが下位8ビットになる。幅の違う読み出しが同じアドレスでできる。
func GetLittle(b []byte) uint64 {
var v uint64
for i := len(b) - 1; i >= 0; i-- {
v = v<<8 | uint64(b[i])
}
return v
}
// GetBig は上位のバイトから並んでいるとして読む。
func GetBig(b []byte) uint64 {
var v uint64
for _, x := range b {
v = v<<8 | uint64(x)
}
return v
}こちらは正しさの問題ではない。どちらでも動く。ただの取り決めになる。
だが取り決めなので、書いた側と読む側で食い違うと壊れる。テストで、下位から並べたものを上位から読むと 0x12345678 が 0x78563412 になることを固定した。同じバイト列で、同じ長さで、値だけが違う。壊れたことに気づかないまま先へ進めてしまうので、たちが悪い。
下位から並べる順には、1つ実際的な取り柄がある。途中で止めても意味が壊れない。先頭の1バイトだけ読めば下位8ビットになり、2バイト読めば下位16ビットになる。同じアドレスを、幅の違う読み出しで使える。テストでこれを固定した。上位から並べる順だと、先頭を読むと上位が出るので、幅を変えるとアドレスも変わる。
一方、上位から並べる順は人間が読む順と同じになる。バイト列をそのまま眺めたときに、16進の並びが数字の並びと一致する。通信の世界で上位から並べる順が使われているのは、この読みやすさと、歴史的な経緯の両方による。
どちらが良いかではなく、境界を越えるときに明示されているかどうかが問題になる。同じ機械の中だけで完結するなら、どちらでも見えない。ファイルに書く、通信で送る、といった瞬間に初めて表に出る。
動かす
下のデモは、幅を選んで全ビットパターンを並べる。3つの表し方を切り替えると、0 が2つある表し方と1つの表し方の違いが表で見える。加算のタブでは、同じ計算に対して2つのはみ出しの旗が別々に立つ。バイト順のタブでは、書いた順と違う順で読んだときに何が起きるかを見る。
「表し方」では、4ビットの全16通りを並べている。表し方を切り替えると、0 が2つある行が現れたり消えたりする。 「はみ出しの2種類」では、同じ加算に対して2つの旗が別々に立つ。片方だけ立つ組み合わせがあることが、 符号つきと符号なしが別物である証拠になる。「バイト順」は、書いた順と読む順が食い違うと何が起きるかを見る。
設計の観点
- 表し方は用途で選ぶ: 読みやすさでなく、その上でどんな操作をするかで決まる。ここでは加算器の数だった
- 例外を1つ作ると、ずっと付いて回る: 絶対値が取れない数が1つあるだけで、あらゆる符号反転が注意を要する
- 同じビット列に複数の意味がある: 符号つきか符号なしか、どちらで見るかは型が決める。ビットは何も語らない
- 取り決めは境界で明示する: 中で完結しているうちは見えない。出た瞬間に食い違う
- 切り詰められる並びは強い: 下位から並べておくと、幅の違う読み出しが同じアドレスでできる
- アロケータや仮想メモリの前提: アドレス計算も、この上に乗っている
対照と実例
| 2の補数 | 1の補数 | 符号と絶対値 | |
|---|---|---|---|
| 0 の表し方 | 1通り | 2通り | 2通り |
| 範囲(8ビット) | -128 .. 127 | -127 .. 127 | -127 .. 127 |
| 引き算 | 加算器のまま | 繰り上がりの回り込みが要る | 符号を見て分岐 |
| 比較 | ビットの比較でほぼ済む | 0 の特別扱いが要る | 符号を先に見る |
| 使われている場所 | ほぼすべての現代の計算機 | 一部の古い機械 | 浮動小数点の仮数部 |
| 下位から(little) | 上位から(big) | |
|---|---|---|
| 先頭1バイト | 下位8ビット | 上位8ビット |
| 幅を変えた読み出し | 同じアドレスでできる | アドレスがずれる |
| 人間が読む | 逆順に見える | そのまま読める |
| 使われている場所 | x86、ARM の既定、多くのファイル形式 | 通信、一部のファイル形式 |
裏どり:
- 2の補数が標準になった: C++20 と C23 で、符号つき整数の表現は2の補数だけと規定された。それ以前は3通りが許されていた
- 符号つきのオーバーフローは未定義: C と C++ では、符号つきの計算がはみ出すと未定義になる。符号なしは回り込むと決まっている
abs(INT_MIN): 未定義になる。範囲の非対称が、標準ライブラリの仕様にまで出ている- 右シフト: 負の数を右にずらしたときの結果は、C では処理系定義だった。C++20 で算術シフトと規定された
- ネットワークバイトオーダー: 通信では上位から並べる順を使う。
htonsやhtonlはそのための変換になる - BOM: UTF-16 の先頭に付く印は、どちらの順で書かれているかを表すためのものになる
簡略化したこと
- 幅は 32 まで: 64ビットは扱わない。マスクの計算が特別扱いになるため
- 浮動小数点なし: 符号と指数と仮数に分ける表し方は扱わない。符号絶対値に近い形になる
- 回路なし: 加算器の中身(桁上げ先読みなど)は扱わない。結果と旗だけ
- 可変長なし: 小さい数を短いバイト数で書く形式は扱わない。バイト順とは別の話になる
- アラインメントなし: 何バイト境界に置くかは扱わない
- 文字符号化なし: UTF-16 の BOM は文章で触れるだけ
参考資料
- Two's complement (Wikipedia) — 表し方の比較と、加算器が1つで済む理由
- P0907R4: Signed Integers are Two's Complement — 標準が2の補数に一本化された経緯
- 実装: foundations/numbers