[Javascript] 64ビット演算のエミュレート

「最近記事書いてないね」って突っ込まれる。
プログラムは、たくさん書いているのですが。

ECMA-262で定義されている通り、ビット演算子は符号付き32ビット整数しか扱えない。Number型は倍精度フォーマット IEEE 754型なので64ビットまで扱えるので、結果が2の31乗以上の値になるビット演算子を扱う時には2の32乗を加算して、補正してやる必要がある。

※ Math.pow関数など、2の53乗以上の数は誤差が出るので注意

console.log((Math.pow(2, 53)-1).toString(2)); // => 11111111111111111111111111111111111111111111111111111
console.log((Math.pow(2, 54)-1).toString(2)); // => 1000000000000000000000000000000000000000000000000000000

64ビット演算のエミュレート。
ECMAScript4にならないと演算子のオーバーロードができないので、関数呼び出しでエミュレートする。関数の呼び出しコストについては後述。

var ASSERT = function() { // {{{
var arg = new Array(arguments.length);
for(var i=0,len=arg.length;i<len;++i)i>[i] = arguments[i];
if('console' in window && 'assert' in console) { // use Assert of Firebug
console.assert(arg.shift(), arg.pop());
} else {
if(!arg.shift()) throw(arg.pop());
}
}; // }}}


// 4294967296 is Math.pow(2, 32);
Number.prototype.bitwiseAnd = function(rhs) {
  return (this & rhs > -1)? this & rhs : this & rhs + 4294967296;
};
Number.prototype.bitwiseOr = function(rhs) {
  return ((this | rhs) > -1)? this | rhs : (this | rhs) + 4294967296;
};
Number.prototype.bitwiseNot = function() {
  return ((~this) > -1)? ~this : (~this) + 4294967296;
};
Number.prototype.bitwiseXor = function(rhs) {
  return ((this ^ rhs) > -1)? this : (this ^ rhs) + 4294967296;
};

ASSERT(0xffffffff.bitwiseAnd(0xffffffff) == 1, 'bitwiseAnd: 0xffffffff & 0xffffffff is equal 4294967295.');
ASSERT(-0x1.bitwiseAnd(0xffffffff) == -1, 'bitwiseAnd: -0x1 & 0xffffffff is equal -1.');
ASSERT(0x1.bitwiseOr(0xffffffff) == 4294967295, 'bitwiseOr: 0x1 | 0xffffffff is equal 4294967295.');
ASSERT(-0x1.bitwiseOr(0xffffffff) == -4294967295, 'bitwiseOr: -0x1 | 0xffffffff is equal 4294967295.');
ASSERT(0x1.bitwiseXor(0xffffffff) == 4294967294, 'bitwiseXor: 0x1 ^ 0xffffffff is equal 4294967294.');
ASSERT(-0x1.bitwiseXor(0xffffffff) == -4294967294, 'bitwiseXor: 0x1 ^ 0xffffffff is equal -4294967294.');
ASSERT((~1) == -2, 'signed 32 bitwiseNot: (~1) is equal -2');
ASSERT(0x1.bitwiseNot() == 4294967294, 'bitwiseNot: 0x1 ^ 0xffffffff is equal 4294967294.');
ASSERT(-0x1.bitwiseNot() == -4294967294, 'bitwiseNot: 0x1 ^ 0xffffffff is equal -4294967294.');

delete ASSERT;

命令数を減らして高速化したいというニーズから、ビット演算を使用する事が多いかと思うので、上記の場合、関数呼び出しのコストが余分にかかる事に気をつける必要があります。インライン展開したコードに比べて、関数が呼び出されるコードでは、約2.5倍程遅くなるので必要に応じてインライン展開してください。

AND演算を100000回実行した結果
インライン: 387ms
bitwiseAnd関数: 991ms

[Javascript] 64bit Number型を上位32bitと下位32bitに分割

JavascriptのNumber型は、倍精度64bitフォーマット IEEE 754型(double-precision 64-bit format IEEE 754 values)です。Javascriptでは、64ビット演算はできないので、上位32ビットと下位32ビットにわけて計算しないといけません。また、Math.pow(2, 55)など大きな数を扱う時には誤差も発生するので別途内部表現を設けて対応しないといけません。

パフォーマンスの犠牲を払っていますが、
上位32ビットと下位32ビットに変換します。

Number.prototype.rdHi = function() {
 var b = this.toString(2);
 return parseInt(b.slice(0,b.length-32), 2) || 0x0;
};
Number.prototype.rdLo = function() {
 var b = this.toString(2);
 return parseInt(b.slice(Math.max(b.length-32, 0), b.length), 2);
};
console.log(0x03ffffffff.rdHi() & 0xffffffff); // => 3
console.log(0xffffffffff.rdHi() & 0xffffffff); // => 255
console.log(0x01ffffffff.rdLo());              // => 4294967295
console.log(0x01ffffffff.rdLo() & 0xffffffff); // => -1

注意しなければいけないのは、最上位ビットは符号ビットだと言う事。最後の結果は、0xffffffffではなく、-1になります。32bit値を何かしらのフラグとして利用する場合は、最上位ビットを考慮したロジックを組む必要があります。

Number型(64bit)を利用する場合速度とメモリ消費量のトレードオフとなります。
例を挙げれば、ボードゲームを実装する際のデータ構造として一般的なBit Boardならば、次のどちらかの戦略をとる事になるかもしれません。

• 64bit値を下位32bitと上位32bitの二要素として配列に持つ
• 64bit変数で保持して、実行時に上記のメソッドを適用する。

一つ目は、メモリ消費量が多くなりますが配列から何かしらの操作を実行する時のコストは低くなり、二つ目はメモり消費量は減らせるが実行時のコストが大きくなります。

P.S
2の53乗以上のデータも扱えるように、倍精度でも誤差がでないNumber型を実装していたら似たようなライブラリがたくさんあったので中断。きちんと調べてから実装するべきだった。