失業中在 github 閑逛，看到有人用類型實現的一個4位虛擬機，為什么是4位呢，因為 TypeScript 的類型實例化深度有限制，沒法實現太大的數字計算。說到用類型實現數字計算，一大堆邱奇數就冒出來了，但是因為這個限制，這種方法通常只能用于很小的數字，今天我們嘗試一種不同的思路，用二進制實現8位的數字計算。

為了實現計算我們要先把數字類型轉換成二進制，比如一個0和1的數組類型，但是進制轉換又需要數學計算，顯然我們是沒辦法實現的，那么怎么辦呢？ 很簡單，硬編碼一個映射就好了。但是對于8位數來說，255個長度為8的數組類型是一段很長的代碼，為了減少代碼長度，我們可以只編碼一個二進制 trie 結構，然后通過搜索路徑得到二進制編碼。

我們用數組來表示二進制 trie，以3位數（0-7）為例，就是這個樣子：

type binaryTrie = [[[0, 1], [2, 3]], [[4, 5], [6, 7]]];

數字的訪問路徑就是對應的二進制，比如binaryTrie[0][1][1]就是3，也就是二進制的 011。然后我們寫一個簡單的腳本來生成8位的 trie：

JSON.stringify((function it(n, acc) {return n > 0? [it(n - 1, acc), it(n - 1, acc + 2 ** n)]: [acc + 0, acc + 1];})(7, 0) );

看一下在編輯器里的樣子：

還好，不算太長，但如果是16位數字的話那出來的就是1M多字節了，所以我們只實現8位數的就好了。然后我們來定義一個用來查找 trie 的類型：

type SearchInTrie<Num, Node, Digits> = {1: Node extends [infer A, infer B]? Num extends A ? Push<Digits, 0>: Num extends B ? Push<Digits, 1>: never : never;0: Node extends [infer A, infer B]? SearchInTrie<Num, A, Push<Digits, 0>>| SearchInTrie<Num, B, Push<Digits, 1>>: never; }[Node extends [number, number] ? 1 : 0];

這是一個遞歸的類型，三個參數分別是 要查找的數字，當前查找節點，當前查找路徑。我們先判斷當前節點：如果是葉子節點（1）判斷是左右節點的哪一個，把相應的二進制值加入路徑并返回，都不是返回never。如果不是葉子節點（0），分別對左右節點進行查找，將結果 union 在一起，由于其中一邊肯定查找不到，結果會是never，所以 union 的結果將會是最終查找到的路徑。

這里用到了一個Push類型來將二進制位加入數組，它的完整定義如下：

type Copy<T, S extends any> = { [P in keyof T]: P extends keyof S ? S[P] : never };type Unshift<T, A> = ((a: A, ...b: T extends any[] ? T : never) => void ) extends (...a: infer R) => void ? R : never;type Push<T, A> =Copy<Unshift<T, any>, T & Record<string, A>>;

你們可能已經見過Unshift這種用法了，它就是用 conditional type 和函數類型的可變參數去推斷出一個在開頭插入了新元素的數組類型。目前只有這種辦法可以向元組類型中加入元素，而且只能在開頭加入。

那么這個Push是怎么實現在末尾加入元素的呢，這就涉及到另一個東西了，就是 mapped type，這個東西有個沒有在文檔中說明的特性，當用于元組類型時，具體來說，in關鍵字后面是一個元組類型的 key 時，mapped type的結果也是一個相同長度的元組類型。TS 的隱式規則越來越多了，很多特性都是糊出來的。

所以我們先定義一個Copy類型將T上的屬性值覆蓋為S的，然后在Push中，我們先往數組開頭隨意插入一個元素，然后從原來的數組T復制屬性過來，但是因為多了一個元素，最后一個元素在T上是沒有的，所以我們加一個& Record<string, A>，無論這最后一個元素的 key 是多少，最后肯定會從這個Record上取到A，也就是我們要加入的元素。

回到主題上來，我們現在可以把數字轉成二進制了，同時這個 trie 也可以由二進制得到數字：

type Digit = 0 | 1; type Bits = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7; type Uint8 = Record<Bits, Digit>; // 也可以定義成8個Digit的數組，這樣寫比較簡短// 數字轉二進制表示 type ToUint8<A extends number> =SearchInTrie<A, BinaryTrie, []>;// 二進制表示轉數字 type ToNumber<A extends Uint8> =BinaryTrie[A[0]][A[1]][A[2]][A[3]][A[4]][A[5]][A[6]][A[7]];

