Skip to content

Instantly share code, notes, and snippets.

@zachhardesty7

zachhardesty7/index.ts

Last active August 9, 2022 15:49
Show Gist options
  • Save zachhardesty7/81679a314603786b1ec9106ac82c3444 to your computer and use it in GitHub Desktop.
Save zachhardesty7/81679a314603786b1ec9106ac82c3444 to your computer and use it in GitHub Desktop.
Download ZIP
TS: binary math!
Raw
index.ts
// copyright 2022 Zach Hardesty
// want to check this out in the TypeScript playground?
// visit the following link to automatically see the latest version!
// https://www.typescriptlang.org/play?jsx=0#gist/81679a314603786b1ec9106ac82c3444
// DEBUGGING HELP
// https://blog.andrewbran.ch/debugging-the-type-script-codebase/
// https://www.typescriptlang.org/docs/handbook/compiler-options.html
// https://medium.com/jspoint/typescript-compilation-the-typescript-compiler-4cb15f7244bc
// https://servingniches.org/posts/2019-05-28___debugging_serverside_typescript_with_webstorm/
// https://github.com/microsoft/TypeScript/pull/45711 // recursive tail call optimization PR
// DEBUGGING AST - maybe helpful, untested if it even works
// https://mihailik.github.io/teapo/
// https://astexplorer.net/
// #region - MATH - started this since version numbers need to be added together for part 1
type AddBit<Bit1 extends string, Bit2 extends string> = Bit1 | Bit2 extends Zero
? Zero
: Bit1 | Bit2 extends One
? "?"
: One
type SubBit<Bit1 extends string, Bit2 extends string> = Bit2 extends Zero
? Bit1
: Bit1 | Bit2 extends One
? Zero
: "?"
/**
* lots of `Zero` & `One` use here. undecided if I like it. this way makes it quicker
* to write, but maybe a bit harder to read
*/
type AddBitCarry<
Bit1 extends string,
Bit2 extends string,
Carry extends string = Zero,
> = Bit1 | Bit2 | Carry extends Zero // all Zero
? [Zero, Zero]
: Bit1 | Bit2 | Carry extends One // all One
? [One, One]
: (Bit1 | Bit2) & (Bit1 | Carry) & (Bit2 | Carry) extends One // One in any 2 out of the 3 positions
? [Zero, One]
: [One, Zero]
type SubBitCarry<
Bit1 extends string,
Bit2 extends string,
Carry extends string = Zero,
> = Bit2 | Carry extends Zero // noop, [x, 0, 0]
? [Bit1, Zero]
: Bit1 | Bit2 extends One // cancel, use carry, [1, 1, x]
? [Carry, Carry]
: (Bit1 | Bit2) & (Bit1 | Carry) extends Zero
? [One, One]
: [Zero, Bit2]
/** v1 does hiding the internal accumulators really matter? */
// type _AddBinaryCarry<
// Bin1 extends string,
// Bin2 extends string,
// // internal
// Out extends string = "",
// Carry extends string = "0"
// > = Bin1 | Bin2 extends "" // base case, both are empty, terminate recursion and return
// ? Carry extends "1"
// ? `1${Out}`
// : Out
// : Bin1 extends `${infer Rest1}${Bit}` // pick off the last bit of each binary string
// ? Bin1 extends `${Rest1}${infer B1}`
// ? Bin2 extends `${infer Rest2}${Bit}`
// ? Bin2 extends `${Rest2}${infer B2}`
// ? _AddBinaryCarry<
// Rest1,
// Rest2,
// `${AddBitCarry<B1, B2, Carry>[0]}${Out}`,
// AddBitCarry<B1, B2, Carry>[1]
// >
// : never
// : never
// : never
// : never
// /** v2 handle sparse bit patterns */
// type _AddBinaryCarry<
// Bin1 extends string,
// Bin2 extends string,
// // internal
// Out extends string = "",
// Carry extends string = "0"
// > = Bin1 | Bin2 extends "" // base case, both are empty, terminate recursion and return
// ? Carry extends "1"
// ? `1${Out}`
// : Out
// : Bin1 extends `${infer Rest1}${Bit}` // pick off the last bit of each binary string
// ? Bin1 extends `${Rest1}${infer B1}`
// ? Bin2 extends `${infer Rest2}${Bit}`
// ? Bin2 extends `${Rest2}${infer B2}`
// ? _AddBinaryCarry<
// Rest1,
// Rest2,
// `${AddBitCarry<B1, B2, Carry>[0]}${Out}`,
// AddBitCarry<B1, B2, Carry>[1]
// >
// : never
// : _AddBinaryCarry<
// Rest1,
// Bin2,
// `${AddBitCarry<B1, "0", Carry>[0]}${Out}`,
// AddBitCarry<B1, "0", Carry>[1]
// >
// : never
// : Bin2 extends `${infer Rest2}${Bit}`
// ? Bin2 extends `${Rest2}${infer B2}`
// ? _AddBinaryCarry<
// Bin1,
// Rest2,
// `${AddBitCarry<Zero, B2, Carry>[0]}${Out}`,
// AddBitCarry<Zero, B2, Carry>[1]
// >
// : never
// : never
/** v3 */
/**
* recursive depth might be pretty limited but fine for now. `Add2Bit` inline would double depth
*
* mismatched binary length inputs are invalid, but could be left padded with zero
*
* @todo optimization
*
* @version 3 handle sparse bit patterns better
*/
type AddBinaryCarry<
Bin1 extends string,
Bin2 extends string,
// internal
Out extends string = "",
Carry extends string = "0",
> = Bin1 | Bin2 extends "" // base case, both are empty, terminate recursion and return
? Carry extends "1"
? `1${Out}`
: Out
: Bitify<Bin1> extends `${infer Rest1}${Bit}` // pick off the last bit of each binary string
? Bitify<Bin1> extends `${Rest1}${infer B1}`
? Bitify<Bin2> extends `${infer Rest2}${Bit}`
? Bitify<Bin2> extends `${Rest2}${infer B2}`
? AddBinaryCarry<
Rest1,
Rest2,
`${AddBitCarry<B1, B2, Carry>[0]}${Out}`,
AddBitCarry<B1, B2, Carry>[1]
>
: never
: never
: never
: never
type A = Zero
// type A = One
type B = Zero
// type B = One
// type C = Zero
type C = One
// logic used for carry bit. true if any 2 of 3 inputs are both One
type TEST_ADD_1 = (A | B) & (A | C) & (B | C) extends One ? true : false
type TEST_ADD_20 = Expect<AddBinaryCarry<"001", "010">, "011">
type TEST_ADD_21 = Expect<AddBinaryCarry<"001", "001">, "010">
type TEST_ADD_22 = Expect<AddBinaryCarry<"001", "011">, "100">
type TEST_ADD_23 = Expect<AddBinaryCarry<"011", "011">, "110">
type TEST_ADD_24 = Expect<AddBinaryCarry<"100", "100">, "1000">
type TEST_ADD_25 = Expect<AddBinaryCarry<"111", "111">, "1110">
type TEST_ADD_26 = Expect<
AddBinaryCarry<"01010101010101010101", "10101010101010101010">,
"11111111111111111111"
>
type TEST_ADD_27 = Expect<
AddBinaryCarry<"11000000000000000001", "10000000000000000000">,
"101000000000000000001"
>
type TEST_ADD_30 = Expect<AddBinaryCarry<"1", "0000">, "0001">
type TEST_ADD_31 = Expect<AddBinaryCarry<"0000", "1">, "0001">
type TEST_ADD_32 = Expect<AddBinaryCarry<"", "1">, "1">
type TEST_ADD_33 = Expect<AddBinaryCarry<"1", "">, "1">
type TEST_ADD_34 = Expect<AddBinaryCarry<"", "">, "">
/** negatives truncate to {@link Zero} */
type SubBinaryCarry<
Bin1 extends string,
Bin2 extends string,
// internal
Out extends string = "",
Carry extends string = "0",
> = Bin1 | Bin2 extends "" // base case, both are empty, terminate recursion and return
? Carry extends "1"
? Zero
: Trim<Out>
: Bitify<Bin1> extends `${infer Rest1}${Bit}` // pick off the last bit of each binary string
? Bitify<Bin1> extends `${Rest1}${infer B1}`
? Bitify<Bin2> extends `${infer Rest2}${Bit}`
? Bitify<Bin2> extends `${Rest2}${infer B2}`
? SubBinaryCarry<
Rest1,
Rest2,
`${SubBitCarry<B1, B2, Carry>[0]}${Out}`,
SubBitCarry<B1, B2, Carry>[1]
>
: never
: never
: never
: never
type TEST_SUB_20 = Expect<SubBinaryCarry<"011", "010">, "1">
type TEST_SUB_21 = Expect<SubBinaryCarry<"010", "001">, "1">
type TEST_SUB_22 = Expect<SubBinaryCarry<"100", "011">, "1">
type TEST_SUB_23 = Expect<SubBinaryCarry<"110", "011">, "11">
type TEST_SUB_24 = Expect<SubBinaryCarry<"1000", "100">, "100">
type TEST_SUB_25 = Expect<SubBinaryCarry<"1110", "111">, "111">
type TEST_SUB_26 = Expect<
SubBinaryCarry<"11111111111111111111", "10101010101010101010">,
"1010101010101010101"
>
type TEST_SUB_27 = Expect<
SubBinaryCarry<"101000000000000000001", "10000000000000000000">,
"11000000000000000001"
>
type TEST_SUB_28 = Expect<
SubBinaryCarry<
"101000000000000000001000101000000000000000001000",
"010000000000000000000000010000000000000000000000"
>,
"11000000000000000001000011000000000000000001000"
>
type TEST_SUB_29 = Expect<
SubBinaryCarry<"100000000000000000000000000000000000000000000000", "1">,
"11111111111111111111111111111111111111111111111"
>
type TEST_SUB_30 = Expect<SubBinaryCarry<"0001", "0000">, "1">
type TEST_SUB_31 = Expect<SubBinaryCarry<"0001", "1">, "0">
type TEST_SUB_32 = Expect<SubBinaryCarry<"", "1">, "0">
type TEST_SUB_33 = Expect<SubBinaryCarry<"1", "">, "1">
type TEST_SUB_34 = Expect<SubBinaryCarry<"", "">, "0">
type TEST_SUB_35 = Expect<SubBinaryCarry<"01", "10">, "0">
type _MultBin<
Bin1 extends string,
Bin2 extends string,
// internal
Count extends string = "1",
Orig extends string = Bin1,
> = Trim<Bin2> extends Count
? Bin1
: _MultBin<AddBinaryCarry<Bin1, Orig>, Bin2, AddBinaryCarry<Count, "1">, Orig>
type MultBin<Bin1 extends string, Bin2 extends string> = "0" extends
| Trim<Bin1>
| Trim<Bin2>
? "0"
: _MultBin<Bin1, Bin2>
type TEST_MULT_00 = Expect<MultBin<"001", "010">, "010">
type TEST_MULT_01 = Expect<MultBin<"001", "001">, "001">
type TEST_MULT_02 = Expect<MultBin<"001", "011">, "011">
type TEST_MULT_03 = Expect<MultBin<"011", "011">, "1001">
type TEST_MULT_04 = Expect<MultBin<"100", "100">, "10000">
type TEST_MULT_05 = Expect<MultBin<"111", "111">, "110001">
type TEST_MULT_06 = Expect<MultBin<"011", "010">, "110">
type TEST_MULT_07 = Expect<MultBin<"010", "011">, "110">
type TEST_MULT_20 = Expect<MultBin<"1", "0000">, "0">
type TEST_MULT_21 = Expect<MultBin<"0000", "1">, "0">
type TEST_MULT_22 = Expect<MultBin<"", "1">, "0">
type TEST_MULT_23 = Expect<MultBin<"1", "">, "0">
type TEST_MULT_24 = Expect<MultBin<"", "">, "0">
type _DivBin<
Bin1 extends string,
Bin2 extends string,
// internal
Count extends string = "0",
> = LTBin<Trim<Bin1>, Trim<Bin2>> extends One
? [Count, Trim<Bin1>]
: _DivBin<SubBinaryCarry<Bin1, Bin2>, Bin2, AddBinaryCarry<Count, "1">>
// steps here speed it up
/** @returns tuple of [result, remainder] */
type DivBin<Bin1 extends string, Bin2 extends string> = Zero extends Trim<Bin2>
? ["Infinity", Zero]
: One extends Trim<Bin2>
? [Trim<Bin1>, Zero]
: Trim<Bin1> extends Trim<Bin2>
? [One, Zero]
: _DivBin<Bin1, Bin2>
/** types to allow indexing */
type Div10Bin<
Bin1 extends string,
/** internal */
Count extends string = "0",
> = Trim<Bin1> extends keyof decimalMap
? [Count, Trim<Bin1>]
: Div10Bin<SubBinaryCarry<Bin1, "1010">, AddBinaryCarry<Count, "1">>
// division tests
type TEST_DIV_00 = Expect<DivBin<"010", "010">, ["1", "0"]> // 2 ÷ 2 = 1
type TEST_DIV_01 = Expect<DivBin<"001", "001">, ["1", "0"]> // 1 ÷ 1 = 1
type TEST_DIV_02 = Expect<DivBin<"011", "011">, ["1", "0"]> // 3 ÷ 3 = 1
type TEST_DIV_03 = Expect<DivBin<"1001", "011">, ["11", "0"]> // 9 ÷ 3 = 3
type TEST_DIV_04 = Expect<DivBin<"10000", "100">, ["100", "0"]> // 16 ÷ 4 = 4
type TEST_DIV_05 = Expect<DivBin<"110001", "111">, ["111", "0"]> // 49 ÷ 7 = 7
type TEST_DIV_06 = Expect<DivBin<"110", "010">, ["11", "0"]> // 6 ÷ 2 = 3
type TEST_DIV_07 = Expect<DivBin<"110", "011">, ["10", "0"]> // 6 ÷ 3 = 2
type TEST_DIV_20 = Expect<DivBin<"0", "0000">, ["Infinity", "0"]> // 0 ÷ 0 = Infinity
type TEST_DIV_21 = Expect<DivBin<"0", "1">, ["0", "0"]> // 0 ÷ 1 = 0
type TEST_DIV_22 = Expect<DivBin<"", "1">, ["0", "0"]> // 0 ÷ 1 = 0
type TEST_DIV_23 = Expect<DivBin<"1", "">, ["Infinity", "0"]> // 1 ÷ 0 = Infinity
type TEST_DIV_24 = Expect<DivBin<"", "">, ["Infinity", "0"]> // 0 ÷ 0 = Infinity
// remainders
type TEST_DIV_30 = Expect<DivBin<"01", "10">, ["0", "1"]> // 1 ÷ 2 = 0, remainder 1
type TEST_DIV_31 = Expect<DivBin<"101", "10">, ["10", "1"]> // 5 ÷ 2 = 2, remainder 1
type TEST_DIV_32 = Expect<DivBin<"101", "1000000">, ["0", "101"]> // 5 ÷ 64 = 0, remainder 5
// size
type TEST_DIV_41 = Expect<Div10Bin<"010011100001111">, ["1111100111", "1001"]> // 9999 ÷ 10 = 999, remainder 9
type Equal<A, B> = [A] extends [B] ? ([B] extends [A] ? true : false) : false
type MinBin<
Bin1 extends string,
Bin2 extends string,
Orig1 extends string = Bin1,
Orig2 extends string = Bin2,
> = Equal<Trim<Bin1>, Trim<Bin2>> extends true
? Bin1
: Bin1 extends `${infer B1}${infer Rest1}`
? Bin2 extends `${infer B2}${infer Rest2}`
? Equal<B1, B2> extends true
? MinBin<Rest1, Rest2, Orig1, Orig2>
: B1 extends "0"
? Orig1
: B2 extends "0"
? Orig2
: never
: never
: never
type TEST_MIN_00 = Expect<MinBin<"001", "010">, "001">
type TEST_MIN_01 = Expect<MinBin<"001", "001">, "001">
type TEST_MIN_02 = Expect<MinBin<"001", "011">, "001">
type TEST_MIN_03 = Expect<MinBin<"011", "011">, "011">
type TEST_MIN_06 = Expect<MinBin<"011", "010">, "010">
type TEST_MIN_07 = Expect<MinBin<"010", "011">, "010">
type TEST_MIN_20 = Expect<MinBin<"1", "0000">, "0000">
type TEST_MIN_21 = Expect<MinBin<"0000", "1">, "0000">
// @ts-expect-error - empty string not implemented
type TEST_MIN_22 = Expect<MinBin<"", "1">, "0">
// @ts-expect-error - empty string not implemented
type TEST_MIN_23 = Expect<MinBin<"1", "">, "0">
// @ts-expect-error - empty string not implemented
type TEST_MIN_24 = Expect<MinBin<"", "">, "0">
type MaxBin<
Bin1 extends string,
Bin2 extends string,
Orig1 extends string = Bin1,
Orig2 extends string = Bin2,
> = Equal<Trim<Bin1>, Trim<Bin2>> extends true
? Bin1
: Bin1 extends `${infer B1}${infer Rest1}`
? Bin2 extends `${infer B2}${infer Rest2}`
? Equal<B1, B2> extends true
? MaxBin<Rest1, Rest2, Orig1, Orig2>
: B1 extends "1"
? Orig1
: B2 extends "1"
? Orig2
: never
: never
: never
type TEST_MAX_00 = Expect<MaxBin<"001", "010">, "010">
type TEST_MAX_01 = Expect<MaxBin<"001", "001">, "001">
type TEST_MAX_02 = Expect<MaxBin<"001", "011">, "011">
type TEST_MAX_03 = Expect<MaxBin<"011", "011">, "011">
type TEST_MAX_06 = Expect<MaxBin<"011", "010">, "011">
type TEST_MAX_07 = Expect<MaxBin<"010", "011">, "011">
type TEST_MAX_20 = Expect<MaxBin<"1", "0000">, "1">
type TEST_MAX_21 = Expect<MaxBin<"0000", "1">, "1">
// @ts-expect-error - empty string not implemented
type TEST_MAX_22 = Expect<MaxBin<"", "1">, "1">
// @ts-expect-error - empty string not implemented
type TEST_MAX_23 = Expect<MaxBin<"1", "">, "1">
// @ts-expect-error - empty string not implemented
type TEST_MAX_24 = Expect<MaxBin<"", "">, "??">
type GTBin<
Bin0 extends string,
Bin1 extends string,
Bins extends [string, string] = NormalizeLengthBin<Bin0, Bin1>,
> = Bins[0] extends `${infer B1}${infer Rest1}`
? Bins[1] extends `${infer B2}${infer Rest2}`
? Equal<B1, B2> extends true
? GTBin<Rest1, Rest2, [Rest1, Rest2]>
: B1 extends "1"
? One
: Zero
: never
: Zero
type TEST_GT_00 = Expect<GTBin<"001", "010">, "0">
type TEST_GT_01 = Expect<GTBin<"001", "001">, "0">
type TEST_GT_06 = Expect<GTBin<"011", "010">, "1">
type TEST_GT_07 = Expect<GTBin<"010", "011">, "0">
type TEST_GT_20 = Expect<GTBin<"1", "0000">, "1">
type TEST_GT_21 = Expect<GTBin<"0000", "1">, "0">
type TEST_GT_22 = Expect<GTBin<"", "1">, "0">
type TEST_GT_23 = Expect<GTBin<"1", "">, "1">
type TEST_GT_24 = Expect<GTBin<"", "">, "0">
type GTEBin<
Bin0 extends string,
Bin1 extends string,
Bins extends [string, string] = NormalizeLengthBin<Bin0, Bin1>,
> = Bins[0] extends `${infer B1}${infer Rest1}`
? Bins[1] extends `${infer B2}${infer Rest2}`
? Equal<B1, B2> extends true
? GTEBin<Rest1, Rest2, [Rest1, Rest2]>
: B1 extends "1"
? One
: Zero
: never
: One
type TEST_GTE_01 = Expect<GTEBin<"001", "001">, "1">
type TEST_GTE_06 = Expect<GTEBin<"011", "010">, "1">
type TEST_GTE_07 = Expect<GTEBin<"010", "011">, "0">
type TEST_GTE_20 = Expect<GTEBin<"1", "0000">, "1">
type TEST_GTE_21 = Expect<GTEBin<"0000", "1">, "0">
type TEST_GTE_22 = Expect<GTEBin<"", "1">, "0">
type TEST_GTE_23 = Expect<GTEBin<"1", "">, "1">
type TEST_GTE_24 = Expect<GTEBin<"", "">, "1">
type TEST_GTE_25 = Expect<GTEBin<"111111", "111111">, "1">
type TEST_GTE_26 = Expect<GTEBin<"00010000001", "001">, "1">
type LTBin<
Bin0 extends string,
Bin1 extends string,
Bins extends [string, string] = NormalizeLengthBin<Bin0, Bin1>,
> = Bins[0] extends `${infer B1}${infer Rest1}`
? Bins[1] extends `${infer B2}${infer Rest2}`
? Equal<B1, B2> extends true
? LTBin<Rest1, Rest2, [Rest1, Rest2]>
: B1 extends "0"
? One
: Zero
: never
: Zero
type TEST_LT_00 = Expect<LTBin<"001", "010">, "1">
type TEST_LT_01 = Expect<LTBin<"001", "001">, "0">
type TEST_LT_06 = Expect<LTBin<"011", "010">, "0">
type TEST_LT_07 = Expect<LTBin<"010", "011">, "1">
type TEST_LT_20 = Expect<LTBin<"1", "0000">, "0">
type TEST_LT_21 = Expect<LTBin<"0000", "1">, "1">
type TEST_LT_22 = Expect<LTBin<"", "1">, "1">
type TEST_LT_23 = Expect<LTBin<"1", "">, "0">
type TEST_LT_24 = Expect<LTBin<"", "">, "0">
type TEST_LT_25 = Expect<LTBin<"11000", "11">, "0">
type TEST_LT_26 = Expect<LTBin<"101010", "111">, "0">
type TEST_LT_27 = Expect<LTBin<"100000001010", "111">, "0">
type EQBin<Bin1 extends string, Bin2 extends string> = Equal<
Trim<Bin1>,
Trim<Bin2>
> extends true
? One
: Zero
type TEST_EQ_00 = Expect<EQBin<"001", "010">, "0">
type TEST_EQ_01 = Expect<EQBin<"001", "001">, "1">
type TEST_EQ_06 = Expect<EQBin<"011", "010">, "0">
type TEST_EQ_07 = Expect<EQBin<"010", "011">, "0">
type TEST_EQ_08 = Expect<EQBin<"00001", "1">, "1">
type TEST_EQ_20 = Expect<EQBin<"1", "0000">, "0">
type TEST_EQ_21 = Expect<EQBin<"0000", "1">, "0">
type TEST_EQ_22 = Expect<EQBin<"", "1">, "0">
type TEST_EQ_23 = Expect<EQBin<"1", "">, "0">
type TEST_EQ_24 = Expect<EQBin<"", "">, "1">
// #endregion
// #region - converters
type binaryMap = {
"0": "0000"
"1": "0001"
"2": "0010"
"3": "0011"
"4": "0100"
"5": "0101"
"6": "0110"
"7": "0111"
"8": "1000"
"9": "1001"
A: "1010"
B: "1011"
C: "1100"
D: "1101"
E: "1110"
F: "1111"
}
/**
* process 2 chars at the same time, half as much recursion
*
* max length: 1999 hex chars
* @version 3
*/
type hexToBin<
S extends string,
Out extends string = "",
> = S extends `${infer S0}${infer S1}${infer Rest}`
? S0 extends keyof binaryMap
? S1 extends keyof binaryMap
? hexToBin<Rest, `${Out}${binaryMap[S0]}${binaryMap[S1]}`>
: never
: never
: S extends keyof binaryMap // only 0 or 1 chars left in input string
? `${Out}${binaryMap[S]}`
: Out
type TEST_HEX_BIN_00 = Expect<hexToBin<"D">, "1101">
type TEST_HEX_BIN_01 = Expect<hexToBin<"D2FE28">, "110100101111111000101000">
type TEST_HEX_BIN_02 = Expect<hexToBin<"NOT_HEX">, never>
// https://itnext.io/implementing-arithmetic-within-typescripts-type-system-a1ef140a6f6f
// https://github.com/fightingcat/sits
// https://github.com/kddnewton/typescript-parse-math
// https://github.com/ronami/meta-typing
// https://github.com/ghoullier/awesome-template-literal-types#bitwise-arithmetic
// https://www.typescriptlang.org/play?ts=4.5.0-dev.20210908#code/C4TwDgpgBAsgggDQJIwKowPpwDLYPIDqAogCIYBCeqAciXAEoCaUAvFACwCcArALABQA0JFgBDMJAAmAHgFR5UalAgAPYBAB2kgM5QNAVwC2AIwgAnADRyF9CNv0AbYMrWadUOGbOiQ0-RoBrDQB7AHcNAD5WKABtAF0rfgUoKJZreQAKW3snGIByB00Ac2AACzy4l3UtXWp05KgAfihsx2B65IAuMQkIGWoLWIA6EdanQbHgfMKNEvK4uIj6gEoBAQB6dagABihBgEZBgCYoEaGOTnYhcGhqI1MzelFZ6DYYcSlpeGQ0TBx8YhkSg0OhMCIxAwmcxxNaCfjCaAAFVUwG00kRVTcugACmZgpAzKAANIQECpKAYlFYvT3cxNKAAA3UagAJABvREAXwZUG6GggADdzLDriIMWwDA4HFAAD5QABEon0wGC8tlFJRaLuUMezyKEAiAG5YQioCQAJYAY2A5uCGlEZhA0TZ9RiuPxUHNGkUtN1Lygol0DPZ7rA3Li3VDAk5sM28l2cv26pOcoAzOr2OruOqAGzqgDs6oAHOrOOr9rszhcrvCbopWPUiGpvNb0YMmSj2ZCHtyolSaozmcB2V6AGZ0+jc+rNeiYgcBUnBUdmq02u0OkDTlfW232x0xegwpIKPmC4XH+SnoVmEX8IA
// https://www.typescriptlang.org/play?ts=4.5.0-dev.20211012#code/C4TwDgpgBAsgggDQJIwKowPpwDLYPIDqAogCIYBCeqAciXAEoCaUAvFAJycCwAUL6JFgBDMJAAmAHl5QZUalAgAPYBAB2YgM5RVAVwC2AIwgAnADTTZ9CBp0AbYAuVrNUOMeNCQEnaoDWqgHsAd1UAPlYoAG0AXXMeWShwlgsZAAorG3tIgHJbNQBzYAALbOjHFXUtahSEqAB+KAy7YBqEgC5hUQhJalMogDpBpvs+4eAcvNVCkujo0JqASl5lngFoan0jY3ohKeg2GBFxCXhkNEwcfGIySho6JlDI3UMTaJX+cGgAYQDVADcTMAACoBDYvYwSIHlZxaDTAYwASymo12+WgSgqLmeWySNXSqPRTkqUF2IFasgaqQABgASADeOz2AF8qdDiUDybV6o0CZzah1VBAAcYlvEuVABUKTKKPoIMBEfv9ASCwVsJNkAKzZPqqkyMtHhAD0hqgGtl0Aw8rYiuFwNBmxM6oAjAAmLU6h3bAlGk2us18HhAA
// https://www.typescriptlang.org/play?ts=4.5.0-dev.20211012&ssl=9&ssc=25&pln=9&pc=31#code/C4TwDgpgBAsgggDQJIwKowPpwDLYPIDqAogCIYBCeqAciXAEoCaUAvFAJycCwAUL6JFgBDMJAAmAHl5QZUalAgAPYBAB2YgM5RVAVwC2AIwgAnADTTZ9CBp0AbYAuVrNUOMeNCQEnaoDWqgHsAd1UAPlYoAG0AXXMeWShwlgsZAAorG3tIgHJbNQBzYAALbOjHFXUtahSEqAB+KAy7YBqEgC5hUQhJalMogDpBpvs+4eAcvNVCkujo0JqASl5lngFoan0jY3ohKeg2GBFxCXhkNEwcfGIySho6JlCAbhX+cGgAYQDVADcTYAAVAIbQwmCT-crOLQaYDGACWU1Gu3y0CUFRcuhBxhiSQs4NRkKgvggIACADNGkjoA0dntIv8yh1VBBfsZnnxVm8oBgIp8fn9AcCthJsgBWbJ9QUmGnI8IAellUBFr0EGG5bF5LIBQM2oOyAEYAExiiU67aUuUKw1K9lAA
type decimalMap = {
"0": "0"
"1": "1"
"10": "2"
"11": "3"
"100": "4"
"101": "5"
"110": "6"
"111": "7"
"1000": "8"
"1001": "9"
}
type _binToDecString<
Res extends [string, keyof decimalMap] = ["0", "0"],
// internal
Out extends string = "",
> = Res[0] extends "0"
? `${decimalMap[Res[1]]}${Out}`
: _binToDecString<Div10Bin<Res[0]>, `${decimalMap[Res[1]]}${Out}`>
// kick off the recursion
type binToDecString<Bin extends string> = _binToDecString<Div10Bin<Bin>>
type TEST_DEC_00 = Expect<binToDecString<"0111">, "7">
type TEST_DEC_001 = Expect<Div10Bin<"0111">, ["0", "111"]>
type TEST_DEC_01 = Expect<binToDecString<"0000">, "0">
type TEST_DEC_02 = Expect<binToDecString<"1010">, "10">
type TEST_DEC_03 = Expect<binToDecString<"1111">, "15">
type TEST_DEC_04 = Expect<binToDecString<"00101010">, "42">
type TEST_DEC_05 = Expect<binToDecString<"101010">, "42">
// 253 / 10 = 25 remainder 3
type TEST_DEC_051 = Expect<Div10Bin<"11111101">, ["11001", "11"]>
// 25 / 10 = 2 remainder 5
type TEST_DEC_052 = Expect<Div10Bin<"11001">, ["10", "101"]>
// 2 / 10 = 0 remainder 2
type TEST_DEC_053 = Expect<Div10Bin<"10">, ["0", "10"]>
type TEST_DEC_06 = Expect<binToDecString<"11111101">, "253">
/** NOTE: max recursion depth of 9999 */
type TEST_DEC_07 = Expect<binToDecString<"010011100001111">, "9999">
// #region - helpers
type Zero = "0"
type One = "1"
type Bit = Zero | One
type Bitify<Bit extends string> = Bit extends "" ? Zero : Bit
/** remove leading zeros */
type Trim<Bin> = Bin extends ""
? "0"
: Bin extends `${infer B0}${infer Rest}`
? B0 extends "0"
? Trim<Rest>
: Bin
: Bin
type TEST_TRIM_00 = Expect<Trim<"010011100001111">, "10011100001111">
type TEST_TRIM_01 = Expect<Trim<"010011100010000">, "10011100010000">
/** take 2 binary strings and make sure they're the same length by padding the starts with 0 */
type NormalizeLengthBin<
Bin1 extends string,
Bin2 extends string,
Out1 extends string = Bin1,
Out2 extends string = Bin2,
> = Bin1 | Bin2 extends ""
? [Out1, Out2]
: Bin1 extends `${infer Rest1}${Bit}`
? Bin2 extends `${infer Rest2}${Bit}`
? NormalizeLengthBin<Rest1, Rest2, Out1, Out2>
: NormalizeLengthBin<Rest1, Bin2, Out1, `0${Out2}`>
: Bin2 extends `${infer Rest2}${Bit}`
? NormalizeLengthBin<Bin1, Rest2, `0${Out1}`, Out2>
: never
type TEST_NORM_00 = Expect<NormalizeLengthBin<"1", "1">, ["1", "1"]>
type TEST_NORM_01 = Expect<NormalizeLengthBin<"00001", "001">, ["00001", "00001"]>
type TEST_NORM_02 = Expect<NormalizeLengthBin<"001", "00001">, ["00001", "00001"]>
type TEST_NORM_03 = Expect<NormalizeLengthBin<"00100", "000010">, ["000100", "000010"]>
type TEST_NORM_04 = Expect<NormalizeLengthBin<"", "">, ["", ""]>
type TEST_NORM_05 = Expect<NormalizeLengthBin<"100", "1">, ["100", "001"]>
/**
* passes thru passing test input, errors with inputs that are not equal
*
* can be used in the middle of an expression and composed to check each step
*
* @todo check for perf issues with recursion
*/
type Expect<
Input extends Intersect,
Expected extends Intersect,
Intersect = Expected & Input,
> = Input
// @ts-expect-error
type expect_chain_test_0 = Expect<42, Expect<number, 42> | 0>
// @ts-expect-error
type expect_chain_test_1 = Expect<Expect<number, 42> | 0, 42>
type expect_chain_test_2 = Expect<Expect<42 | number, number> | 0, number>
type expect_chain_test_3 = Expect<number, Expect<number, 42 | number> | 0>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment