カテゴリー
TypesriptでもBitwiseなテンプレートリテラル型で簡単ビット演算チェック
※ 当ページには【広告/PR】を含む場合があります。
2024/09/13
ビット演算を型で表現するテクニック集
Digit
type Digit = '0' | '1';
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''型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';
OR演算とXOR演算
OrXor
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';
右シフト
RShiftLogicalRShiftArith
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';
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
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'];
AB[<足し算後の結果>, <繰り上げビット>]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
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> : //...☆②
Num1Num2ResultCarry'1'「☆①」「☆②」「☆①」
//...前パートは省略
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
「☆②」
//...前のパートは省略
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型
AdderAdderLittleEndian
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'>>>>;
AdderCarまとめ
記事を書いた人
ナンデモ系エンジニア
主にAngularでフロントエンド開発することが多いです。 開発環境はLinuxメインで進めているので、シェルコマンドも多用しております。 コツコツとプログラミングするのが好きな人間です。
カテゴリー