那么我們就可以開始實現計算了，最簡單的也是最基礎的就是加法了，我們要用類型實現一個全加器。讓我們先來實現1位的加法器：

// 兩個1 bit數相加，C 表示進位 type BitAdd<A extends Digit, B extends Digit, C extends Digit> = [[[[0, 0], [1, 0]], [[1, 0], [0, 1]]],[[[1, 0], [0, 1]], [[0, 1], [1, 1]]] ][A][B][C];

非常簡單，A和B是相加的兩個1位數字，C是進位標志，返回的類型是兩個值的數組，第一個值是和，第二個值是進位標志。

然后把8個1位加法器級聯起來就組成了一個8位全加器：

type AsDigit<T> = T extends Digit ? T : never; type AsUint8<T> = T extends Uint8 ? T : never;type Uint8Add<A extends Uint8, B extends Uint8> =BitAdd< A[7], B[7], 0> extends [infer S7, infer C]? BitAdd<A[6], B[6], AsDigit<C>> extends [infer S6, infer C]? BitAdd<A[5], B[5], AsDigit<C>> extends [infer S5, infer C]? BitAdd<A[4], B[4], AsDigit<C>> extends [infer S4, infer C]? BitAdd<A[3], B[3], AsDigit<C>> extends [infer S3, infer C]? BitAdd<A[2], B[2], AsDigit<C>> extends [infer S2, infer C]? BitAdd<A[1], B[1], AsDigit<C>> extends [infer S1, infer C]? BitAdd<A[0], B[0], AsDigit<C>> extends [infer S0, infer C]// ? C extends 1 ? "overflow" :? AsUint8<[S0, S1, S2, S3, S4, S5, S6, S7]>: never : never : never : never : never : never : never : never;

這里我們用 infer 語法當作變量保存每一步的結果，這個語法直接把“函數式”變成了“過程式”（笑），不過 infer 出來的類型變量是沒有類型約束的，所以我們額外定義了兩個類型AsDigit和AsUint8來把結果 assert 成期望的類型，主要是為了滿足泛型參數的約束檢查。從中間的注釋可以看到，我們沒有對加法溢出進行處理，溢出會得到循環后的結果，這也是實現減法的原理。

我們來看一下，8 位二進制數能表示的最大數字，8 位全是 1，十進制是 255，如果我們對它加 1 會怎樣？因為每位都是 1，所以會不斷的進位最終得到全 0。如果加 2 呢，其實就相當于加 1 再加 1，第一次加 1 得到 0，第二次加 1 就得到 1。所以我們可以簡單的認識到，有限位的二進制數字是循環的，因為最高位溢出后就回歸到 0 了。再舉一個例子，如果 255 加 256 呢？由于 256 是超出 8 位數范圍的，我們拆開成加 1 + 255。加 1 得到 0，再加 255 又得到 255。因為 0-255 共 256 個數，所以任何數加 256 相當于循環一圈，得到的還是原來的數。

我們再來看對一個數字減 1 會如何。以0 - 1為例，根據前面的推論我們知道，任何 8 位數字加 256 結果不變，我們把0 - 1表示為0 + 256 - 1，就變成了計算0 + (256 - 1)，再進一步地，由于 256 超出了 8 位數范圍，我們改寫為0 + (255 - 1 + 1)，我們知道 255 的二進制 8 位全是 1，它減任何一個 8 位數，我們逐位相減可以發現，如果被減數字的某一位為 0，那么結果為1 - 0 = 1，如果為 1 結果為1 - 1 = 0，所以我們可以簡單地把被減數每一位取反，得到的就是 255 減去它的結果。所以0 + (255 - 1 + 1)就變成了0 + (對1按位取反 + 1)，所以0 - 1就等于“對 1 按位取反再加 1”（這個1是我們從256里拿出來的，不是減數1，不要搞混了），結果是 8 位全 1 也就是 255。和加法溢出類似，減法也產生了溢出循環的效果。這其實就是-1 的二進制表示，“按位取反再加 1”就是所謂的“補碼”。在有符號的數字系統里，數字表示范圍的后一半就是用來表示負數（這就是為什么有符號數上溢會產生負數，但實際上-1 + 1 = 0 才是二進制溢出的結果），對于計算機來說正數負數都是一樣的，都是在一個環上，是我們通過指令的語義或語言的類型賦予了數字正負的含義。

