8-бітний додавець з перенесенням цифр: повні додавачі, ланцюги перенесення та чому процесори 64 біт стали занадто повільними.

A half adder, then a full adder

Binary addition of two single bits needs two outputs: the sum bit and a carry bit, since 1+1 overflows a single bit. A half adder computes both with two gates — an XOR for the sum, an AND for the carry:

Sum = A XOR B Carry = A AND B That handles the least significant bit, but every higher bit position must also absorb a carry in from the position below it — three inputs, not two. A full adder extends the half adder to accept a carry-in Cin alongside A and B, and produces a sum bit and a carry-out:

Sum = A XOR B XOR Cin Cout = (A AND B) OR (Cin AND (A XOR B)) The second equation says: a carry is generated either when both A and B are 1 outright, or when exactly one of A, B is 1 and there was already a carry coming in to push the sum over 1. A full adder is built from two half adders plus an OR gate, or directly from five to nine logic gates depending on the gate library.

Sum   = A XOR B
Carry = A AND B

Ripple-carry: chaining 8 of them

An 8-bit adder chains eight full adders, wiring the carry-out of bit position i directly into the carry-in of bit position i+1. This is the ripple-carry adder — named because a carry generated at the low-order bit must physically propagate, or ripple, through every higher stage before the final result is valid, exactly like this simulation's bit-toggle animation shows.

bit: 7 6 5 4 3 2 1 0 ┌────┬────┬────┬────┬────┬────┬────┬────┐ Cin → │ FA │←Cout│ FA │←Cout│ FA │←Cout│ FA │←Cout ... →Cout(final) └────┴────┴────┴────┴────┴────┴────┴────┘ each FA: Sum = A⊕B⊕Cin, Cout = AB + Cin(A⊕B) The simplicity is also the design's weakness. Each full adder cannot produce a correct sum bit until its carry-in has settled, so the worst-case propagation delay of an n-bit ripple-carry adder grows linearly with n — roughly 2n gate delays, since a carry has to pass through the AND-OR carry logic of every stage in sequence. For 8 bits that is a modest 16 gate delays and entirely fine for a slow or moderate clock; for a 64-bit ALU it becomes the critical path that limits the whole processor's clock speed.

bit:     7    6    5    4    3    2    1    0
       ┌────┬────┬────┬────┬────┬────┬────┬────┐
Cin →  │ FA │←Cout│ FA │←Cout│ FA │←Cout│ FA │←Cout ... →Cout(final)
       └────┴────┴────┴────┴────┴────┴────┴────┘
              each FA: Sum = A⊕B⊕Cin, Cout = AB + Cin(A⊕B)

Why real CPUs don't use ripple-carry at 64 bits

The fix is to stop waiting for the carry to ripple and instead compute it directly. A carry-lookahead adder defines, for each bit, a generate signal G = A·B (this position produces a carry regardless of Cin) and a propagate signal P = A⊕B (this position passes an incoming carry through). Every carry bit can then be written as a sum-of-products of G's and P's from lower positions — no longer a chain, but a shallow tree of gates, which collapses the O(n) delay to roughly O(log n) at the cost of considerably more wiring and gates.

Real ALUs typically use a hybrid: lookahead within 4-bit blocks, ripple (or a second level of lookahead) between blocks, trading gate count against delay.

Читання результату трьома способами

Після того, як 8 бітів суми та остаточний перенос засиділися, сирий малюнок бітів є просто послідовністю 0 і 1 без будь-якого вродженого значення — це інтерпретація, яка призначає йому значення. Прочитати як незмінний бінарний, біт i сприяє 2^i, що дає діапазон від 0 до 255 для 8 бітів; перенос 1 вказує на справжню суму, яка перевищує 255 і викликала переповнення регістру. Прочитати як двійкову представлення з позначкою «два» (двокомплект), верхній біт є знаком, що вартує -2⁷ замість +2⁷, що дає діапазон від -128 до 127, і переповнення виявляється порівнюючи перенос у верхній біт із виходом з нього. Одна й та сама схема додавання обчислює обидва інтерпретації одночасно — додавання в двійковому представленні з позначкою «два» побітно еквівалентне незмінному додаванню, що є причиною того, чому двійкове представлення стало універсальним вибором для підписаних цілих чисел.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте 8-Bit Adder і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.