👏

TypeScriptの型システム上に2進数計算機を作った話し

Riya Amemiya

2023/08/12に公開

TypeScript

2進数

tech

はじめに

この記事で紹介するコードは、個人開発のライブラリから抜粋したものです。

2進数の計算方法

２つの入力を受け取り、答えと繰り上がりを出力する型を作ります。

// 1bitの2進数のANDを求める型
export type binary1bitAND<
  X extends `${0 | 1}`,
  Y extends `${0 | 1}`,
> = binary1bitANDParser<X, Y>;

type binary1bitANDParser<X extends string, Y extends string> = X extends "1"
  ? Y extends "1"
    ? "1"
    : "0"
  : "0";

// 1bitの2進数のXORを求める型
export type binary1bitXOR<
  X extends `${0 | 1}`,
  Y extends `${0 | 1}`,
> = binary1bitXORParser<X, Y>;

type binary1bitXORParser<X extends string, Y extends string> = X extends "1"
  ? Y extends "1"
    ? "0"
    : "1"
  : Y extends "1"
  ? "1"
  : "0";

// 半加算器
export type binaryHalfAdder<
  X extends `${0 | 1}`,
  Y extends `${0 | 1}`,
> = binaryHalfAdderParser<X, Y>;

type binaryHalfAdderParser<
  X extends string,
  Y extends string,
  C extends string = "",
> = C extends ""
  ? binaryHalfAdderParser<X, Y, binary1bitANDParser<X, Y>>
  : `${C}${binary1bitXORParser<X, Y>}`;

これを半加算器と言います。
{繰り上げ}{答え} の形式で出力します。

type Test = binaryHalfAdder<"1", "1">; // "10"

1桁の計算しかできないので、半加算器を組み合わせて全加算器を作ります。
全加算器は、2個の半加算器と1個のORから構成から構成され、任意の桁数の2進数の加算ができます。

全加算器

// 1bitの2進数のORを求める型
export type binary1bitOR<
  X extends `${0 | 1}`,
  Y extends `${0 | 1}`,
> = binary1bitORParser<X, Y>;

type binary1bitORParser<X extends string, Y extends string> = X extends "1"
  ? "1"
  : Y extends "1"
  ? "1"
  : "0";

// 文字列の先頭からN文字を取得する型
export type FirstNChars<
  S extends string,
  N extends number,
  C extends unknown[] = [],
  A extends string = "",
> = C["length"] extends N
  ? A
  : S extends `${infer Head}${infer Rest}`
  ? FirstNChars<Rest, N, [...C, Head], `${A}${Head}`>
  : never;

// 文字列の先頭を削除する型
export type ShiftString<S extends string> = S extends `${string}${infer R}`
  ? R
  : never;

// 文字列を配列に変換する型
export type StringToArray<
  S extends string,
  T extends unknown[] = [],
> = S extends `${infer F}${infer R}` ? StringToArray<R, [...T, F]> : T;

// 文字を配列に変換して長さを取得する型
export type LengthOfString<S extends string,> = StringToArray<S>["length"];

// 文字列を反転する型
export type StringReverse<S extends string> = S extends `${infer F}${infer R}`
  ? `${StringReverse<R>}${F}`
  : "";

// 全加算器
export type binaryFullAdder<
  X extends string,
  Y extends string,
  B extends number = LengthOfString<X>,
> = LengthOfString<X> extends LengthOfString<Y>
  ? FirstNChars<
      ShiftString<
        StringReverse<
          binaryFullAdderParser<
            StringReverse<FirstNChars<X, B>>,
            StringReverse<FirstNChars<Y, B>>
          >
        >
      >,
      B
    >
  : never;

type binaryFullAdderParser<
  X extends string,
  Y extends string,
  A extends string = "",
  C extends string = "0",
> = X extends `${infer F}${infer R}`
  ? Y extends `${infer F2}${infer R2}`
    ? binaryHalfAdderParser<F, F2> extends `${infer F3}${infer R3}`
      ? binaryHalfAdderParser<R3, C> extends `${infer F4}${infer R4}`
        ? binaryFullAdderParser<R, R2, `${A}${R4}`, binary1bitORParser<F3, F4>>
        : never
      : never
    : never
  : `${A}${C}`;

TypeScriptの仕様の関係で、先頭から文字列を取り出して、計算します。
文字列を反転させて、計算した後に、再度反転させて、元の文字列に戻します。
今回は符号付きの2進数を扱うので、オーバーフローは切り捨てます。