再回到我們的主題，要實現A - B的計算，其實就是實現A + (-B)，而負數我們上面已經說了就是補碼，只不過我們的數字系統里沒有負數，但是對于二進制來說都是一樣的。

我們先來實現取反：

type Reverse = [1, 0];type Uint8Reverse<A extends Uint8> = [Reverse[A[0]],Reverse[A[1]],Reverse[A[2]],Reverse[A[3]],Reverse[A[4]],Reverse[A[5]],Reverse[A[6]],Reverse[A[7]] ];

然后實現補碼，先取反再加 1：

type ONE = [0, 0, 0, 0, 0, 0, 0, 1];type Uint8Negate<A extends Uint8> =Uint8Add<Uint8Reverse<A>, ONE>;

減法就是加上被減數的補碼：

type Uint8Sub<A extends Uint8, B extends Uint8> = Uint8Add<A, Uint8Negate<B>>;

回顧一下，我們通過 1 位數的加法實現了 8 位數的加法，又通過加法實現減法。接下來我們又會用加法和減法實現除法，不過讓我們先來看一下如何實現乘法。根據小學的數學知識，只要把被乘數和乘數的每一位相乘再相加就可以了，這里面其實還會有進位，還有與被乘數每一位相乘的操作其實還乘了位權，比如乘以 21，這個 2 其實是 20，要補上與位權相應的 0。

示例：

二進制和十進制的算法是一樣的，只是更簡單，因為被乘數字只會有 0 或 1 兩種，為 0 時結果也是 0，為 1 時數字不變，就只要補 0 就可以了，也就是左移操作。

示例：

我們先來實現左移，為了方便使用，我們用一個額外的參數指定左移時填補的數字：

type LShift<A extends Uint8, B extends number, P extends Digit> =B extends 1 ? [A[1], A[2], A[3], A[4], A[5], A[6], A[7], P]: B extends 2 ? [A[2], A[3], A[4], A[5], A[6], A[7], P, P]: B extends 3 ? [A[3], A[4], A[5], A[6], A[7], P, P, P]: B extends 4 ? [A[4], A[5], A[6], A[7], P, P, P, P]: B extends 5 ? [A[5], A[6], A[7], P, P, P, P, P]: B extends 6 ? [A[6], A[7], P, P, P, P, P, P]: B extends 7 ? [A[7], P, P, P, P, P, P, P]: B extends 0 ? A : [P, P, P, P, P, P, P, P];

然后實現逐位的乘法，額外提供一個參數指示位移長度，這里左移填充0，但是后面我們還會用到第三個參數：

type ZERO = [0, 0, 0, 0, 0, 0, 0, 0];type BitMul<A extends Uint8, B extends Digit, C extends Bits> =B extends 1 ? LShift<A, C, 0> : ZERO;

最后實現完整的乘法，對每一位運算的結果進行累加就是乘積了：

type Uint8Mul<A extends Uint8, B extends Uint8> = Uint8Add<ZERO, BitMul<A, B[7], 0>> extends infer S? Uint8Add<AsUint8<S>, BitMul<A, B[6], 1>> extends infer S? Uint8Add<AsUint8<S>, BitMul<A, B[5], 2>> extends infer S? Uint8Add<AsUint8<S>, BitMul<A, B[4], 3>> extends infer S? Uint8Add<AsUint8<S>, BitMul<A, B[3], 4>> extends infer S? Uint8Add<AsUint8<S>, BitMul<A, B[2], 5>> extends infer S? Uint8Add<AsUint8<S>, BitMul<A, B[1], 6>> extends infer S? Uint8Add<AsUint8<S>, BitMul<A, B[0], 7>>: never : never : never : never : never : never : never;

除法的算法也不過是小學知識，就是從被除數的最高位開始與除數比較，大于就相除并記錄商和余數，不斷地將被除數的下一位補到余數的末位來，直到除完所有數位。先來看 10 進制的：

二進制的更簡單了，因為每次求余的結果，商要么為 0 要么為 1，也就是說不會超過 2 倍，只要比較大小相減即可：

先來實現一個比較器，從高位到低位比較，不相等就返回比較結果，相等就繼續比較下一位：

