TypesriptでもBitwiseなテンプレートリテラル型で簡単ビット演算チェック

趣味の範囲で組込み開発も行う著者としては、ビット演算の値が色々と気になります。
そもそもビット演算で扱うのは、二進数の整数型であり、ほぼ全てのプログラミング言語の中のプリミティブな数値型で、それ以上でもそれ以外でもないものです。
しかし、Typescriptはその柔軟な型表現により、ビット演算で表現できる全ての型を文字列リテラル型として扱うことができます。
以下が本家の実装です。

参考｜ cleoold/bitstring.ts

ものは試しで、今回はBitwiseなテンプレートリテラル型の使い方を解説していきます。

Javascript(js)＆Typescript(ts)プログラミング入門〜これから学ぶ人のためのおすすめ書籍＆教材の手引き

ビット演算を型で表現するテクニック集

本家ではBitwiseなテンプレートリテラル型の実装がまとめてありますが、この記事では読みやすくするため、以下小出しに解説を加えていきます。
ベースとなる

Digit

型は共通です。

開く/閉じる

            type Digit = '0' | '1';

NOT演算

まずはNOT演算を表現する型を以下のように定義しています。

開く/閉じる

            type Not<Num> = Num extends '' ?
    '' : Num extends '0' ?
        '1' : Num extends '1' ?
            '0' : Num extends `${infer Num_0}${infer Num_s}` ?
                Num_0 extends Digit ?
                    `${Not<Num_0>}${Not<Num_s>}` : never
                : never;

const a = '010101';

const x: Not<typeof a> = '101010';

//✘ Type '"101000"' is not assignable to type '"101010"'.
const y: Not<typeof a> = '101000';

この

Not

型の実装は、前回取り上げた

Conditional Types

で再帰処理させる応用になっています。
ビット数の先頭から桁から一つづつビット反転させて、末尾(

''型

)まで来たら処理が終了するというのを、conditional typesとinferで上手く表現しています。

AND演算

次に2つのビット数のAND演算を表現した

And

型は以下のようになります。

開く/閉じる

            type And<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 [Digit, Digit] ?
                            `${And<Num1_0, Num2_0>}${And<Num1_s, Num2_s>}`
                            : never
                        : never;

//演算させる2つのビット数の桁数はあらかじめ揃えておく
const a = '010101';
const b = '000101';

const x: And<typeof a, typeof b> = '000101';

//✘ Type '"101000"' is not assignable to type '"000101"'.
const y: And<typeof a, typeof b> = '101000';

こちらもconditional typesとinferを巧みに使って、ビット数の先頭から末尾までの各桁のビットを論理和を計算して返す、という操作を表現しています。

OR演算とXOR演算

2つのビット数のOR/XORの演算子もANDとほぼ同じ考え方で

Or

型と

Xor

型を表現できます。

開く/閉じる

            type Or<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 [Digit, Digit] ?
                        `${Or<Num1_0, Num2_0>}${Or<Num1_s, Num2_s>}`
                        : never
                    : never;

//※Not型/And型の実装は省略
type Xor<Num1, Num2> = Or<And<Num1, Not<Num2>>, And<Not<Num1>, Num2>>;

const a = '010101';
const b = '000101';

///OR演算
const x1: Or<typeof a, typeof b> = '010101';
//✘ Type '"101000"' is not assignable to type '"010101"'.
const y1: Or<typeof a, typeof b> = '001100';

///XOR演算
const x2: Xor<typeof a, typeof b> = '010000';
//✘ Type Type '"001100"' is not assignable to type '"010101"'.
const y2: Xor<typeof a, typeof b> = '101110';

左シフト

ビット数の左シフトは、論理シフト、算術シフトとも同じ

LShift

型で表現できます。

開く/閉じる

            type LShift<Num> = Num extends '' ?
    '' : Num extends `${infer _}${infer Num_s}` ?
        `${Num_s}0` : never;

const a = '010101';

const x: LShift<typeof a> = '101010';
//✘ Type '"001100"' is not assignable to type '"101010"'.
const y: LShift<typeof a> = '011001';

左に1つずらして空いた桁を0で埋めるだけなので簡単です。

右シフト

右シフトは、論理シフト・

RShiftLogical

型、算術シフト・

RShiftArith

で少し実装が異なります。

開く/閉じる

            type Car<L> = L extends readonly [infer L0, ... infer _] ?
    L0 : L extends `${infer L0}${infer _}` ?
        L0 : never;

type RShiftHelper<Num> = Num extends '' | Digit ?
    '' : Num extends `${infer Num_0}${infer Num_s}` ?
        Num_0 extends Digit ?
            `${Num_0}${RShiftHelper<Num_s>}`
            : never
        : never;

//論理シフト(空いたスペースに0を入れる)
type RShiftLogical<Num> = Num extends '' ?
    '' : `0${RShiftHelper<Num>}`;