type Test = binaryFullAdder<"00001000", "00001110">; // "00010110" 22
type Test2 = binaryFullAdder<"00001000", "00001111">; // "00010111" 23
type Test3 = binaryFullAdder<"11111111", "00001000">; // "00000111" 7

Code全文

// 1bitの2進数のANDを求める型
export type binary1bitAND<
  X extends `${0 | 1}`,
  Y extends `${0 | 1}`,
> = binary1bitANDParser<X, Y>;

type binary1bitANDParser<X extends string, Y extends string> = X extends "1"
  ? Y extends "1"
    ? "1"
    : "0"
  : "0";

// 1bitの2進数のXORを求める型
export type binary1bitXOR<
  X extends `${0 | 1}`,
  Y extends `${0 | 1}`,
> = binary1bitXORParser<X, Y>;

type binary1bitXORParser<X extends string, Y extends string> = X extends "1"
  ? Y extends "1"
    ? "0"
    : "1"
  : Y extends "1"
  ? "1"
  : "0";

// 半加算器
export type binaryHalfAdder<
  X extends `${0 | 1}`,
  Y extends `${0 | 1}`,
> = binaryHalfAdderParser<X, Y>;

type binaryHalfAdderParser<
  X extends string,
  Y extends string,
  C extends string = "",
> = C extends ""
  ? binaryHalfAdderParser<X, Y, binary1bitANDParser<X, Y>>
  : `${C}${binary1bitXORParser<X, Y>}`;

// 1bitの2進数のORを求める型
export type binary1bitOR<
  X extends `${0 | 1}`,
  Y extends `${0 | 1}`,
> = binary1bitORParser<X, Y>;

type binary1bitORParser<X extends string, Y extends string> = X extends "1"
  ? "1"
  : Y extends "1"
  ? "1"
  : "0";

// 文字列の先頭からN文字を取得する型
export type FirstNChars<
  S extends string,
  N extends number,
  C extends unknown[] = [],
  A extends string = "",
> = C["length"] extends N
  ? A
  : S extends `${infer Head}${infer Rest}`
  ? FirstNChars<Rest, N, [...C, Head], `${A}${Head}`>
  : never;

// 文字列の先頭を削除する型
export type ShiftString<S extends string> = S extends `${string}${infer R}`
  ? R
  : never;

// 文字列を配列に変換する型
export type StringToArray<
  S extends string,
  T extends unknown[] = [],
> = S extends `${infer F}${infer R}` ? StringToArray<R, [...T, F]> : T;

// 文字を配列に変換して長さを取得する型
export type LengthOfString<S extends string,> = StringToArray<S>["length"];

// 文字列を反転する型
export type StringReverse<S extends string> = S extends `${infer F}${infer R}`
  ? `${StringReverse<R>}${F}`
  : "";

// 全加算器
export type binaryFullAdder<
  X extends string,
  Y extends string,
  B extends number = LengthOfString<X>,
> = LengthOfString<X> extends LengthOfString<Y>
  ? FirstNChars<
      ShiftString<
        StringReverse<
          binaryFullAdderParser<
            StringReverse<FirstNChars<X, B>>,
            StringReverse<FirstNChars<Y, B>>
          >
        >
      >,
      B
    >
  : never;

type binaryFullAdderParser<
  X extends string,
  Y extends string,
  A extends string = "",
  C extends string = "0",
> = X extends `${infer F}${infer R}`
  ? Y extends `${infer F2}${infer R2}`
    ? binaryHalfAdderParser<F, F2> extends `${infer F3}${infer R3}`
      ? binaryHalfAdderParser<R3, C> extends `${infer F4}${infer R4}`
        ? binaryFullAdderParser<R, R2, `${A}${R4}`, binary1bitORParser<F3, F4>>
        : never
      : never
    : never
  : `${A}${C}`;

まとめ

TypeScriptの型システムを使って、2進数の計算機を作りました。
TypeScriptの型システムはチューリング完全なので、できることは無限にあります。
次回は、乗算、除算を実装したいと思います。

GitHubで編集を提案

GMOメディアテックブログPublication

GMOインターネットグループの一員であるGMOメディアは、BtoC向けの様々なインターネットサービスを提供し続けています。サービスをより良くしてユーザーに良い体験を提供すべく一緒に働くメンバーを募集しています。GitHub Copilot for Business や ChatGPT PlusなどAIサービス積極導入！

はじめに

2進数の計算方法

全加算器

まとめ

Discussion