Hatena::ブログ(Diary)

風と宇宙とプログラム このページをアンテナに追加 RSSフィード

2009-11-19

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+100Compile 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などの暗黙の型変換が実行されます。このことは知らなくてもほとんど問題はないことだと思いますが、仕様できちんと定義されているということは覚えてもよいでしょう。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証