javascriptで整数の変数を強制的に符号なし整数に変換する方法

chromeでPageRankを表示するための拡張機能PageRankToolStripでURLからハッシュ値を出すような処理が入っていて、そこで符号なし整数のビット演算処理があります。もとにしたPHPのコードでは

$a = sprintf('%u', $a);

のような方法で整数値を符号なしで扱うようにしてあったのですがjavascriptにはsprintfなんかないのでどうすればいいのか困ってしまいました。javascriptの整数は内部的には32bit intで扱われていて(Firefox3.1, Chrome2.0の場合)、演算の結果が0×80000000を超えると自動的に負の値になります。

どうしたらいいのか検索したら、符号なしシフト演算子>>>で0ビットシフトしろって書いてありました。

var a = 0xffffffff; // 4294967295
var b = a & 0xffffffff; // -1
var c = b >>> 0; // 4294967295

常識かもしれない＆あんまり使う場面ありませんが知らなかったので。

追記

あいまいに32bit intで扱われてると書いていたところを404 Blog Not Found:javascript – には整数はないでとりあげていただいてはてなブックマーク – 404 Blog Not Found:javascript – には整数はないでもいろいろコメントいただいてたのでFirefoxのjavascriptエンジンであるspidermonkeyの実装についてだけもうちょっと詳しく調べました。

ECMAScriptの仕様上は整数は存在しませんが、実装する上はdoubleとintで4バイトも差があるのでメモリ効率が違ってくる(=実行速度も違ってくる)のと、整数演算で済むのと浮動小数点演算になるのとでは必要なCPUサイクルが一桁違うので、intで済む範囲では極力doubleを使わないでintを使うようなっています。FirefoxのjavascriptエンジンであるSpiderMonkeyではどこが境界線になっているか見てみました。

SpiderMonkeyではSpiderMonkey Internals – MDCに

operates on values of type jsval—type-tagged pointer-size words that represent the full range of JavaScript values.

とあるようにJavaScriptの変数はすべてjsvalというポインタで表されていて、その実体は32bitのポインタになっています。そしてそのポインタの下位3ビットをタグとして利用しています(なので実際に変数が確保されているアドレスは必ず8の倍数になります)。タグの種類は以下の5つ。

#define JSVAL_OBJECT            0x0     /* untagged reference to object */
#define JSVAL_INT               0x1     /* tagged 31-bit integer value */
#define JSVAL_DOUBLE            0x2     /* tagged reference to double */
#define JSVAL_STRING            0x4     /* tagged reference to string */
#define JSVAL_BOOLEAN           0x6     /* tagged boolean value */

コメントからすると内部実装では数値は31bitで表現できるときはint32で表現して、その範囲を超えたらdoubleになるようになっているようです。

実際のコードを見てみる前に、スタンドアロンのSpiderMonkeyのシェルについているdis()で関数のバイトコードをダンプして見ることができるので、バイトコードを見てみましょう。

js> dis (function () { a=0xffffffff; b=a&a; print (b>>>0)})
flags: LAMBDA INTERPRETED
main:
00000:  bindname "a"
00003:  double 4294967295
00006:  setname "a"
00009:  pop
00010:  bindname "b"
00013:  name "a"
00016:  name "a"
00019:  bitand
00020:  setname "b"
00023:  pop
00024:  callname "print"
00027:  name "b"
00030:  zero
00031:  ursh
00032:  call 1
00035:  pop
00036:  stop

Source notes:
  0:    32 [  32] xdelta
  1:    32 [   0] pcbase   offset 8

そうするとたしかに32bitでしか表現できない0xffffffffはdoubleで確保されています！変数aはJSVAL_DOUBLEで初期化されることになります。

じゃあそのJSVAL_DOUBLEをどうやってビット演算の&をしているのかバイトコードbitandの中身を見てみましょう。bitandはBITWISE_OP(&)というコードで定義されていて、マクロの中身は

#define BITWISE_OP(OP)                                                        \
    JS_BEGIN_MACRO                                                            \
        FETCH_INT(cx, -2, i);                                                 \
        FETCH_INT(cx, -1, j);                                                 \
        i = i OP j;                                                           \
        regs.sp--;                                                            \
        STORE_INT(cx, -1, i);                                                 \
    JS_END_MACRO

こうなっています。引数はスタックに入れてあってそれを持ってきてintに変換して&をとって戻してます。FETCH_INTは中でjs_ValueToECMAInt32()といういかにもな名前の関数を呼んでいてここでdouble->intの変換が行われています。

int32
js_DoubleToECMAInt32(jsdouble d)
{
    int32 i;
    jsdouble two32, two31;

    if (!JSDOUBLE_IS_FINITE(d))
        return 0;

    i = (int32) d;
    if ((jsdouble) i == d)
        return i;

    two32 = 4294967296.0;
    two31 = 2147483648.0;
    d = fmod(d, two32);
    d = (d >= 0) ? floor(d) : ceil(d) + two32;
    return (int32) (d >= two31 ? d - two32 : d);
}

31bitで表せる最大値で割り算をして余りを整数とみなしたときに正負を考慮した上で変換しています。ここで無事doubleの4294967296.0になっていた0xffffffffは整数に戻ってきて0xffffffff & 0xffffffff => 0xffffffffの演算が終了します。

問題は次のSTORE_INTです。SpiderMonkeyの実装ではjsvalの最下位ビットはjsvalが保持する値が整数かどうかを示すフラグになっているので31bitまでの値しか保存できません。32bitでしか表現できない0xffffffffはどうなるのか?
というと、ふつうに31bitでしか表せない値はdoubleで保存されるだけです。

#define STORE_INT(cx, n, i)                                                   \
    JS_BEGIN_MACRO                                                            \
        if (INT_FITS_IN_JSVAL(i))                                             \
            regs.sp[n] = INT_TO_JSVAL(i);                                     \
        else if (!js_NewDoubleInRootedValue(cx, (jsdouble) (i), &regs.sp[n])) \
            goto error;                                                       \
    JS_END_MACRO

ここで出てくるJSVAL_INT_MAXは((1<<30) - 1)として定義されています。判別のしかたがトリッキーなのは正負両方で31bitを超えずに表現できるかを同時に判別するためです。

#define INT_FITS_IN_JSVAL(i)    ((jsuint)((i)+JSVAL_INT_MAX) <= 2*JSVAL_INT_MAX)

STORE_INTは0xffffffffをJSVAL_DOUBLEの-1に変換して保存することがわかりました。これでa & aが-1になる理由が実装からもわかりました。

最後に b >>> 0 で-1が4294967296になる仕組みも0xffffffffが-1になる仕組みと似たようなもので、ビットシフトの結果が31bitで表現できる範囲であればJSVAL_INTとして、できなければJSVAL_DOUBLEとして保存されるようになっています。今回の例では0xffffffffで31bitに収まらないのでJSVAL_DOUBLEの4294967296.0として保存される仕組みになっています。

というわけでSpiderMonkeyにおいて31bitを超える整数はdoubleになるという話でした。
ちなみに話がややこしくなるので省略しましたが、aに入れる値を小さくしていくとなぜか26bitで表現できるサイズになったときにint32というバイトコードに変わります。なので整数が常にJSVAL_DOUBLEとして初期化されるわけではありません。