//算術シフト(空いたスペースを符号ビットで埋める)
type RShiftArith<Num> = Num extends '' ?
    '' : Car<Num> extends Digit ?
        `${Car<Num>}${RShiftHelper<Num>}` : never;

const a = '110101';

///右論理シフト

const x1: RShiftLogical<typeof a> = '011010';
//✘ Type '"110101"' is not assignable to type '"011010"'.
const y1: RShiftLogical<typeof a> = '110101';

///右算術シフト

const x2: RShiftArith<typeof a> = '111010';
//✘ Type '"011001"' is not assignable to type '"111010"'.
const y2: RShiftArith<typeof a> = '011011';

Car型

ここで出現している

Car

型の役割について少し補足しておきましょう。

開く/閉じる

            type Car<L> = L extends readonly [infer L0, ...infer _] ?
    L0 : L extends `${infer L0}${infer _}` ?
        L0 : never;

この型はビット値から符号ビット(一番左端のビット)を判別するためのものです。
少し分かりにくいかもしれないので、小出しに分解して理解してみましょう。
まず、最初に

Digit

型の要素からなるタプル型が、型変数に指定された際の型処理が走ります。

開く/閉じる

            type Car<L> = L extends readonly [infer L0, ...infer _] ?
    L0 : never;

const a = ['0', '1'] as const;

const x: Car<typeof a> = '0';
//Type '"1"' is not assignable to type '"0"'.
const y: Car<typeof a> = '1';

型変数にタプル型でない型の値が指定された場合には、

開く/閉じる

            type Car<L> = L extends `${infer L0}${infer _}` ? L0 : never;

const a = '01';

const x: Car<typeof a> = '0';
//Type '"1"' is not assignable to type '"0"'.
const y: Car<typeof a> = '1';

というように処理されます。
という2つの条件を一度に評価しているのが

Car

型です。

加算・減算

さて、ここでもっとも難解な型表現が、加算と減算の型です。
ここでの、

Digit/Not/Car

型は前の節での説明ものと同じです。

開く/閉じる

            type Reverse<S> = S extends '' ?
    '' : S extends `${infer S0}${infer Ss}` ?
        `${Reverse<Ss>}${S0}` : 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 SignedOverflowChecker<A, B, R> = [A, B, R] extends |
    (['0', '0', '1'] | ['1', '1', '0']) ?
        true : false;

type UnsignedOverflowChecker<Carry> = Carry extends '1' ? true : false;

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 Digit ?
                        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, B> = 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 Add<A, B> = Car<Adder<A, B>>;

type Sub<A, B> = Car<Adder<A, Car<Adder<Not<B>, '1'>>>>;

const a = '0110101';
const b = '0011011';

///和算: a + b
const x1: Add<typeof a, typeof b> = '1010000';
//✘ Type '"0010000"' is not assignable to type '"1010000"'.
const y1: Add<typeof a, typeof b> = '0010000';

///減算: a - b
const x2: Sub<typeof a, typeof b> = '0011010';
//✘ Type '"110101"' is not assignable to type '"0011010"'.
const y2: Sub<typeof a, typeof b> = '0100101';

加算型・

「Add」

と減算型・

「Sub」

の中身は複数の機能の型で構成されています。
これらの型が何を行っているか、一つずつ確認してみましょう。

Reverse型

まず

Reverse

型ですが、これはビット数の順序を先頭から末尾まで逆転させる操作を表現した型です。

開く/閉じる

            type Reverse<S> = S extends '' ?
    '' : S extends `${infer S0}${infer Ss}` ?
        `${Reverse<Ss>}${S0}` : never;

const a = '0110101';
const b = '0011011';

const x: Reverse<typeof a> = '1010110';
const y: Reverse<typeof b> = '1101100';

HalfAdder型

HarfAdder

型は、1ビット同士の和の結果を表現します。

開く/閉じる

            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;

const x1: HalfAdder<'0', '0'> = ['0', '0'];
const x2: HalfAdder<'1', '0'> = ['1', '0'];
const x3: HalfAdder<'0', '1'> = ['1', '0'];
const x4: HalfAdder<'1', '1'> = ['0', '1'];

型変数の

A

と

B

の足し算で、その結果を

[<足し算後の結果>, <繰り上げビット>]

というタプル型で返します。

OverflowChecker型

加算によって、元のビット数よりも最大桁数が繰り上げとなるかをチェックするのが、

OverflowChecker

型です。
これは符号なし演算用の

「UnsignedOverflowChecker」

と符号あり演算用の

「SignedOverflowChecker」

で分けて実装しているようです。

開く/閉じる

            type UnsignedOverflowChecker<Carry> = Carry extends '1' ? true : false;

const a1: UnsignedOverflowChecker<'1'> = true;
const b1: UnsignedOverflowChecker<'0'> = false;

type SignedOverflowChecker<A, B, R> = [A, B, R] extends |
    (['0', '0', '1'] | ['1', '1', '0']) ?
        true : false;

