2進数演算と2の補数ラボ

現代のコンピュータでは、負の整数は2の補数表現を使って表されます。最上位ビット（MSB）は負の重みとして機能し、8ビット整数ではビット7が+128ではなく-128を表します。減算が加算と同一になるという美しい性質があり、CPUはA - BをA + (~B + 1)として計算します。これにより別途の減算ハードウェアが不要となり、ALUが両演算に同じ加算回路を使用できます。

普段の数では各桁が右隣の10倍の重みを持ちますが、2進数ではその倍率が単純に2になります。ビットは（右から）1, 2, 4, 8, 16, 32, … という重みを持ちます。2進数を読むとは、1が立っている桁の重みを足し合わせることです。1011 は 8 + 0 + 2 + 1 = 11 です。このツールのビット重み表示では各ビットを切り替えながら合計の変化を追えます。それがここでのすべての変換の種明かしです。

ここで示す筆算の掛け算——Aを2倍し、Bに1のビットがある位置で足し合わせる——は、まさに「ロシア農民の掛け算」であり、3000年以上前のエジプトのパピルスにも見られる手法です。一方の数を半分にし（余りは捨てる）、もう一方を2倍にして、半分にした数が奇数の行だけ2倍した値を合計します。半分にして奇数かを調べることは、まさに2進数の桁を読むことなので、古代の書記官と現代のALUは同じアルゴリズムを実行しているのです。