桁あふれと2の補数
8ビットの加減算で、切り捨てられる桁と符号付きの値の関係を学びます。
説明
保存場所を8ビットに固定すると、保持できるビット列は256通りです。計算結果が9ビット以上になったとき、下位8ビットだけを残す方式では、上位の桁が失われます。これが桁あふれの一例です。
このモジュールでは、8ビットの加算から始め、255の次が0になる仕組みを確かめます。続いて同じビット列を符号付き整数として解釈し、127の次が−128になる理由、負の数の2の補数表現、減算との関係を説明します。Pythonの整数自体に8ビットの上限があるわけではないため、下位8ビットを残す処理を明示して計算します。
1下位8ビットを残すマスク
ビット単位のANDは、両方が1の位置だけを1にします。11111111とのANDを取ると、下位8ビット以外は0になります。
mask = (1 << 8) - 1下位8ビットが1の整数; mask, format(mask, '08b')値とビット列マスクは255、2進数では11111111です。1を左へ8桁移動すると256になり、そこから1を引くと下位8桁がすべて1になります。
2上限直前の加算
250に5を加える例です。計算結果と、下位8ビットだけを残した結果を並べます。
total = 250 + 5加算結果; total, total & mask下位8ビットを残す, format(total & mask, '08b')保存されるビット列どちらも255で、11111111です。計算結果が0〜255の範囲に収まる間は、上位ビットを取り除いても値は変わりません。
3255に1を加えた場合
前の結果にさらに1を加えます。計算結果のビット列には、9桁目が必要になります。
total += 1さらに1を加算; format(total, '09b')9桁の計算結果, format(total & mask, '08b')下位8ビット, total >> 8外へ出た上位ビット計算結果は100000000ですが、下位8ビットは00000000です。右へ8桁移した値1が、8ビットの外へ出た桁です。
48ビットの値が一周する周期
254から258までの整数に、同じマスクを適用します。
[(n, n & mask元の整数と下位8ビットの値) for n in range(254, 259)上限前後の5値]254、255の次は0、1、2です。符号なし8ビットで下位だけを残す操作は、256で割った余りを求める操作と一致します。
5同じビット列を符号付きとして扱う
2の補数による8ビット符号付き整数は−128〜127を表します。最上位ビットが1なら、符号なしでの値から256を引いて解釈します。
signed = lambda n: n - 256 if n >= 128 else n0〜255を8ビット符号付きの値に変換; [(n, format(n, '08b'), signed(n)) for n in (0, 127, 128, 255)]境界のビット列と両解釈を表示10000000は符号なしなら128、符号付きなら−128です。11111111は255または−1になります。保存されているビットが同じでも、型の指定によって数値が変わります。
6符号付きでは127の次が−128になる
127と1は、どちらも正の数です。合計の下位8ビットを、符号付きとして解釈します。
total = 127 + 1正の数同士を加算; total > mask8ビットの外へ出たか, format(total & mask, '08b')保存されるビット列, signed(total & mask)符号付きとして解釈上位への桁あふれはFalseですが、符号付きの結果は−128です。数学的な結果128が符号付き8ビットの上限127を超えたためです。符号付きのオーバーフローと、9桁目への繰り上がりは同じ条件ではありません。
7−5のビット列を作る
正の5を8ビット内で反転し、1を加えると−5の2の補数表現になります。反転は11111111とのXORで行います。
positive = 5元の正の整数; inverted = positive ^ mask8ビットを反転; negative = (inverted + 1) & mask1を加えて8ビットに収める; format(positive, '08b'), format(inverted, '08b'), format(negative, '08b')変換の三段階00000101を反転すると11111010、1を加えると11111011です。後者を符号付きとして解釈すると251−256=−5になります。
8正負を加えると0になる
5と、直前に作った−5のビット列を加えます。下位8ビットの結果を確認します。
total = positive + negative二つのビット列の値を加算; total, total & mask, signed(negative)合計・下位8ビット・負数の解釈合計は256ですが、下位8ビットは0です。符号付きの意味では5+(−5)=0となり、同じ加算の回路で負の数も計算できる理由の一つです。
9減算を負数の加算として計算
3−5を、3と−5のビット列の加算で求めます。
result = (3 + negative) & mask3と−5を加えて8ビットに収める; format(result, '08b'), signed(result), 3 - 5ビット列・符号付きの値・通常の減算11111110は、符号付きで−2です。3−5という通常の計算結果と一致します。
10−128の正負を反転できない理由
最小値−128のビット列10000000にも、反転して1を加える処理を適用します。
minimum = 128−128を表すビット列の符号なし値; negated = ((minimum ^ mask) + 1) & mask反転して1を加える; format(negated, '08b'), signed(negated)結果のビット列と符号付きの値結果は再び10000000、つまり−128です。8ビット符号付きには+128が存在しないため、負号を反転した値を同じ幅で表せません。
まとめ
下位8ビットだけを残す計算では、256ごとに値が一周します。符号なしの上限と符号付きの上限は異なります。
2の補数では最上位ビットが1の値を負数として扱います。8ビットの範囲は−128〜127で、最小値−128の正負反転は同じ幅に収まりません。
操作履歴と解説を振り返れます。
Python 3
mask = (1 << 8) - 1; mask, format(mask, '08b')(255, '11111111')
total = 250 + 5; total, total & mask, format(total & mask, '08b')(255, 255, '11111111')
total += 1; format(total, '09b'), format(total & mask, '08b'), total >> 8('100000000', '00000000', 1)[(n, n & mask) for n in range(254, 259)][(254, 254), (255, 255), (256, 0), (257, 1), (258, 2)]
signed = lambda n: n - 256 if n >= 128 else n; [(n, format(n, '08b'), signed(n)) for n in (0, 127, 128, 255)][(0, '00000000', 0), (127, '01111111', 127), (128, '10000000', -128), (255, '11111111', -1)]
total = 127 + 1; total > mask, format(total & mask, '08b'), signed(total & mask)(False, '10000000', -128)
positive = 5; inverted = positive ^ mask; negative = (inverted + 1) & mask; format(positive, '08b'), format(inverted, '08b'), format(negative, '08b')('00000101', '11111010', '11111011')total = positive + negative; total, total & mask, signed(negative)(256, 0, -5)
result = (3 + negative) & mask; format(result, '08b'), signed(result), 3 - 5('11111110', -2, -2)minimum = 128; negated = ((minimum ^ mask) + 1) & mask; format(negated, '08b'), signed(negated)('10000000', -128)演習完了