今回の記事は「特に」個人の感想色が強く、JavaScript好きにとって不快になる要素が含まれているかもしれません
おそらく手続き型言語であれば必ずと言って良いほど存在するbit演算。今回はJavaScript(以下JS)のNumber
型におけるbit演算は自分が今まで見てきたbit演算の中でも最悪の物であることをお伝えしたいと思う。
数値で扱えるbit数について
基本的に数値で扱えるbit数は決して無限大ではなく、限りがある。そのため数値を扱うときはこのbit数を気にしなければならない。たとえば今の一般的なハイスペックコンピュータにおいてCのint
は32bitの符号付き整数である。つまりそのうちの1bitは正の値であるか負の値であるかのフラグに使われるため、-2147483648(0x80000000)
~2147483647(0x7fffffff)
の範囲の整数値が扱えることになる。
当然、JSの数値にも限りがあるのだが、JSの場合は数値はNumber
型と呼ばれる、64bitで表現される倍精度実数しか扱わない*1ことがほとんどである。Number
型は64bitであるが、そのうちの1bitが正の値か負の値かを判別するフラグに使われる符号bitで、11bitが の の部分を表す指数bit、52bitが小数点以下を表す仮数bitである。
指数は ~ の範囲で表され、仮数は ~ の範囲で表される。ただし、指数bitが0
であった場合に限り仮数bitにおいて52bitとは別にある整数部分が0
になることを示す(0x001
~0x7fe
の場合は整数部分が1
となる)。つまり、±0(±0x00_00_00_00_00_00_00_00)
~±1.7976931348623157e+308(±0x7f_ef_ff_ff_ff_ff_ff_ff)
の範囲の実数を表現することが可能だ。
・・・あれ?いくつか表せていない値がなくないか?と思った人はきっと賢い。実はJSのNumber
型において、指数bitが0x7ff
の場合、仮数bitが0
であれば±Infinity
(無限大)、0 <
であれば±NaN
(そもそも数でない)という特別な値を表すようになっている。
指数部が仮数部の整数部分を表現する役割もあることを考慮すると、JSのNumber
型の精度は53bitである。これは整数値を表現する場合も同様なので、JSのNumber
型の値は54bitの符号付き整数型の値としても表現できると考えても良いだろう。
JavaScriptでのbit演算
さて本題に入ろう。JSのbit演算ではまず覚えておかなければならないことがある。それは実際に計算される値の型はNumber
型ではないということである。
ではJSのbit演算は何を計算しているのか?その答えは、
Number
型を一旦32bit整数型に変換してから計算している
である。以降この型のことをInt32
型またはUint32
型と呼ぶことにする。もちろん、JSにはInt32
型、Uint32
型なんてものはないので、その値はNumber
型に変換して返されるというややこしい計算方法となっている。ここで問題となってくるのは、最大及び最小の範囲(Int32
型の場合-2_147_483_648(0x80_00_00_00)
~2_147_483_647(0x7f_ff_ff_ff)
、Uint32
型の場合0(0x00_00_00_00)
~4_294_967_295(0xff_ff_ff_ff)
)を超えた場合どうなってしまうのか?ということである。先述したようにJSのNumber
型は符号付き54bit整数としても表現できる。それはすなわち整数値から22bit分欠落すると考えても良いだろう。しかもInt32
型に変換する場合は、先頭の1bitが符号bitとして扱われてしまい、2_147_483_648
以上の値を表現したかったのに負の値になってしまうといった不具合も発生する。
Number
型で計算すると危険なbit演算子一覧
- (1)
(&)
演算子
2つの値どうしで各bitのAND演算を行う。たとえば 0b1010 & 0b0011
を計算すると、0b0010
が返ってくる。値の一部bitをマスクするためによく用いられる。
この演算はInt32
型に変換されてから計算され、AND演算は符号bitに対しても適用される。
- (2)
(|)
演算子
2つの値どうしで各bitのOR演算を行う。たとえば 0b1010 | 0b0001
を計算すると、0b1011
が返ってくる。値の一部bitだけをほかのbitに影響を与えることなく変更させるためによく用いられる。
この演算はInt32
型に変換されてから計算され、OR演算は符号bitに対しても適用される。
- (3)
(^)
演算子
2つの値どうしで各bitのExOR演算を行う。たとえば 0b1010 ^ 0b1100
を計算すると、0b0110
が返ってくる。値の一部bitだけをほかのbitに影響を与えることなく反転させるためによく用いられる。
この演算はInt32
型に変換されてから計算され、ExOR演算は符号bitに対しても適用される。
- (4)
(~)
演算子
1つの値で各bitのNOT演算を行う。たとえば ~0b1010
を計算すると、0b0101
が返ってくる。値の全bitを反転させるためによく用いられる。
この演算はInt32
型に変換されてから計算され、NOT演算は符号bitに対しても適用される。
- (5)
(<<)
演算子
1つの値に対し bit分左にシフトする。たとえば 0b0000_1010 << 3
を計算すると、0b0101_0000
が返ってくる。
この演算はInt32
型に変換されてから計算され、符号bitに対しても適用される論理シフトである。
- (6)
(>>)
演算子
1つの値に対し bit分右にシフトする。たとえば 0x00_ff_ff_00 >> 8
を計算すると、0x00_00_ff_ff
が返ってくる。
この演算はInt32
型に変換されてから計算され、符号bitに対しては適用されない算術シフトである。
特に負の値を右シフトする場合、シフトされたbitは0
ではなく1
で埋められる。たとえば、0xff_ff_00_00 >> 8
を計算すると、0x80_7f_ff_00
ではなく0xff_ff_ff_00
が返ってくるので注意が必要である。
- (7)
(>>>)
演算子
(>>)
と同じであるが、変換される型がUint32
型であり、実質論理シフトである、という点が異なる。
bit演算によって起こる不具合の例
たとえば54bitの符号付き整数値を7byteのリトルエンディアンのバイナリに変換したいとする。バイナリ生成にはUint8Array
を用いる。
たとえば0x12_34
のような32bitの範囲を超えないような数値であれば問題なくUint8Array
に変換できるだろう。なお、実行結果では各バイナリ値が10進数で表示されていることにあらかじめご了承いただきたい。以降の表示も同様である。
// Number 型の値をバイナリに変換する関数 const numberToBinary = (n) => { return new Uint8Array(7).map((_) => { const binary = n & 0xff; n >>>= 8; return binary; }); }; // 0x12_34 をバイナリに変換 console.log(numberToBinary(0x12_34));
Uint8Array(7) [ 52, 18, 0, 0, 0, 0, 0 ]
しかし0x12_34_56_78_9a
のような32bitの範囲を超えた値を格納すると、本来バイナリ値18(0x12)
も格納されるべきなのだがそれが欠落してしまう。
// 0x12_34_56_78_9a をバイナリに変換
console.log(numberToBinary(0x12_34_56_78_9a));
Uint8Array(7) [ 154, 120, 86, 52, 0, 0, 0 ]
これはJSの(>>>)
演算でNumber
型からUint32
型に変換されてしまったからであり、これはbit演算だけでは32bitを超える整数値は扱えないことを意味する。
対処法
対処法1: 整数値を2つに分割する
Number
型だけで対処したい場合「整数値を2つに分割する」のがパッと思いつく手段であろう。
そのためにはほんの少しだけ数学的な観点から考える必要がある。たとえば10進数において、ある数を で除算するとき、その数は 桁繰り下がる、という法則がある。たとえば は という結果が返ってくる。ここから、1桁繰り下がっていることがわかるだろう。
これは、2進数や16進数においてもほぼそうであると言える。今回、必要なのは16進数における桁の繰り下げ手法であるため、それをもとに考えてみる。
たとえば597(0x02_55)
に対して16(0x10)
で除算して小数点以下を切り捨てると、37(0x25)
となる。この例から、16進数において、ある整数を で除算して切り捨てると 桁繰り下がるという法則が成り立つことがわかる*2。
ただし、この法則が成り立つのは正の値である場合に限る。負の値のとき、 で除算すると辻褄が合わなくなる。なぜなら、コンピュータにおいて負の値は2の補数で表現されているからである。そのため、負の値の場合は除算した後に2の補数から1の補数に変換するといった処理が必須である。なお、辻褄が合わなくなるのも16で割り切れない場合に限る。これは16進数では0x0
~0xf
までを扱い、符号付き整数型において-0x0
という値は存在しないからである。
以上を踏まえると、整数値を2分割するためにまず元の値をUint32
型の値に変換し、残り22bitは元の値から0x01_00_00_00_00
(つまり )を除算し、負の値かつ16で割り切れない場合に1の補数に変換すればある程度は良さそうである。
// 0x12_34_56_78_9a を2つの値に分割する const u32Array = ((n) => new Uint32Array([ n | 0, n / 0x01_00_00_00_00 - Number(n < 0 && (n % 16) != 0) & 0x3f_ff_ff, ]))(0x12_34_56_78_9a); // 分割した2つの値を16進数で出力 u32Array.forEach((n) => { console.log(`0x${n.toString(16)}`); });
0x3456789a 0x12
ただ、これだけだと-4_294_967_295(0x3f_ff_ff_00_00_00_01)
~-1(0x3f_ff_ff_ff_ff_ff_ff)
を で除算したときかつ16で割り切れる場合に残り22byteが0
になってしまうため、想定した動作にはならないだろう。
// -16 を2つの値に分割する const u32Array = ((n) => new Uint32Array([ n | 0, n / 0x01_00_00_00_00 - Number(n < 0 && (n % 16) != 0) & 0x3f_ff_ff, ]))(-16); // 分割した2つの値を16進数で出力 u32Array.forEach((n) => { console.log(`0x${n.toString(16)}`); });
0xfffffff0 0x0
そこで、-0x01_00_00_00_00 < n
の場合においても1の補数に変換する。これにより問題が解決し、所望の値が得られる。
// -16 を2つの値に分割する const u32Array = ((n) => { const carryDown = 0x01_00_00_00_00; const toOneComplement = Number( n < 0 && ((n % 16) != 0 || -carryDown < n) ); return new Uint32Array([ n | 0, n / carryDown - toOneComplement & 0x3f_ff_ff, ]); })(-16); u32Array.forEach((n) => { console.log(`0x${n.toString(16)}`); });
0xfffffff0 0x3fffff
では以上をもとに、問題を解決したバイナリ変換を以下に示す。
// Number 型の値をバイナリに変換する関数 const numberToBinary = (n) => { const u32Array = (() => { const carryDown = 0x01_00_00_00_00; const toOneComplement = Number( n < 0 && ((n % 16) != 0 || -carryDown < n) ); return new Uint32Array([ n | 0, n / carryDown - toOneComplement & 0x3f_ff_ff, ]); })(); return new Uint8Array(7).map((_, i) => { const index = Number(4 <= i); const binary = u32Array[index] & 0xff; u32Array[index] >>>= 8; return binary; }); }; // 0x12_34_56_78_9a をバイナリに変換 console.log(numberToBinary(0x12_34_56_78_9a));
Uint8Array(7) [ 154, 120, 86, 52, 18, 0, 0 ]
対処法2: toString()
メソッドを使う
toString()
メソッドを使うのも一つの手である。toString()
はデフォルトで10進数の文字列を返すが、16
を引数として渡すことで16進数の文字列を返すことが可能になる。
// 0x12_34_56_78_9a を文字列に変換
console.log((0x12_34_56_78_9a).toString(16));
123456789a
これに対し末尾から2文字ずつslice()
メソッドを用いてからNumber
型に変換しUint8Array
に格納していくようにすれば正の値に関しては問題なく変換できる。
// Number 型の値をバイナリに変換する関数 const numberToBinary = (n) => { const binaryLength = 7; const s = n.toString(16); const sliceRange = [-2]; return new Uint8Array(binaryLength).map((_, i) => { const mask = i === (binaryLength - 1) ? 0x3f : 0xff; const slice = s.slice(...sliceRange); sliceRange.splice(0, 2, sliceRange[0] - 2, sliceRange[0]); return (slice !== '' ? parseInt(slice, 16) : 0) & mask; }); }; // 0x12_34_56_78_9a をバイナリに変換 console.log(numberToBinary(0x12_34_56_78_9a));
Uint8Array(7) [ 154, 120, 86, 52, 18, 0, 0 ]
もちろんこれだけでは足りない。なぜなら負の値を文字列に変換すると、2の補数ではなく正の値にそのまま-
をつけた文字列が返されるからである。
// -0x12_34_56_78_9a (つまり 0x3f_ff_ed_cb_a9_87_66 )を文字列に変換
console.log((-0x12_34_56_78_9a).toString(16));
-123456789a
これは実数において符号は負の値であるかを判定するフラグでしかなく、負の値は2の補数で表現されないためである。ではこれに対しどうすれば良いのかと言うと、まずは正の値に変換する。その際、負の値であるかどうかをフラグとして保存しておく。
const n = -42; // 負の値であった場合フラグを true にする const neg = n < 0; // 値を正の値に変換する const posNum = neg ? -n : n;
次に、整数において、負の値は2の補数として表されるため、あらかじめ-1
しておく。
// 2の補数に変換しておく const twoComplement = posNum - 1;
あとは文字列に変換しスライシングしてから、負の値フラグがtrue
であったときbit反転させれば負の値も扱うことが可能となる。
// 文字列に変換する const s = twoComplement.toString(16); ・ ・ ・ // 負の値であった場合にスライシングした文字列から変換した値をbit反転する const convertedNum = ((slice) => { const n = slice !== '' ? parseInt(slice, 16) : 0; if (neg) { return n ^ 0xff; } else { return n; } })(s.slice(...sliceRange); // 変換したバイナリを返す return convertedNum & mask; }
では以上をもとに、問題を解決したバイナリ変換を以下に示す。
// Number 型の値をバイナリに変換する関数 const numberToBinary = (n) => { const neg = n < 0; const binaryLength = 7; const s = (neg ? (-n - 1) : n).toString(16); const sliceRange = [-2]; return new Uint8Array(binaryLength).map((_, i) => { const mask = i === (binaryLength - 1) ? 0x3f : 0xff; const convertedNum = ((slice) => { const n = slice !== '' ? parseInt(slice, 16) : 0; if (neg) { return n ^ 0xff; } else { return n; } })(s.slice(...sliceRange)); sliceRange.splice(0, 2, sliceRange[0] - 2, sliceRange[0]); return convertedNum & mask; }); }; // -0x12_34_56_78_9a (つまり 0x3f_ff_ed_cb_a9_87_66 )をバイナリに変換 console.log(numberToBinary(-0x12_34_56_78_9a));
Uint8Array(7) [ 102, 135, 169, 203, 237, 255, 63 ]
対処法3: BigInt
を使う
Number
型におけるbit演算は問題がありすぎるし、対処も面倒なので、BigInt
型を使う。BigInt
型を使えば、簡単に問題を解決できてしまう。BigInt
型では(>>>)
演算子が使えないため、負の値を扱うと無限ループしてしまうが、(メモリの許す限り)サイズが無限大なので負の値は変換できないようにすれば問題はなく、さらに作るバイナリのサイズは何byteでも良い。
// BigInt 型の値をバイナリに変換する関数 const bigIntToBinary = (n) => { return new Uint8Array((() => { const array = []; for (; 0n < n; n >>= 8n) { array.push(Number(n & 0xff)); } return array; })()); }; // 0x12_34_56_78_9an をバイナリに変換 console.log(bigIntToBinary(0x12_34_56_78_9an));
Uint8Array(5) [ 154, 120, 86, 52, 18 ]
欠点としてはECMAScript 2020以降でないと使えないことか。
まとめ
以上から、Number
型におけるbit演算には以下のような問題がある。
- 使う側には見えない整数型に変換し、変な値になってしまうという初心者殺しが発生する
- 32bit以上の値を使ってbit演算をする場合、めちゃくちゃ手間がかかる
したがって、自分が伝えたいことは
Number
型を使ってbit演算をするべきではない
これに尽きる。bit演算するのであれば、Number
型ではなくBigInt
型を使うことを強くお勧めする。
*1:なお、ECMAScript 2020にてBigIntという型が追加されている
*2:実数の場合においても法則があるが、ややこしいので割愛する