Binary Addition

Add two binary numbers bit for bit, carry included, the way hardware does it.

The inputs to BinaryAdd<A, B> are two binary numbers represented as tuples of bits, and the rule that makes the challenge interesting is that they must never be translated out of binary. Counting tricks with tuple lengths are off the table. Instead you model a real full adder: walk both numbers from the least significant bit, compute a sum bit and a carry bit at each position, and propagate the carry leftwards. You can assume the two inputs always have the same length.

type Add1 = BinaryAdd<[0], [1]> // expected to be [1]
type Add2 = BinaryAdd<[1], [1]> // expected to be [1, 0]
type Add3 = BinaryAdd<[1, 1, 0], [0, 0, 1]> // expected to be [1, 1, 1]

Two techniques carry the solution: encoding a truth table as an object type you index into, and recursing over tuples from the end rather than the front.

Detailed Explanation

The full solution:

type Bit = 1 | 0
 
type FullAdder<A extends Bit, B extends Bit, C extends Bit> = {
  '000': [0, 0]
  '001': [0, 1]
  '010': [0, 1]
  '011': [1, 0]
  '100': [0, 1]
  '101': [1, 0]
  '110': [1, 0]
  '111': [1, 1]
}[`${A}${B}${C}`]
 
type AddBits<A extends Bit[], B extends Bit[], Carry extends Bit = 0> = [
  A,
  B,
] extends [
  [...infer RestA extends Bit[], infer LastA extends Bit],
  [...infer RestB extends Bit[], infer LastB extends Bit],
]
  ? FullAdder<LastA, LastB, Carry> extends [
      infer NextCarry extends Bit,
      infer Sum extends Bit,
    ]
    ? [...AddBits<RestA, RestB, NextCarry>, Sum]
    : never
  : Carry extends 1
    ? [1]
    : []
 
type BinaryAdd<A extends Bit[], B extends Bit[]> = AddBits<A, B>

The design mirrors how a CPU adds numbers: a chain of full adders, each taking two bits plus a carry-in and producing a sum bit plus a carry-out. Let's build it up.

The truth table as a type

A full adder has eight possible inputs: two bits and a carry, each 0 or 1. Rather than nesting eight conditional types, FullAdder writes the truth table down literally as an object type and indexes into it:

• The key `${A}${B}${C}` uses a template literal type to stringify the three bits. For A = 1, B = 0, C = 1 it evaluates to the literal '101'.
• Indexing the object with that key looks up the row: '101' maps to [1, 0], meaning carry-out 1, sum 0 (because 1 + 0 + 1 = 2, which is 10 in binary).

A quick intermediate check:

[object Object]

This lookup-table idiom is worth remembering: whenever a type-level function has a small, finite input space, an indexed object type is flatter and easier to audit than a tower of ternaries.

Recursing from the least significant bit

Addition starts at the right end of a number, so AddBits must peel bits off the end of each tuple, not the front. The pattern [...infer RestA extends Bit[], infer LastA extends Bit] does exactly that: the rest element matches everything before the last position, and LastA captures the final bit. Matching both tuples at once inside [A, B] extends [...] keeps the two destructurings in a single conditional.

The inline extends Bit[] / extends Bit constraints on infer matter. Without them, LastA would only be known to be unknown and couldn't be passed to FullAdder, which requires Bit.

Threading the carry

Each recursive step does three things:

• Runs FullAdder<LastA, LastB, Carry> on the current column.
• Destructures the result into NextCarry and Sum with a second infer (so the lookup is evaluated once, not twice).
• Emits [...AddBits<RestA, RestB, NextCarry>, Sum]: the sum bit goes on the right, and the carry travels left into the recursive call.

Tracing BinaryAdd<[1], [1]>: the only column is FullAdder<1, 1, 0> = [1, 0], so the result is [...AddBits<[], [], 1>, 0]. Both tuples are now empty, so the destructuring pattern fails and we reach the base case.

The base case and the extra digit

When both tuples are exhausted, one question remains: is there a leftover carry? Carry extends 1 ? [1] : [] answers it. If the final carry is 1, the result grows one digit longer than the inputs. That's how [1] + [1] becomes [1, 0], and how thirteen 1s plus thirteen 1s produce a fourteen-bit result in the test suite. If the carry is 0, the empty tuple spreads into nothing and the result keeps the input length, which is why BinaryAdd<[0], [1]> is just [1] with no leading zero.

Edge cases the tests cover

• BinaryAdd<[0], [1]> → [1]: no carry ever fires, so no extra digit is prepended.
• The thirteen-bit all-ones case: the carry ripples through every single column, verifying the recursion depth is comfortable and the final [1] lands in front.
• [1, 0, 1, 0, 1, 1, 1, 0] + [1, 0, 0, 0, 1, 1, 0, 0] → a nine-bit result: carries start and stop mid-number, exercising five of the eight adder rows along the way.

The shape generalizes: a truth table for the single step, end-first recursion with a carry accumulator. The same skeleton extends to type-level subtraction or multiplication.