Skip to content

Instantly share code, notes, and snippets.

@JoshuaKGoldberg
Last active May 3, 2023 18:25
Show Gist options
  • Save JoshuaKGoldberg/7543c2b3258fdce0a4ad70fd854ff7ff to your computer and use it in GitHub Desktop.
Save JoshuaKGoldberg/7543c2b3258fdce0a4ad70fd854ff7ff to your computer and use it in GitHub Desktop.
Silly Binary Arithmetic in TypeScript's Type System
type Bit = 0 | 1;
type BitOr<A extends Bit, B extends Bit> =
[A, B] extends [0, 0] ? 0 :
[A, B] extends [0, 1] | [1, 0] | [1, 1] ? 1 :
Bit
;
type BitAnd<A extends Bit, B extends Bit> =
[A, B] extends [0, 0] | [1, 0] | [0, 1] ? 0 :
[A, B] extends [1, 1] ? 1 :
Bit
;
type BitXor<A extends Bit, B extends Bit> =
[A, B] extends [0, 0] | [1, 1] ? 0 :
[A, B] extends [0, 1] | [1, 0] ? 1 :
Bit
;
// Output: [Xor, Carry]
type BitAdd<A extends Bit, B extends Bit> = [BitXor<A, B>, BitAnd<A, B>];
// Output: [Diff, Borrow]
type BitSubtract<A extends Bit, B extends Bit> =
[A, B] extends [0, 0] | [1, 1] ? [0, 0] :
[A, B] extends [1, 0] ? [1, 0] :
[A, B] extends [0, 1] ? [1, 1] :
[Bit, Bit]
;
type Int8 = [Bit, Bit, Bit, Bit, Bit, Bit, Bit, Bit];
type ZeroOut<TInt extends Bit[]> = {
[Index in keyof TInt]: 0;
};
type Zero = ZeroOut<Int8>;
type AssertExtends<Expected, Actual extends Expected = Expected> = Actual;
// From here on out, it's little Endian!
type ReplaceBits<Bits extends Bit[], Replacements> = {
[Index in keyof Bits]: Index extends keyof Replacements
? Replacements[Index]
: Bits[Index]
};
type One = ReplaceBits<Zero, [1]>;
type Two = ReplaceBits<Zero, [0, 1]>;
type Three = ReplaceBits<Zero, [1, 1]>;
type Four = ReplaceBits<Zero, [0, 0, 1]>;
type Five = ReplaceBits<Zero, [1, 0, 1]>;
type Six = ReplaceBits<Zero, [0, 1, 1]>;
type Seven = ReplaceBits<Zero, [1, 1, 1]>;
type Eight = ReplaceBits<Zero, [0, 0, 0, 1]>;
type Nine = ReplaceBits<Zero, [1, 0, 0, 1]>;
type Ten = ReplaceBits<Zero, [0, 1, 0, 1]>;
// [Sum, Carry]
type BitAddThree<A extends Bit = Bit, B extends Bit = Bit, C extends Bit = 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] :
[A, B, C] extends [1, 1, 1] ? [1, 1] :
[Bit, Bit, Bit]
;
type BitAdds<A extends Int8, B extends Int8> = {
[P in 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7]: BitAdd<A[P], B[P]>;
};
type AddInt8<
A extends Int8,
B extends Int8,
BitsAdded extends BitAdds<A, B> = BitAdds<A, B>,
And0 extends BitsAdded[0] = BitsAdded[0],
And1 extends BitAddThree<A[1], B[1], And0[1]> = BitAddThree<A[1], B[1], And0[1]>,
And2 extends BitAddThree<A[2], B[2], And1[1]> = BitAddThree<A[2], B[2], And1[1]>,
And3 extends BitAddThree<A[3], B[3], And2[1]> = BitAddThree<A[3], B[3], And2[1]>,
And4 extends BitAddThree<A[4], B[4], And3[1]> = BitAddThree<A[4], B[4], And3[1]>,
And5 extends BitAddThree<A[5], B[5], And4[1]> = BitAddThree<A[5], B[5], And4[1]>,
And6 extends BitAddThree<A[6], B[6], And5[1]> = BitAddThree<A[6], B[6], And5[1]>,
And7 extends BitAddThree<A[7], B[7], And6[1]> = BitAddThree<A[7], B[7], And6[1]>,
> = ReplaceBits<Zero, [
And0[0],
And1[0],
And2[0],
And3[0],
And4[0],
And5[0],
And6[0],
And7[0],
]>;
type OnePlusZero = AddInt8<One, Zero>;
type OnePlusOne = AddInt8<One, One>;
type OnePlusTwo = AddInt8<One, Two>;
type OnePlusThree = AddInt8<One, Three>;
type OnePlusFour = AddInt8<One, Four>;
type OnePlusFive = AddInt8<One, Five>;
type OnePlusSix = AddInt8<One, Six>;
type OnePlusSeven = AddInt8<One, Seven>;
type TwoPlusTwo = AddInt8<Two, Two>;
type ThreePlusFour = AddInt8<Three, Four>;
type FivePlusSix = AddInt8<Five, Six>;
type Validations = [
AssertExtends<OnePlusZero, One>,
AssertExtends<OnePlusThree, Four>,
AssertExtends<AddInt8<Two, Two>, Four>,
AssertExtends<AddInt8<Four, Three>, Seven>,
AssertExtends<AddInt8<Zero, Zero>, Zero>,
];
type InvertBit<B extends Bit> =
B extends 1 ? 0 :
B extends 0 ? 1 :
B
;
// [Borrow, Top, Bottom]: as in, -Borrow + (Top - Bottom)
// [Diff, Borrow]
type BitSubtractThree<A extends Bit = 0, B extends Bit = 0, C extends Bit = 0> =
[A, B, C] extends [0, 0, 0] ? [0, 0] :
[A, B, C] extends [1, 0, 0] ? [1, 1] : // ???
[A, B, C] extends [0, 1, 0] ? [1, 0] :
[A, B, C] extends [0, 0, 1] ? [1, 1] : // ???
[A, B, C] extends [1, 1, 0] ? [0, 0] :
[A, B, C] extends [1, 0, 1] ? [0, 1] : // ???
[A, B, C] extends [0, 1, 1] ? [0, 0] :
[A, B, C] extends [1, 1, 1] ? [1, 1] : // ???
[Bit, Bit]
;
type BitSubtracts<A extends Int8, B extends Int8> = Int8 & {
[P in 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7]: BitSubtract<A[P], B[P]>;
};
type SubtractInt8<
A extends Int8,
B extends Int8,
BitsSubtracted extends BitSubtracts<A, B> = BitSubtracts<A, B>,
Sub0 extends BitsSubtracted[0] = BitsSubtracted[0],
Sub1 extends BitSubtractThree<Sub0[1], A[1], B[1]> = BitSubtractThree<Sub0[1], A[1], B[1]>,
Sub2 extends BitSubtractThree<Sub1[1], A[2], B[2]> = BitSubtractThree<Sub1[1], A[2], B[2]>,
Sub3 extends BitSubtractThree<Sub2[1], A[3], B[3]> = BitSubtractThree<Sub2[1], A[3], B[3]>,
Sub4 extends BitSubtractThree<Sub3[1], A[4], B[4]> = BitSubtractThree<Sub3[1], A[4], B[4]>,
Sub5 extends BitSubtractThree<Sub4[1], A[5], B[5]> = BitSubtractThree<Sub4[1], A[5], B[5]>,
Sub6 extends BitSubtractThree<Sub5[1], A[6], B[6]> = BitSubtractThree<Sub5[1], A[6], B[6]>,
Sub7 extends BitSubtractThree<Sub6[1], A[7], B[7]> = BitSubtractThree<Sub6[1], A[7], B[7]>,
> = ReplaceBits<Zero, [
Sub0[0],
Sub1[0],
Sub2[0],
Sub3[0],
Sub4[0],
Sub5[0],
Sub6[0],
Sub7[0],
]>;
type ZeroMinusZero = SubtractInt8<Zero, Zero>;
type OneMinusZero = SubtractInt8<One, Zero>;
type TwoMinusOne = SubtractInt8<Two, One>;
type SevenMinusFour = SubtractInt8<Seven, Four>;
type EightMinusThree = SubtractInt8<Eight, Three>;
type SubtractionValidations = [
AssertExtends<Zero, ZeroMinusZero>,
AssertExtends<One, OneMinusZero>,
AssertExtends<One, TwoMinusOne>,
AssertExtends<Three, SevenMinusFour>,
AssertExtends<Five, EightMinusThree>,
];
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment