Binary Arithmetic in the TypeScript Type System
October 11, 2019 💾 Download the slides here!
(updated 10/19 with typo fixes)
Preamble
Throughout the tech stacks and projects you could work on, the idea of a language is constant. Language describes how reality should be.
JavaScript describes how to create objects and manipulate them in an environment such as a browser, Node, or Deno. TypeScript contains that JavaScript language and a types language to describe the shapes your objects an be.
Take this
Movie
description:
type Movie = {
name: string;
rating: number;
};
We’re declaring in the TypeScript type system that all “Movie” objects must have two properties:

A
name
property of typestring

A
rating
property of typenumber
This TypeScript snippet contains JavaScript code declaring the
creation of a
movie
variable and type
system code declaring the type of that variable to be
Movie
:
const movie: Movie = {
name: "This is Spinal Tap",
rating: 11,
};
Cool.
The type system can also represent
“it’s one of these” (union) types such as
this RawId
:
type RawId = number  string;
Anything of type RawId may be either a
number
or a
string
. In this snippet,
the id
variable is happy as
either of those:
let id: RawId;
id = 123;
id = "abc";
…but if we give it something else, the type system complains:
// Type 'number' is not assignable to type 'RawId'
id = false;
Also cool.
Goals
The end goal of this rant is to implement binary arithmetic in the TypeScript type system. That means we’ll have to:
 Create types representing computer bits
 Create types representing operations performed on those bits
 Perform fancy operations on those types
Bits
To start:
type Bit = 0  1;
Variables of type Bit
can
be either the number
0
or the number
1
.
Given a myBit
variable
declared of type Bit
, these
values are fine:
let bit: Bit;
bit = 0;
bit = 1;
…but, as with the
id
variable above, values
not of type Bit
(0
or 1
) are not allowed:
// Type 'number' is not assignable to type 'Bit'.
myBit = 2;
myBit = 1 + 1;
Bit Values
We can also represent the more specific bit values of
0
and
1
within the type system.
Just as we declared a general
Bit
type to represent
anything that’s either of those, we can declare types to be
those specific values:
type BitZero = 0;
type BitOne = 1;
Those types exist only within the type system. If you wanted to think of the operations we’re running here as having equivalents in plain old JavaScript, the equivalent would be:
const BitZero = 0;
const BitOne = 1;
Generic Types
In some cases we’ll want to describe a new type based off a previous type.
type BitFlip<T> = T extends 0 ? 1 : 0;
This BitFlip
type is a
generic, or templated type.

If the original type
T
is0
, then the new type is1
. 
Otherwise, the new type is
0
.
We’ll use “extends” as a sortofequal operator. (It’s more of a “can be described by” operator.)
Given a usage of BitFlip
,
we can clue in to what it’ll result in by filling in the code:

type BitOne = BitFlip<0>;

type BitOne = 0 extends 0 ? 1 : 0;
type BitOne = 1;
Type Phrasing
Another way of looking at the these types could be to translate them to functional TypeScript code. If a generic type takes in a previous type, then we can consider those equivalent to arguments passed to a function. The new type could be the returned value from that function.
function BitFlip(T) {
return T === 0 ? 1 : 0;
}
Voila! Subsequent examples here will come with both the type system and traditional code variants.
Type Safety
Problem: how do we restrict the input types… of our
type
s?
Suppose someone passes an invalid template type to
BitFlip
:
// We probably want some kind of type// system complaint, right?
type Wat = BitFlip<"Nope">;
Types allow ’extends
’ with
generics to limit what you’re allowed to give them. If we add
an extends Bit
to the
BitFlip
’s
T
:
type BitFlip<T extends Bit> = T extends 0 ? 1 : 0;
…we’ll be told by the type system when we pass the wrong types in:
// Type '"Nope"' does not satisfy the constraint 'Bit'.
type Wat = BitFlip<"Nope">;
That’s the equivalent of adding a parameter type declaration to a regular function.
function BitFlip(T: Bit) {
return T === 0 ? 1 : 0;
}
Tuple Types!
Generics can take in multiple templated types. Each is allowed
its own extends
clause.
Even better, we can perform operations such as
extends
on “tuple” types,
which arefixedlength arrays containing types at specific
indices:
type BitAnd<A extends Bit, B extends Bit> = [A, B] extends [1, 1] ? 1 : 0;
In other words, the
BitAnd
type takes in two
bits: A
and
B
. If
[A, B]
is
[1, 1]
(so both
A
and
B
are
1
), then the resultant type
is 1
. In any other case the
resultant type is 0
.
function BitAnd(A: Bit, B: Bit) {
return A === 1 && B === 1 ? 1 : 0;
}
In other other words, the returned type is
1
if both
A
and
B
are, and
0
otherwise.
Bit Addition
We’re getting closer to binary arithmetic! First: how do you
add two bits (0  1
)?

If both are
0
, the sum is0
. 
If one is
0
and the other is1
, the sum is1
. 
If both are
1
, the sum is0
, with a1
carried over to the next bit.
Let’s show that in code:
// Output: [Sum, Carry]
type BitAdd<A extends Bit, B extends Bit> = [A, B] extends [0, 0]
? [0, 0]
: [A, B] extends [1, 0]  [0, 1]
? [1, 0]
: [0, 1];
Wowee.
Amusingly, the type system version of
BitAdd
is a little bit more
concise than its JavaScript equivalent:
function BitAdd(A: Bit, B: Bit) {
if (A === 0 && B === 0) return [0, 0];
if (A === 0 && B === 1) return [1, 0];
if (A === 1 && B === 0) return [0, 1];
return [0, 1];
}
Introducing Integers
An “eight bit integer” is an integer value represented using… eight bits!
The value of an Int8
is the
sum of its bits, where each bit contributes twice as much as
the previous to the total.

If all bits are
0
, the value is0
. 
If the first bit is
1
, the value is1
. 
If the second bit is
1
, the value is2
. 
If the first and second bits are
1
, the value is1+2 = 3
. 
If the third bit is
1
, the value is4
.
type Int8 = [Bit, Bit, Bit, Bit, Bit, Bit, Bit, Bit];
Tada! 🎉
type Zero = [0, 0, 0, 0, 0, 0, 0, 0];
type One = [1, 0, 0, 0, 0, 0, 0, 0];
type Two = [0, 1, 0, 0, 0, 0, 0, 0];
type Three = [1, 1, 0, 0, 0, 0, 0, 0];
type Four = [0, 0, 1, 0, 0, 0, 0, 0];
// ...and so on...
It’s getting tedious to type out these values using all 8 bits manually. There’s an easier way to generate them…
Mapped Types
A “mapped type” is one that transforms the properties of some input type. It… maps them! I want to make a “ZeroOut” helper that takes in an original array of bits and converts all its values to 0.
type ZeroOut<Ints extends Bit[]> = {
[Index in keyof Ints]: 0;
};
Seen in JavaScript:
function ZeroOut(Ints: Bit[]) {
return Ints.map(() => 0);
}
Array#map
and our mapped
types come from the same term – to map from one type
to another. Map!
More Mapping
Taking mapped types one step further, we can replace just a subset of an original type. This mapped type uses conditional logic to swap out some bits from an original, input array of bits.
type ReplaceBits<Bits extends Bit[], Replacements extends Bit[]> = {
[Index in keyof Bits]: Index extends keyof Replacements
? Replacements[Index]
: Bits[Index];
};
Running through the logic in order:

Bits
andReplacements
are input types, both of which must be describable asBit[]
s 
The resultant type maps over the
Index
ed values inBits

Each of the new, mapped values is one of two things:

If the
Index
exists in theReplacements
array, we’ll use that (replacing) value 
If not, use the original value under
Bits[Index]

If the
type One = ReplaceBits<Zero, [1]>; // [1, 0, 0, 0, 0, 0, 0, 0]
type Two = ReplaceBits<Zero, [0, 1]>; // [0, 1, 0, 0, 0, 0, 0, 0]
type Three = ReplaceBits<Zero, [1, 1]>; // [1, 1, 0, 0, 0, 0, 0, 0]
In JavaScript:
function ReplaceBits(Bits: Bit[], Replacements: Bit[]) {
return Bits.map((Original, Index) => {
return Index in Object.keys(Replacements)
? Replacements[Index]
: Original;
});
}
Addition with Bits
As with decimal (10) based addition, numbers overflow as “carries” to the next column. Since this is binary, you can overflow a 1.
Suppose you wanted to add
110
to
111
.

