はじめに
エンコーディングとかをしらべていたら2の補数表現なる概念があることを知った
個人用メモとしてどういう仕組みなのかまとめておく
ざっくりまとめ
2の補数表現とは、ある値の補数bitをその値の負数として扱おうというもの
(正確には、0を正数として扱う都合上、実際にはもとの値の絶対値に+1したものがその補数bitに割り当てられる)
たとえば8bitの場合は 0b01111111(127) の補数は 0b10000000(-128) となります
ざっくりいうと、ある値が表現できる空間(int8だったら8bit)を半分にわけて、前半を正数、その補数を負数に割り当てます
負数の場合はbitが立つほど絶対値が小さくなっていくので直感的には違和感があるかもしれないですが、このように分けると数直線上は右に行くと値が増えて左に行くと値が減るというのが統一できるので、加減算がuintなどの正数のみの値と同じルールで行えて都合が良いです
ようするにこういうことです(8bit値の例で16進数で表記)
これで理解してしまった人は以下の文章を読む必要がないです
なんで2の補数表現が必要？
とはいえ図だけではピンとこないと思うので解説。
なぜ2の補数表現が必要かというと、負数を表現するためです。
まず、負数が存在しない場合を考えてみる。
コンピュータ上で扱う値は、その値が表現できるサイズを超えるとオーバーフローして0に戻ったりします。(Civの核ガンジーとかがいいオーバーフローの例)
なので、8bit変数だとすると以下のようになる
0 1 2 ~ 254 255 0 // 一周すると0に戻る 1 2
で、この仕組では負数を扱えないので、負数をとりあつかうためには違う仕組みが必要そう。その一つが2の補数表現
ほかにもzigzag encodingなどの負数をbit列で扱うしくみはあります。
なんですが、前述の通り2の補数表現はuintと同じルールで演算できるのでコンピュータに都合が良いです。
2の補数表現は値をどう表現する？
2の補数表現の8bit変数は以下のようになる
0 1 2 ~ 125 127 -128 // 中間地点を超えると負数になる -127 ~ -2 -1 0 // マイナスを超えると0に戻る
8bitの256パターンの空間で
- 前半128パターン(0~127)は正数で、
0~127の値に対応している0b00000000なら00b01111111なら127- bitが増えるほど値が増える
- 後半128パターン(128~255)は負数で、
-128~-1の値に対応している0b10000000なら-1280b111111111なら-1- bitが増えるほど値が値が増える(
-128よりも-1のほうが大きい値) - 絶対値としてはbitが立つごとに減っていくように見える
というように割り当てています
正負の判断は先頭1bitが立ってるかどうかで判断可能で、負数の絶対値はbit反転したものに1足したものになります
例
0b11111111(uintでいう255) ↓反転 0b00000000 ↓uintで言う0なので1足す -1
0b10110110(uintでいう182) ↓反転 0b01001001 ↓uintでいう73なので1足す -74
わざわざbit反転が必要だったり、めっちゃわかりづらいように見えますが、これには理由があるので説明します
なんでこういう割当になってるの？
127 の次が -128 であることに違和感を持つかもしれません(そこは -1 が来たほうがbit反転とか不要になって便利では？など)
これにはちゃんと理由があり、 加算と減算がuintと同じルールでできて都合が良い からです
たとえば、uintで以下の計算をするとします
# uintで計算 0b11111111(255) + 0b00000001(1) = 0b00000000(0)
オーバーフローして0ですね。
じつはこれ、まったく同じ式で2の補数表現でも成り立ちます
# intで計算 0b11111111(-1) + 0b00000001(1) = 0b00000000(0)
ほかの例でも見てみましょう。次はちょっと複雑な値で計算してみよう！
# uintで計算 0b10110110(182) + 0b01100011(99) = 0b00011001(25) # intで計算 0b10110110(-74) + 0b01100011(99) = 0b00011001(25)
計算結果が負数になる場合は？
# uintで計算 0b10110110(182) + 0b00000011(3) = 0b10111001(185) # intで計算 0b10110110(-74) + 0b00000011(3) = 0b10111001(-71)
全く同じ仕組みで加算が成り立っている！
つまりなんでこんなややこしい分け方をしているかというと、冒頭の図のような数直線として捉えることで常に加算と減算のルールを一つで行えるようにするため！
2の補数表現、直感的にはなんでこんなことになってんだ？と思う部分もあるかと思うんですが、
数直線に落とし込むことでuintの場合と同じルールで演算できるようにするためだ！ということがわかるとスッキリしますね(ぼくはしました)
感想
- 2の補数表現は演算しやすいようにうまいことできてる
- 負数のときに最上位bitが常に立つ
- 負数の絶対値はbitを反転した値に1を足せば求められる。これは数直線の逆の位置に変換する処理とも言える。1足すのは空間の分割の都合で0を正数としてあつかってるから負数は正数部分よりも1大きいため
- zigzag encodingとか負数でも最上位bitが立たない負数表現はあるが、uintと同じルールで演算したりはできない。メリデメあり
