Edd Mann Developer

Binary Addition using Half and Full Adders within TypeScript

Recently, I watched an interesting talk about Binary Addition in the TypeScript Type System and thought it would be interesting to explore this concept in more depth. I wanted to pay close attention to how I could leverage the TypeScript type-system to help ensure validity in the final implementation.

The Bit

Starting from basic principles and working our way up we define the concept of a Bit and a fixed tuple of Bits using Recursive Conditional Types which will be available in TypeScript 4.1.

type Bit = 0 | 1;
type Bits<N extends number> = N extends N ? (number extends N ? Bit[] : _Bits<N, []>) : never;
type _Bits<N extends number, R extends Bit[]> = R["length"] extends N ? R : _Bits<N, [Bit, ...R]>;

From here, we create a simple factory function which, based on the desired Bit width size, pads out a supplied Partial type with trailing zeros. For this exercise we will be storing the Bits in Least Significant Bit order.

type PartialBits<N extends number> = Partial<Bits<N>>;

const Bits = <N extends number>(size: N) => (bits: PartialBits<N>): Bits<N> => {
  let result = Array<Bit>(size) as Bits<N>;

  for (let i = 0; i < size; i++) {
    result[i] = bits[i] || 0;
  }

  return result;
};

const Int8 = Bits(8);
const Int16 = Bits(16);

In doing this we are now levaging the type system to ensure that any supplied bits do not exceed the allocated represenation width. This is highlighted in the examples below.

Int8([1, 0, 1]); // valid
Int8([1, 0, 0, 1, 1, 0, 1, 0, 1]); // invalid
Int16([1, 0, 0, 1, 1, 0, 1, 0, 1]); // valid

The Logic Gates

So as to perform the final addition we need to provide the tooling around being able to construct Logic Gates based on supplied Bits. We are able to achieve this using the approach laid out below.

const and = (a: Bit, b: Bit): Bit => (a === 1 && b === 1 ? 1 : 0);
const or = (a: Bit, b: Bit): Bit => (a === 1 || b === 1 ? 1 : 0);
const invert = (a: Bit): Bit => (a ? 0 : 1);
const nand = (a: Bit, b: Bit): Bit => invert(and(a, b));
const nor = (a: Bit, b: Bit): Bit => invert(or(a, b));
const xor = (a: Bit, b: Bit): Bit => and(or(a, b), nand(a, b));

The Half Adder

The Half Adder is used to add two single bits A and B together, resulting in Sum and Carry outputs. We can build such a circuit using the following three approaches - the simplest of which is shown first, comprising of a single XOR and AND gate.

type Addition = {
  sum: Bit;
  carry: Bit;
};

type HalfAdder = (a: Bit, b: Bit) => Addition;

Simplest Half-Adder

Simplest Half-Adder

const halfAdder: HalfAdder = (a, b) => ({
  sum: xor(a, b),
  carry: and(a, b),
});

Half-Adder using only NAND Gates

Half-Adder using only NAND Gates

const halfAdderUsingNand: HalfAdder = (a, b) => {
  const ab = nand(a, b);
  return {
    sum: nand(nand(ab, a), nand(ab, b)),
    carry: nand(ab, ab),
  };
};

Half-Adder using only NOR Gates

Half-Adder using only NOR Gates

const halfAdderUsingNor: HalfAdder = (a, b) => {
  const carry = nor(nor(a, a), nor(b, b));
  return {
    sum: nor(carry, nor(a, b)),
    carry,
  };
};

The Full Adder

On its own a Half Adder is unable to perform the binary addition we hope to achieve. To achieve this we can use a Full Adder which is able to handle a subsquent third bit within the input - this being the Carry from a previous operation. This Adder can be constructed by using two Half Adders like so.

The Full Adder

type FullAdder = (a: Bit, b: Bit, c: Bit) => Addition;

const fullAdder = (halfAdder: HalfAdder): FullAdder => (a, b, c) => {
  const ab = halfAdder(a, b);
  const abc = halfAdder(ab.sum, c);
  return {
    sum: abc.sum,
    carry: or(ab.carry, abc.carry),
  };
};

Binary Addition

With this tooling in-place we can then construct an addition function. Based on a Bit result width size, we supply Partials of this Bit width and in-turn use the Full Adder to calculate the final result. Leveraging the type system we are able to ensure that we do permit inputs that are larger than the allocated return type.

const add = (fullAdder: FullAdder) => <N extends number>(size: N) => (
  a: PartialBits<N>,
  b: PartialBits<N>
): Bits<N> => {
  let carry: Bit = 0;
  let result = Array<Bit>(size) as Bits<N>;

  for (let i = 0; i < size; i++) {
    ({ sum: result[i], carry } = fullAdder(a[i] || 0, b[i] || 0, carry));
  }

  return result;
};

Finally, we can test out this implementation like so.

const addInt8 = add(fullAdder(halfAdder))(8);
const addInt16 = add(fullAdder(halfAdderUsingNand))(16);

addInt8(Int8([1, 0, 1, 1]), Int8([1, 0, 1])); // 01001000
addInt8(Int16([1, 0, 1, 1, 1, 1, 1, 1, 1]), Int8([1, 1, 1, 1])); // invalid
addInt16(Int16([1, 0, 1, 1, 1, 1, 1, 1, 1]), Int8([1, 1, 1, 1])); // 0011000001000000

Notice the type system again helping to enforce width rules with regards to Bits in the second example. If you are interested in experimenting with the demonstration you can visit this TypeScript playground.