Created
November 9, 2020 04:34
-
-
Save cleoold/c278c1689b41a25ce1417eb4c07877f4 to your computer and use it in GitHub Desktop.
Revisions
-
cleoold created this gist
Nov 9, 2020 .There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,170 @@ /** * Binary string and bitwise arithmetic entirely in TypeScript's type system * (with template string types). * * Requires version >= 4.1.0 * * Hover on the types to see the results. */ type A = '010101' type B = '000101' type ANot = BitNot<A> type AAndB = BitAnd<A, B> type AOrB = BitOr<A, B> type AXorB = BitOr<BitAnd<A, BitNot<B>>, BitAnd<BitNot<A>, B>> type ALeftSh = BitLeftShift<A> type ARightShLogical = BitRightShiftLogical<A> type AArightShArith = BitRightShiftArith<A> type APlusB = Adder<A, B> type AMinusB = Car<Adder<A, Car<Adder<BitNot<B>, '1'>>>> /* IMPLEMENTATION */ type Reverse<S> = S extends '' ? '' : S extends `${infer S0}${infer Ss}` ? `${Reverse<Ss>}${S0}` : never type Car<L> = L extends [infer L0, ... infer _] ? L0 : L extends `${infer L0}${infer _}` ? L0 : never type BinaryDigit = '0' | '1' type BitNot<Num> = Num extends '' ? '' : Num extends '0' ? '1' : Num extends '1' ? '0' : Num extends `${infer Num_0}${infer Num_s}` ? Num_0 extends BinaryDigit ? `${BitNot<Num_0>}${BitNot<Num_s>}` : never : never type BitAnd<Num1, Num2> = Num1 extends '' ? Num2 : Num2 extends '' ? Num1 : [Num1, Num2] extends (['0', '0'] | ['0', '1'] | ['1', '0']) ? '0' : [Num1, Num2] extends ['1', '1'] ? '1' : [Num1, Num2] extends [`${infer Num1_0}${infer Num1_s}`, `${infer Num2_0}${infer Num2_s}`] ? [Num1_0, Num2_0] extends [BinaryDigit, BinaryDigit] ? `${BitAnd<Num1_0, Num2_0>}${BitAnd<Num1_s, Num2_s>}` : never : never type BitOr<Num1, Num2> = Num1 extends '' ? Num2 : Num2 extends '' ? Num1 : [Num1, Num2] extends ['0', '0'] ? '0' : [Num1, Num2] extends (['0', '1'] | ['1', '0'] | ['1', '1']) ? '1' : [Num1, Num2] extends [`${infer Num1_0}${infer Num1_s}`, `${infer Num2_0}${infer Num2_s}`] ? [Num1_0, Num2_0] extends [BinaryDigit, BinaryDigit] ? `${BitOr<Num1_0, Num2_0>}${BitOr<Num1_s, Num2_s>}` : never : never type BitLeftShift<Num> = Num extends '' ? '' : Num extends `${infer _}${infer Num_s}` ? `${Num_s}0` : never type BitRightShiftHelper<Num> = Num extends '' | BinaryDigit ? '' : Num extends `${infer Num_0}${infer Num_s}` ? Num_0 extends BinaryDigit ? `${Num_0}${BitRightShiftHelper<Num_s>}` : never : never type BitRightShiftLogical<Num> = Num extends '' ? '' : `0${BitRightShiftHelper<Num>}` type BitRightShiftArith<Num> = Num extends '' ? '' : Car<Num> extends BinaryDigit ? `${Car<Num>}${BitRightShiftHelper<Num>}` : never type HalfAdder<A, B> = [A, B] extends ['0', '0'] ? ['0', '0'] : [A, B] extends (['0', '1'] | ['1', '0']) ? ['1', '0'] : [A, B] extends ['1', '1'] ? ['0', '1'] : never type AdderLittleEndian<Num1, Num2, Carry = '0', Result extends string = ''> = Num1 extends '' ? Num2 extends '' ? [Result, Carry] : Num2 extends `${infer Num2_0}${infer Num2_s}` ? HalfAdder<Num2_0, Carry> extends [infer SumBit, infer NextCarry] ? SumBit extends string ? AdderLittleEndian<'', Num2_s, NextCarry, `${Result}${SumBit}`> : never : never : never : Num2 extends '' ? AdderLittleEndian<Num2, Num1, Carry, Result> : [Num1, Num2] extends [`${infer Num1_0}${infer Num1_s}`, `${infer Num2_0}${infer Num2_s}`] ? HalfAdder<Num1_0, Num2_0> extends [infer SumBit, infer NextCarry] ? Carry extends '0' ? SumBit extends BinaryDigit ? AdderLittleEndian<Num1_s, Num2_s, NextCarry, `${Result}${SumBit}`> : never : Carry extends '1' ? SumBit extends '0' ? AdderLittleEndian<Num1_s, Num2_s, NextCarry, `${Result}1`> : SumBit extends '1' ? AdderLittleEndian<Num1_s, Num2_s, '1', `${Result}0`> : never : never : never : never type Adder<A extends string, B extends string> = AdderLittleEndian<Reverse<A>, Reverse<B>> extends [infer Result, infer Carry] ? Reverse<Result> extends infer RealResult ? [ RealResult, { carry: Carry, overflowSigned: SignedOverflowChecker<Car<A>, Car<B>, Car<RealResult>>, overflowUnsigned: UnsignedOverflowChecker<Carry> } ] : never : never type SignedOverflowChecker<A, B, R> = [A, B, R] extends (['0', '0', '1'] | ['1', '1', '0']) ? true : false type UnsignedOverflowChecker<Carry> = Carry extends '1' ? true : false