The smallest bit (index 0) is
0 + 1 = 1
, with nothing carried over 
The index 1 bit is
1 + 1 = 0
, with1
carried over 
The index 2 bit is
1 + 1 + 1
because of that1
carried over, making it1
with another1
carried over 
The index 3 bit is
1
from being carried over
110 + 111 = 1101
.
Representing each column’s three bits of addition in the type system:
// Output: [Sum, Carry]
type BitAddThree<A extends Bit, B extends Bit, C extends Bit> = [
A,
B,
C
] extends [0, 0, 0]
? [0, 0]
: [A, B, C] extends [1, 0, 0]  [0, 1, 0]  [0, 0, 1]
? [1, 0]
: [A, B, C] extends [1, 1, 0]  [1, 0, 1]  [0, 1, 1]
? [0, 1]
: [1, 1];
If you think that’s a mouthful, take a look at the JavaScript equivalent:
function BitAddThree(A: Bit, B: Bit, C: Bit) {
if (A === 0 && B === 0 && C === 0) return [0, 0];
if (
(A === 1 && B === 0 && C === 0) 
(A === 0 && B === 1 && C === 0) 
(A === 0 && B === 0 && C === 1)
)
return [1, 0];
if (
(A === 1 && B === 1 && C === 0) 
(A === 1 && B === 0 && C === 1) 
(A === 0 && B === 1 && C === 1)
)
return [0, 1];
return [1, 1];
}
Getting Ready to Rock! 🤘
…how do we set up bit adds of all columns in our input binary?
Also, adding eight bits together means we might have to carry
a bit from index 0
to
1
, then from index
1
to
2
, etc. all the way to the
last bit.
…how do we store variables in our types?
Helper: Get [Sum, Carry]s of Two Int8s
In theory, we could add our bit columns together by mapping
the known shared keys from them,
0
through
8
, to the
BitAdd
of the those two
bits.
// Output: [[Sum, Carry], [Sum, Carry], [Sum, Carry], ...]
type BitAdds<A extends Int8, B extends Int8> = {
[P in 0  1  2  3  4  5  6  7]: BitAdd<A[P], B[P]>;
};
Seeing this in JavaScript, it’s a little cleaner:
function BitAdds(A: Int8, B: Int8) {
return [0, 1, 2, 3, 4, 5, 6, 7, 8].map((P) => BitAdd(A[P], B[P]));
}
(this utility isn’t necessary for the final result  it’s just cool)
Generic Parameter Defaults
We’ll use a quirk of generics to store variables within a type.
type ContrivedExample<
A extends Bit,
B extends Bit,
C extends BitAnd<A, B> = BitAnd<A, B>
> = [A, B, C];
The C
generic is the
equivalent of a variable:

We restrict it to the
BitAnd<A, B>
type withextends

and if not provided, it defaults to
BitAnd<A, B>
with=
Tl;dr: C = BitAnd<A, B>
.
We’re Almost Ready!
So exciting! We’re almost ready to implement 8 bit integer additions in the type system.
Before we get into the TypeScript implementation, here’s the JavaScript equivalent for reference:
function Int8Add(A: Int8, B: Int8) {
// Grab the Sum and Carry for the result's first bit
const At0 = BitAdd(A[0], B[0]);
// The result at each index is the Sum from that index + the previous Carry.
const At1 = BitAddThree(A[1], B[1], At0[1]);
const At2 = BitAddThree(A[2], B[2], At1[1]);
const At3 = BitAddThree(A[3], B[3], At2[1]);
const At4 = BitAddThree(A[4], B[4], At3[1]);
const At5 = BitAddThree(A[5], B[5], At4[1]);
const At6 = BitAddThree(A[6], B[6], At5[1]);
const At7 = BitAddThree(A[7], B[7], At6[1]);
return [At0[0], At1[0], At2[0], At3[0], At4[0], At5[0], At6[0], At7[0]];
}
…and now, 8 bit binary arithmetic in the TypeScript type system! ✨
type Int8Add<
A extends Int8,
B extends Int8,
// Grab the Sum and Carry for the result's first bit
At0 extends BitAdd<A[0], B[0]> = BitAdd<A[0], B[0]>,
// The result at each index is the Sum from that index + the previous Carry.
At1 extends BitAddThree<A[1], B[1], At0[1]> = BitAddThree<
A[1],
B[1],
At0[1]
>,
At2 extends BitAddThree<A[2], B[2], At1[1]> = BitAddThree<
A[2],
B[2],
At1[1]
>,
At3 extends BitAddThree<A[3], B[3], At2[1]> = BitAddThree<
A[3],
B[3],
At2[1]
>,
At4 extends BitAddThree<A[4], B[4], At3[1]> = BitAddThree<
A[4],
B[4],
At3[1]
>,
At5 extends BitAddThree<A[5], B[5], At4[1]> = BitAddThree<
A[5],
B[5],
At4[1]
>,
At6 extends BitAddThree<A[6], B[6], At5[1]> = BitAddThree<
A[6],
B[6],
At5[1]
>,
At7 extends BitAddThree<A[7], B[7], At6[1]> = BitAddThree<
A[7],
B[7],
At6[1]
>
> = [At0[0], At1[0], At2[0], At3[0], At4[0], At5[0], At6[0], At7[0]];
We did it!
Next Steps
Extra credit: what else can you make with this?
BitSubtract
?Int8Multiply
?
Even better, use your knowledge for good: contribute to DefinitelyTyped!
 Is your library missing? Add it?
 Are your types wrong? Fix them!
Thanks for reading!