type EQ = 0; type GT = 1; type LT = 2;type BitCMP<A extends Digit, B extends Digit> =[[EQ, LT], [GT, EQ]][A][B];type Uint8CMP<A extends Uint8, B extends Uint8> =BitCMP<A[0], B[0]> extends GT | LT ? BitCMP<A[0], B[0]>: BitCMP<A[1], B[1]> extends GT | LT ? BitCMP<A[1], B[1]>: BitCMP<A[2], B[2]> extends GT | LT ? BitCMP<A[2], B[2]>: BitCMP<A[3], B[3]> extends GT | LT ? BitCMP<A[3], B[3]>: BitCMP<A[4], B[4]> extends GT | LT ? BitCMP<A[4], B[4]>: BitCMP<A[5], B[5]> extends GT | LT ? BitCMP<A[5], B[5]>: BitCMP<A[6], B[6]> extends GT | LT ? BitCMP<A[6], B[6]>: BitCMP<A[7], B[7]>;

再實現用于迭代的簡單求余器，返回商和余數兩個值，被除數小于除數則商為 0 余數為被除數，否則商為 1 余數為兩數之差，這里用到了我們前面實現的減法：

type Remainder<A extends Uint8, B extends Uint8> =Uint8CMP<A, B> extends LT ? [0, A] : [1, Uint8Sub<A, B>];

最后，讓我們來實現完整的除法運算：

type Uint8Div<A extends Uint8, B extends Uint8> =Remainder<LShift<ZERO, 1, A[0]>, B> extends [infer Q0, infer R]? Remainder<LShift<AsUint8<R>, 1, A[1]>, B> extends [infer Q1, infer R]? Remainder<LShift<AsUint8<R>, 1, A[2]>, B> extends [infer Q2, infer R]? Remainder<LShift<AsUint8<R>, 1, A[3]>, B> extends [infer Q3, infer R]? Remainder<LShift<AsUint8<R>, 1, A[4]>, B> extends [infer Q4, infer R]? Remainder<LShift<AsUint8<R>, 1, A[5]>, B> extends [infer Q5, infer R]? Remainder<LShift<AsUint8<R>, 1, A[6]>, B> extends [infer Q6, infer R]? Remainder<LShift<AsUint8<R>, 1, A[7]>, B> extends [infer Q7, infer R]? [AsUint8<[Q0, Q1, Q2, Q3, Q4, Q5, Q6, Q7]>, AsUint8<R>]: never : never : never : never : never : never : never : never;

我們把被除數從高位到低位逐位后綴到每一步的余數后面，這里用到了我們左移操作的第三個參數。然后不斷對新的數求余，并保存每一位得到的商，然后返回最終的商和最終的余數。

最后，我們來定義幾個便于使用的類型：

// 加 type Add<A extends number, B extends number> =ToNumber<Uint8Add<ToUint8<A>, ToUint8<B>>>; // 減 type Sub<A extends number, B extends number> =ToNumber<Uint8Sub<ToUint8<A>, ToUint8<B>>>; // 乘 type Mul<A extends number, B extends number> =ToNumber<Uint8Mul<ToUint8<A>, ToUint8<B>>>; // 除 type Div<A extends number, B extends number> =B extends 0 ? never :ToNumber<Uint8Div<ToUint8<A>, ToUint8<B>>[0]>; // 取余 type Mod<A extends number, B extends number> =B extends 0 ? never :ToNumber<Uint8Div<ToUint8<A>, ToUint8<B>>[1]>;

然后我們簡單的測試一下：

type case1_ShouldBe99 = Add<33, 66>; // 33 + 66 = 99 type case2_ShouldBe0 = Add<255, 1>; // 255 + 1 = 0 (overflow)type case3_ShouldBe99 = Sub<123, 24>; // 123 - 24 = 99 type case4_ShouldBe255 = Sub<0, 1>; // 0 - 1 = 255 (overflow)type case5_ShouldBe153 = Mul<17, 9>; // 17 x 9 = 153 type case6_ShouldBe253 = Mul<255, 3>; // 255 x 3 = 253 (overflow)type case7_ShouldBe33 = Div<100, 3>; // 100 / 3 = 33 type case8_ShouldBeNever = Div<1, 0>; // 1 / 0 = error (divide by 0)type case9_ShouldBe1 = Mod<100, 3>; // 100 % 3 = 1 type case10_ShouldBeNever = Mod<1, 0>; // 1 % 0 = error (divide by 0)

最后放上 Playground 可以在線試一下（更新到了TS 4.0，和文章略有出入）。下一篇我再說一下如何用類型實現一個 parser 來從一個 token 數組中解析表達式和語法，會用到更多奇技淫巧，如果有人想看的話。

總結

以上是生活随笔為你收集整理的typescript 怎么表示当前时间减一个月_TypeScript类型元编程：实现8位数的算术运算...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。