JavaScriptのビット演算の仕組みを理解する

はじめに

JavaScriptの数値表現はIEEE754の64ビットの倍精度型浮動小数ですが、ビット演算はどのように定義されているのでしょうか。今回はそのビット演算について解説します。この仕様は10年以上前から変わらないのですが、改めてその部分が書籍などでどのように解説してあるかを見ると、and, or などのビット演算が教科書的に書かれているだけで、任意の数値に対してどう定義されるかについてはほとんど説明されていません。

JavaScript以外の言語では？

JavaScriptについて説明する前に、他の言語ではどうなっているでしょうか。ここでは、ちょっと手を抜いて実際に実行した結果のみを示します。バージョンによっては結果が違うかも知れません。

まずは、一番単純な 0 との orを調べてみました。つまり x | 0 の結果です。

x	C (gcc)	Java	Ruby	Perl
-123	-123	-123	-123	18446744073709551493
9876543210	1286608618	9876543210	9876543210	9876543210
123.45	Compile Error	Compile Error	NoMethodError	123
9.87e+12	Compile Error	Compile Error	NoMethodError	9870000000000
9.87e+200	Compile Error	Compile Error	NoMethodError	18446744073709551615

CとJavaでは浮動小数に対してのビット演算はコンパイルエラーになります。一方、Rubyはメソッド '|' が定義されていないという実行時エラーになりました。

Perlの結果は独特です。-123 | 0の結果の18446744073709551493は 2^64-123と一致します。9.87e+200 | 0 は 2^64-1です。

ちなみに、EmacsLispでも浮動小数上のビット演算(logand, logior, logxorなど)は実行時エラーになります。

次に、シフト演算を見てみます。15 << n の結果です。

n	C (gcc)	Java	Ruby	Perl
27	2013265920	2013265920	2013265920	2013265920
40	16492674416640	16492674416640	16492674416640	16492674416640
70	0 (warn)	960	17708874310761169551360	960
-1	-2147483648 (warn)	-2147483648	7	9223372036854775808
-2	-1073741824 (warn)	-1073741824	3	13835058055282163712
-123	480 (warn)	480	0	480
2.5	Compile Error	Compile Error	60	60
1.23e+100	Compile Error	Compile Error	RangeError	9223372036854775808

C言語とJavaでは数値15は64ビット整数としてコンパイルしています。

このように、多くの言語ではビット演算は整数に対して定義されますが、32ビット以上の数などについては、言語ごとに動作が異なるようです。

JavaScriptのビット演算

では、JavaScriptの場合はどうなるかみてみましょう。以下のようになります。

x | 0

x	JavaSript
-123	-123
9876543210	1286608618
123.45	123
9.87e+12	165153792
9.87e+200	0

15 << n

n	JavaScript
27	2013265920
40	3840
70	960
-1	-2147483648
-2	-1073741824
-123	480
2.5	60
1.23e+100	15

JavaScriptでは数値はIEEE754の64ビットの倍精度型浮動小数で表現されます。ビット演算を意味のあるものにするには、他の言語でも見たように、整数値に変換する必要があります。整数値として64ビットの整数型はIEEE754とコンフリクトしますので使えません。結局、JavaScriptでは32ビットの整数に変換してビット演算を行います。これは、四則演算でオペランドが数値でない場合には、数値に暗黙に型変換しますが、ビット演算もそれと同様であり、演算が有効になるように32ビット整数型に暗黙に型変換が行われるということです。

任意の数値を32ビット整数に変換する規則はECMA262規格書に記述されています。JavaScriptでほぼそのまま記述すると以下のようになります。

function ToInt32(x) {
  x = Number(x);
  if (!isFinite(x) || x === 0) {
    return 0;
  }
  var p32 = 4294967296;    // = 2^32
  var p31 = 2147483648;    // = 2^31
  var neg;
  if (x < 0) {
    neg = true;
    x = -x;
  }
  var x = Math.floor(x) % p32;
  if (x > p31) {
    x -= p32;
  }
  return neg ? -x : x;
}

