Français · article non traduitGitHub

The devutils collection

Binary adders

Derive a full adder, follow carries through four bits, and distinguish unsigned carry from signed overflow.

On this page

Prerequisites

Add one column at a time

An adder computes a binary sum. For an unsigned bit vector, each position has twice the weight of the position to its right: the four bits 1101 represent 8 + 4 + 1 = 13. Read combinational logic first; the adder in this page has no stored state.

Start with two bits A and B. Their total ranges from 0 to 2, so one result bit is insufficient. A half adder produces a low bit S and a carry C:

S = A XOR B
C = A AND B

For 1 + 1, S = 0 and C = 1: together the two bits are 10, representing 2.

Include an incoming carry

A full adder adds A, B and an incoming carry Cin. Its outputs must satisfy this arithmetic invariant:

A + B + Cin = S + 2 * Cout

Here the additions and multiplication in the invariant are ordinary integer arithmetic. The equivalent Boolean rules are:

S    = A XOR B XOR Cin
Cout = (A AND B) OR (A AND Cin) OR (B AND Cin)
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Check the last row: 1 + 1 + 1 = 3, and S + 2 × Cout = 1 + 2 = 3.

Follow a four-bit sum

Take A = 1101 (13) and B = 0110 (6). Start with carry 0 at the least significant position and work toward the left:

Position, starting at 0 A bit B bit Carry in Sum bit Carry out
0 1 0 0 1 0
1 0 1 0 1 0
2 1 1 0 0 1
3 1 0 1 0 1

Read the sum bits in the reverse order from the table rows: 0011. The final carry adds a fifth bit, making 10011 = 19. If the destination stores only four bits, it keeps 0011, which is 3: addition modulo 16. Keeping the final carry preserves the complete unsigned result.

Carry is not signed overflow

The same bits can encode different meanings. In four-bit two’s-complement arithmetic, 0111 represents 7. Adding 0001 produces 1000, which represents −8. No fifth-bit carry is required for this result, yet the mathematical sum 8 is outside the signed range −8 through 7.

That is signed overflow. It differs from losing an unsigned carry. Always state the width and interpretation before judging whether a result fits.

Delay and alternatives

A ripple-carry design connects each stage’s carry to the next stage. The logical composition is simple, but the carry dependency can limit settling speed. Carry-select and carry-lookahead designs reorganize work to trade more structure for different timing. Gate counts alone do not establish the speed of a real implementation.

Exercise and answer

Add four-bit 1111 and 0001 with an initial carry of 0. At position 0, 1 + 1 + 0 produces sum 0 and carry 1. Each higher position then adds 1 + 0 + 1, again producing sum 0 and carry 1. The complete unsigned result is 10000; the retained four-bit result is 0000.

Continue with memory and registers to preserve a computed result between operations.

Verification record

  • Sources assessed by Codex (assistant)
  • Example checks recorded
  • Independent human review pending

Selected claims have been assessed against the passages below. This record does not certify every sentence or guarantee correctness.

Inspect claims, evidence and limitations

Source assessment: . 4 of 4 selected claims marked supported by the assessor. This is not a coverage percentage for the article.

  1. The full-adder output satisfies A+B+Cin = S+2*Cout.

    Assessor finding: supported · definition · Article passage

    An arithmetic invariant independently checks all eight displayed rows.

  2. The four-bit teaching example retains the low bits and exposes an unsigned carry.

    Assessor finding: supported · model · Article passage

    The 13+6 column trace is original and independently recomputed.

  3. A signed interpretation differs from unsigned carry; the four-bit +7+1 example wraps to -8.

    Assessor finding: supported · model · Article passage

    The concrete interpretation is derived and recomputed; the cited slides provide the arithmetic context, not this exact worked example.

  4. Ripple carry has a serial carry dependency; other carry organizations trade structure and timing.

    Assessor finding: supported · definition · Article passage

    No measured speedup or technology-specific bound is asserted.

Reproducible checks

  • Full-adder rows and all four carry-propagation columns.

    Passed on 2026-10-27

    node --test --test-name-pattern='published gate, selector and full-adder tables cover all inputs and match their specifications' src/library/editorial.test.ts
  • Unsigned wrap and four-bit signed interpretation.

    Passed on 2026-10-27

    node --test --test-name-pattern='article substitutions, capacities, signed sums and completion answers are reproducible' src/library/exercises.test.ts

Limits and open work

  • The earlier MIT student-notes URL was removed after retrieval failures; the retained MIT OCW and Cornell sources support the selected claims.
  • No physical adder timing, area or power was measured.

Independent human review

Pending. No independent human reviewer has signed off this version.

Content fingerprint: 6de0592891e979917655c252e78afd69f0378e318b7470ad4a276286e257b4e7. An article change invalidates this assessment.

Sources

  1. MIT OpenCourseWare, Computation Structures — adder design tradeoffs
  2. Cornell CS 3410, Gates and Logic — definitions and arithmetic

Published by devutils · Updated · Original explanatory text; sources retain their own terms.