bitstring manip in typescript type system

bitstring.ts

/**
 * 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

Any practical example of how to use it?
All I've managed to do is to get compile-time message of something is wrong.

@alexanderfedinatnasa Lines 10-21 are some examples how to use it. This code is not actually useful it just demonstrates the new type system.

Also make sure this runs on tsc >= 4.1.0 as older versions do not support this. You can open typescriptlang.org/play and paste the code there

😐

"bruh" - Socrates