ちょっと複雑に見えますが、ゼロに近い整数に丸めて、それを 2^32 で割った余りです。32ビット目を符号として扱う点が注意するだけです。また、x === 0で 0を返しているのはゼロにも符号があり -0 のときは +0 にするという意味です。

符号なしの32ビット整数に変換するのも同様に以下のようになります。

function ToUint32(x) {
  x = Number(x);
  if (!isFinite(x) || x === 0) {
    return 0;
  }
  var p32 = 4294967296;    // = 2^32
  var neg;
  if (x < 0) {
    neg = true;
    x = -x;
  }
  x = Math.floor(x);
  if (neg) {
    x = -x;
  }
  x = x % p32;
  return (x < 0) ? p32 + x : x;
}

ToInt32とToUint32には以下の恒等式が成立します。

ToInt32(ToUint32(x)) == ToInt32(x)
ToUint32(ToInt32(x)) == ToUint32(x)

&, |, ^, ~ ビット演算

ToInt32を使ってJavaScriptのビット演算は以下のように定義されます。[&]のようにカッコで括ったのはJavaScriptの&ではなく、「生の」メタなオペレータという区別をするためです。

x & y ::= ToInt32(ToInt32(x) [&] ToInt32(y))
x | y ::= ToInt32(ToInt32(x) [|] ToInt32(y))
x ^ y ::= ToInt32(ToInt32(x) [^] ToInt32(y))
 ~x   ::= ToInt32([~]ToInt32(x))

つまり、xとyをToInt32してビット演算を適用して、符号つき32ビットにするということです。

例であげた x | 0 の値は、ToInt32(x)の値そのものであることが分ります。

<<, >>, >>> シフト演算

シフト演算も同様に以下のように定義されます。オペレータの右側の値は0x1Fでマスクされることに注意してください。

x <<  y ::= ToInt32(ToInt32(x)  [<<]  (ToUint32(y) [&] 0x1F))
x >>  y ::= ToInt32(ToInt32(x)  [>>]  (ToUint32(y) [&] 0x1F))
x >>> y ::= ToUint32(ToUint32(x) [>>>] (ToUint32(y) [&] 0x1F))

いくつか確認してみます。

15 << 40
 = 15 << (ToUint32(40) & 0x1F)
 = 15 << (40 & 0x1F)
 = 15 << 8
 = 3840

15 << -1
 = 15 << (ToUint32(-1) & 0x1F)
 = 15 << (4294967295 & 0x1F)
 = 15 << 31
 = -2147483648

15 << -123
 = 15 << (ToUint32(-123) & 0x1F)
 = 15 << (4294967173 & 0x1F)
 = 15 << 5
 = 480

数値の型変換をJavaScriptで記述する

ECMA262規格書に記述されているToInt32とToUint32関数をJavaScriptで書いてみましたが、ビット演算を使うと以下のように簡潔に記述できます。

function ToInt32(x) {
  return x | 0;
}
function ToUint32(x) {
  return x >>> 0;
}

また、ToUint16という関数も定義されています。これは、String.fromCharCode()関数でUTF16のUnicodeから文字列を生成するときに使われます。これを利用するとToUint16関数は次のように実装できます。文字列を生成するためコストがかかる関数なので実用的ではありませんが。

function ToUint16(x) {
  return String.fromCharCode([x]).charCodeAt(0);
}

まとめ

JavaScriptの数値は仕様的には64ビット倍精度の浮動小数です。それに対してビット演算は32ビットの整数に変換して適用されます。32ビットより大きい整数や浮動小数（または負の数など）に対してビット演算を行うときは、ToInt32やToUint32などの暗黙の型変換が実行されます。このことは知らなくてもほとんど問題はないことだと思いますが、仕様できちんと定義されているということは覚えてもよいでしょう。