補数について

う　え　き　ぷ　に　き　あ　く　ん　笑 Advent Calendar 2021 25日目です
pwn記事は書けませんでした。悲しいです...（かなしいです...）

この記事について

本記事内でのn進数の表記は以下の通りとします。
$ (数字)_{n} $

例えば、

$ (123)_{10} $ → 10進数の123

$ (101)_{10} $ → 10進数の101

$ (101)_{2} $ → 2進数の101（10進数では5）

とします。しかし、10進数のみはこの表記をしないこととします（ちょっと　書きにくいし（ぼくが）読みにくいので（は？））。

また、様々な証明や詳細な理屈について、本記事内では省略しています。ご了承ください。ごめんなさい。うう...

補数の種類

前提として、補数は、各n進数に対し、nの補数とn-1の補数の2種類存在します！！！

n進数におけるnの補数

n進数におけるnの補数とは、ある正整数Aに対し、足し合わせるとちょうど桁上がりが発生する数のことです。
以下、実例です。

$ A = 3 $のとき、10の補数は$ 7 $
$ A = 100 $のとき、10の補数は$ 900 $
$ A = (101)_2 $のとき、2の補数は$ (11)_2 $

Aの桁数をdとすると、n進数における、Aに対するの補数は以下の式で表すことができます。

$ n^d - A $

すごい！わかりにくくなった気がする！うう！ごめんなさい！！！

n進数におけるn-1の補数

n進数におけるn-1の補数とは、ある正整数Aに対し、足し合わせた際に桁上がりが発生しない最大の数のことです。すなわち、Aに対するnの補数から1を引いた値になります。先程の例を元にすると、

$ A = 3 $のとき、9の補数は$ 6 $
$ A = 100 $のとき、9の補数は$ 899 $
$ A = (101)_2 $のとき、1の補数は$ (10)_2 $

nの補数の用途

nの補数の使用用途として、減算を行うために用いることができます。具体的には、n進数でA - Bを行うとき、CをBに対するnの補数とする（桁数はAに合わせます）と、A + Cを行い、桁上がりした部分を捨てることで実現が可能です。
以下、実例です。

$ A = 3, B = 2 $のとき、$ C = 8 $
$ A + C = 11 $桁上がりした部分を捨てると$ 1 $
$ A - B = 1 $なので等しい

$ A = (1001)_2, B = (100)_2 = (0100)_2 $のとき、$ C = (1100)_2 $
$ A + C = (10101)_2 $桁上がりした部分を捨てると$ (0101)_2 = (101)_2 $
$ A - B = 9 - 4 = 5, (101)_2 = 5 $なので等しい

コンピュータにとっての2の補数

コンピュータにとって、2の補数はとても大事な役割を担っています。
それは、減算を行うための役割です。

そもそも、コンピュータにとって、加算は容易ですが、減算は難しいです。
しかし、2の補数を使うことで、加算を用いて減算と同じ結果を得ることができます。ここでは、その手順を説明します。

コンピュータが2の補数を作る手順

2進数における2の補数は、ある正整数Aとその桁数dによって、以下の式

$ 2^d - A $

で表されますが、この式中にそもそもマイナスの符号が出てきています。しかし、2進数における1の補数について考えると、正整数Aに対する1の補数（Bとします）は、Aの各ビットを反転させたものになっています。
以下、実例です。

$ A = 10 = (1010)_2 $
$ d = 4 $なので
$ B = 2^4 - 10 = 16 - 10 = 6 = (0101)_2 $
$ (1010)_2 $と$ (0101)_2 $は互いに各ビットを反転させたものになっており、足し合わせると$ (1111)_2 $になるため、1の補数として適切。

ここで、Aに対する1の補数は、Aに対する2の補数-1であることから、
$ Aに対する2の補数 = Aに対する1の補数+1 $であることがわかります。
よって、2進数における2の補数をコンピュータが作るには、以下の手順を踏んでいることがわかります（ここでは、Aをある正整数としています）。

1. Aの各ビットを反転させたものをBとする
2. Bに1を足す（桁上がりは捨てる）

シンプルですね。わかりやすい！すげー　ちなみに、コンピュータでは、符号付きの整数は、最上位ビットが符号を表しているため、少し手順は増えますが、Aが負の整数でも上記のような手順で期待した結果を得ることができます。

コンピュータが減算を行う手順

これまでで、コンピュータが2の補数、というよりも、ある数の符号を反転させる手順はわかりました。わからなかったらごめんなさいです...
これからは、コンピュータが減算を行う手順を説明していきます。ここでは、Aを引かれる整数、Bを引く整数としています。

1. Bに対する2の補数の数Cを作る
2. A + Cを行う（桁上がりは捨てる）

おわり　よっしゃ！（え？）
これでできます！この項、内容薄いな...

最後に

このようなコンピュータの動作原理を知ることは、とっても楽しいしうれしいし大事だと思うので、貪欲に勉強していきたいですね！そうですね！

今日でアドベントカレンダーは終わりのようです。最後を締めくくるにふさわしい記事になったかな...？と心配です...