加算器
加算器（かさんき、Adder）とは、加算を行う演算装置である。この記事ではデジタル回路によるものについて説明する。アナログ回路による加算回路の一例はオペアンプ#加算回路（電圧によるもの。他に電流の加算もある）を参照。
半加算器
半加算器（はんかさんき、Half adder）は、2進数の同じ桁どうしの演算をして（通常は最下位の桁）、桁上がりは桁上げ出力（Carry out）によって出力する。ANDゲート、ORゲート、NOTゲートの組み合わせで作ると図のようになる。
入力A、入力B、出力（S、Sum）、桁上げ出力（C、Carry out）の関係を示す真理値表は次の通り。
| A | B | C | S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
SはAとBのXORゲートによる出力に他ならない。論理の方式にもよるが、たとえば三路スイッチ（たとえば階段の上のスイッチでも下のスイッチでもオンとオフをトグル可能なスイッチに見られる方式）のような構造でXORを直接実装できる方式であれば、直接実現することができる。XORの実装方法の詳細についてはXORゲートの記事を参照のこと。ただし加算器の場合、後述する高速桁上げのためにANDとOR（ないしNOR）を生成する場合には、それらの結果を流用することもできるので、好適な設計が違うこともある。
全加算器
全加算器（ぜんかさんき、Full adder）は、2進数の最下位以外の同じ桁どうしの演算をして、下位からの桁上げ入力を含めて出力する。下位の桁上げ出力を上位の桁上げ入力に接続することにより、任意の桁数の2進数の加算が可能となる。1個の全加算器は、2個の半加算器と1個のORから構成される。
入力が3本存在し（入力A、入力B、桁上げ入力）、全て対等に動作する。しかし回路上は3入力が対称になっているとは限らない。
入力A、入力B、桁上げ入力（X）、出力（S）、桁上げ出力（C）の関係を示す真理値表は次の通り。
| A | B | X | C | S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
複数ビットの加算器
前述の半加算器1個を最下位桁用に、この全加算器を他の上位桁用に桁数分だけ組み合わせる事によって、任意の桁数の2進数加算器が構成できる。下図は6桁の加算器の回路図である。（A5A4A3A2A1A0+B5B4B3B2B1B0→CS5S4S3S2S1S0）
最上位桁から出るCは、単純には「桁あふれ、オーバーフロー、Overflow、Overflow Carry」とは判定できない（解釈による）ことに注意が必要である。敢えて呼ぶなら、「エンドキャリー、End Carry」となる。
キャリー先読み
加算は情報処理の基本であるため、高速な情報処理のためにはまず加算器の動作の高速性が求められる。論理回路の動作速度は、入力から出力までの間にある基本論理素子（ANDまたはOR回路）の個数が大きく影響するため、加算器におけるこの段数を考察してみよう。
上記の半加算器では入力AまたはBから出力Sまでの基本論理素子の段数は2、出力Cまでの段数は1である。（一般にはNOTは段数に含めない。基本論理素子を構成する回路の入力用トランジスタを逆に使うだけでNOTは実現できるからである。）
同様に、全加算器ではSの段数は4、Cの段数も4になる。このことより、上記の6桁の加算器では、最大の段数となるA0入力からC出力までの間は、全加算器Cの段数×5+半加算器Cの段数 = 4×5+1 = 21段ということになる。
桁数が大きくなってくるとこの段数はかなり大きいものとなるので、各素子の伝播遅延の合計の遅延時間も顕著となり高速処理の大きな障害になってくる。このため、段数を大きくしている桁上げ信号（キャリー信号）の部分を別に計算する事により、段数を減らすという事がしばしば行なわれる。この、桁上げ信号を別の論理回路で生成する手法の事を「キャリー先読み（キャリールックアヘッド : Carry look ahead）」と呼び、半加算器、全加算器とこのキャリー先読み回路を含めて全体を「キャリールックアヘッドアダー (Carry look ahead adder)」と呼ぶ。
具体的には、S1を生成している全加算器の桁上げ入力は、
X1 ← A0 AND B0
となり、S2を生成している全加算器の桁上げ入力は、
X2 ← (A1 AND B1) OR (A0 AND B0 AND A1) OR (A0 AND B0 AND B1)
となる。さらに、S3を生成している全加算器の桁上げ入力は、
X3 ← (A2 AND B2) OR (A1 AND B1 AND A2) OR (A1 AND B1 AND B2)
OR (A0 AND B0 AND A1 AND A2) OR (A0 AND B0 AND A1 AND B2)
OR (A0 AND B0 AND B1 AND A2) OR (A0 AND B0 AND B1 AND B2)
となる。このように、桁数が上がれば回路は飛躍的に複雑になるが、いずれもたった2段で桁上げ信号が生成される。（2入力のANDも3入力のANDも、回路上はトランジスタを並列に並べるだけの事であるので、1段である事に変わりがない。ORについても同様。）
この方法を用いると、桁数がいくつになってもたった4段しか必要としないため画期的な高速化を図る事ができる。しかし、必要となる回路素子数が格段に多くなるため、消費電力と回路のコストが大きく犠牲になる。
キャリー予測
キャリー先読みを行わない加算器の場合、上位桁の計算は、下位桁の値が決定するまで開始できない。
そこで、全桁数を半分に分割し、下位桁の計算と同時に、上位桁の計算を、下位桁から上位桁への桁上げの有無双方の2通りについて行う。下位桁の計算が完了した時点で、上位桁への桁上げの有無によって、計算済みの2通りの上位桁の値の片方を選択する。このため、上位桁は加算器を2重に用意する必要がある。
これにより、全加算器の数は1.5倍、桁数の半分のビット数のマルチプレクサ（データセレクタ）が必要となるが、計算時間はほぼ半分になる。
さらに、上位桁と下位桁をそれぞれ1/2, 1/4, 1/8...とさらに分割して予測計算をすることで、究極的には加算器1段分の遅延と、桁数の2の対数段分(32bitであれば5段)のマルチプレクサの遅延で計算が完了する。
桁数の対数に比例する計算時間の遅延が発生するが、回路規模は桁数比例にとどまり、キャリー先読みのように桁数の指数関数となる大きさになることはない。
減算器
一般に、有限桁数の減算は「補数」を用いることで加算に置き換えて計算する事が出来る。まずは理解しやすいように10進数で考えてみよう。
例として4桁同士の「5714 - 2840」という計算を考える。この減算を直接計算する代わりに、この式を次のように変形してみよう。
5714 - 2840 = 5714 + 10000 - 2840 - 10000 = 5714 + 1 + 9999 - 2840 - 10000
「9999-2840」の部分は「7159」であるが、9999から4桁以内の数字を引く場合には桁借りが発生する事は無いため、他の桁の事を考慮する事無く各桁毎に「9-2」「9-8」「9-4」「9-0」を行なえばよい。つまり「足すと9になる数」に各桁を置き換えるだけで「9999-2840」の計算ができることになる。この「足すと9になる数」のことを、「9の補数」と呼ぶ。
つまり、上記の減算は、次の手順で計算できる事になる。
1: 引く数 2840の各桁を9の補数化する。→ 7159 2: それに1を加える。→ 7160 3: それに引かれる数 5714を加える。→ 12874 4: 最後に10000を引く。→ 2874
解説の最後に減算が出てきたが、手順3:の計算結果は10000以下の数+4桁の数の加算であるから19999が最大となるため、この計算は常に5桁目を無視するだけで済む。
さて、2進数で同様の手法を考えると、9の補数の代わりに1の補数が計算できれば、減算を加算器を用いて計算できる事がわかる。1の補数とは「足して1になる数」であるので、2進数なら「0→1」「1→0」ということになり、これはNOTに他ならない。
例として「100101-010110」という計算は次の手順で計算できる事になる。
1: 引く数010110の各桁を反転(NOT)する。→ 101001 2: それに1を加える。→ 101010 3: それに引かれる数100101を加える。→ 1001111 4: 最上位桁を無視する。→ 001111
これを回路にすると、次のようになる。
この図では、外部から最下位への桁上げ X への入力を 1 に固定しているが、もしこれが 0 だったとしたら、出力される結果が 1 だけ小さいものになる、ということに注意する。多倍長の計算中だったとしたら、より下の桁の計算において上の桁からの借り（ボロー）があったとしたらこの X への入力を 0 にして計算すれば良い、ということが了解されるだろう。また同様にして、最上位桁の全加算器からのキャリー出力 C は、この計算全体においてボローがなければ 1、ボローがあったら 0 になる。
プロセッサの演算装置では、キャリーやボローの状態について、フラグレジスタを通して、連続する計算の間を引き回すようにする、という設計がよくある。この時、減算時のボローフラグを、加算用のキャリーフラグと兼用し、さらにハードウェアを単純にする目的から、ボローのありなしについては、ボロー有→キャリーフラグは 0、ボロー無→キャリーフラグは 1、とした設計が見られる（6502・POWER・ARM・PICなど）。
直列加算器
以上で説明した加算器は、8ビットなり16ビットなりの1ワードを並列に計算するものであった。これに対し、ワード中のビットを最下位ビット（LSB）から順番に1ビットずつ足していく加算器があり、直列加算器（en:serial binary adder）という。1個の1ビット全加算器のキャリー出力を、1クロック信号を遅らせるフリップフロップを通して、自身のキャリー入力につなぐ。
この直列加算器の2つの入力に、2個のワードのLSBから順番に同時に入力すれば、出力には加算の結果がLSBから順番に出力される。レジスタにシフトレジスタや、古くは遅延記憶装置を使った計算機と相性が良く、速度が遅いことと引き換えに、わずかなハードウェア資源で加算器が実現できる。
出典
- 柴山潔『改訂新版 コンピュータアーキテクチャの基礎』近代科学社,2003年,ISBN 978-4-7649-0304-3