const a2: SignedOverflowChecker<'0', '0', '1'> = true;
const b2: SignedOverflowChecker<'1', '1', '0'> = true;
const c2: SignedOverflowChecker<'0', '1', '1'> = false;

AdderLittleEndian型

今回のテンプレートリテラルでもっとも難解な型が

「AdderLittleEndian」

型で、実際に2つのビット数を加算する手続きを表現しています。
ちなみに、ここではリトルエンディアンという名前が付いていますが、「小さい桁数から順番に大きい桁数に向かって計算していくよ」、という意味合い程度でしかなく、ビッグエンディアン版の計算方法やバイト数単位での格納などを指した言葉ではないことに留意してください。
また、conditional typesを使う上ではしか無いことかもしれませんが、三項条件演算子がいくつも連鎖していて、一見して何がどう分岐しているか分かりにくいです。
そのうち慣れてくると、あまり気にならなくなってくるものなので、とにかく自分の手でコードをコツコツ実装してみましょう。
一旦、

AdderLittleEndian

型を俯瞰でみてみます。

開く/閉じる

            type AdderLittleEndian<
    Num1, Num2, Carry = '0', Result extends string = ''
> = Num1 extends '' ?
        //👇Num1で計算対象のビットが無くなった場合
        Num2 extends '' ?
            //👇Num2も計算対象のビットが無くなったら[Result, Carry]を返して終了
            [Result, Carry] : // ... ☆①
        //👇Num1で計算対象のビットが存在する場合
        : Num2 extends '' ?
            //👇Num2の計算対象のビットが無くなったらNum1とNum2を交換して再び計算続行
            AdderLittleEndian<Num2, Num1, Carry, Result> : //...☆②

というふうに書くと、でおおよその操作が理解できると思います。
なお、型変数ですが、

Num1

と

Num2

はリトルエンディアン方式を念頭においているので、実際に計算したいビット数とは順序が逆になります。
型変数

Result

は加算の結果で得られたビット数を保持しています。
型変数

Carry

は加算の結果、桁が繰り上がった場合に

'1'

型を保持して次の計算に持ち込むためのオプショナルな型変数です。
さて、俯瞰で見た上のコードで、

「☆①」

と

「☆②」

の処理部分を残していました。
まず、Num1の全てのビットが計算し終わって、かつNum2ではまだ計算していないビットが残っている

「☆①」

ですが、

開く/閉じる

            //...前パートは省略
Num2 extends `${infer Num2_0}${infer Num2_s}` ?
    //👇1つ前の計算結果から、繰り上げがあれば足し算
    HalfAdder<Num2_0, Carry> extends [infer SumBit, infer NextCarry] ?
        SumBit extends string ?
            //👇足し算の結果があればNum1は空にして更に計算を行う
            AdderLittleEndian<'', Num2_s, NextCarry, `${Result}${SumBit}`>
            : never
    : never

ような処理になっています。
最後に、Num1にもNum2にも計算途中のビットが残っている場合の

「☆②」

については以下のような処理になります。

開く/閉じる

            //...前のパートは省略
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 Digit ?
                    //👇今回の計算結果を格納し次の計算へ進む
                    AdderLittleEndian<Num1_s, Num2_s, NextCarry, `${Result}${SumBit}`>
                    : never
                //👇一つ前の計算で繰り上がった場合
                : Carry extends '1' ?
                    SumBit extends '0' ?
                        //👇計算後のビットが0だった場合、結果を1にして次の計算に進む
                        AdderLittleEndian<Num1_s, Num2_s, NextCarry, `${Result}1`>
                        : SumBit extends '1' ?
                            //👇計算後のビットが1だった場合、結果を0、繰り上げを1にして次の計算に進む
                            AdderLittleEndian<Num1_s, Num2_s, '1', `${Result}0`>
                            : never
                    : never
            : never
        : never;

この処理がもっとも複雑で、現在のビットが同士の足し算を、前回の計算での繰り上げに考慮して計算を行います。

Adder型

この

Adder

型で、ビット数の入出力を"リトルエンディアン"形式に変換し、先程の

AdderLittleEndian

型から得られた加法演算の結果を見やすいように整えています。

開く/閉じる

            type Adder<A, B> = 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 Add<A, B> = Car<Adder<A, B>>;

type Sub<A, B> = Car<Adder<A, Car<Adder<Not<B>, '1'>>>>;

なお、

Adder

型の返す型から結果だけを抽出する際にも、

Car

型を使います。

Javascript(js)＆Typescript(ts)プログラミング入門〜これから学ぶ人のためのおすすめ書籍＆教材の手引き

まとめ

以上、Typescriptのテンプレートリテラル型とConditional typesとinferを巧妙に組み合わせたテクニックにより、Bitwiseなリテラル型のチェックが可能になったことが示せました。
これで電卓がなくても、型にはめ込むだけでビット演算可能ですので、使いようによってはかなり強力な助っ人になるのではないでしょうか。