四則演算を JavaScript で実装する
aki note ≫ Google 電話面接を受けました orz （いまは消えてるけど）にて
割り算が壊れました。自分で実装してみてください
という質問が紹介されていた。
せっかく(?)の機会なので、割り算だけでなく、四則演算を全部壊してみて、JavaScript で実装して見ることにした。
JavaScript を選んだのは、コンパイル不要、ビット演算がある、Firebug で手軽に確認できる、という理由から。それ以上の深い意味はない。
ということで、次のような問題に一般化してみた。
問い
四則演算を JavaScript で実装しなさい。
演算子は ==、!= およびビット演算子のみ使ってよいものとします。
補足
例えば、for 文で
for(var i = 0; i < 10; i++){
// ...
}
と書くためには、< 演算子と ++ 演算子を自前で実装しなきゃならない。
++ 演算子は次のように定義できる。
function increment(i){
var c = 1;
while(c){
if(i & c){
i &= ~c;
c <<= 1;
}
else{
i |= c;
break;
}
}
return i;
}
一番右のビットから見ていって、1 である限りは 0 にしていく。0 ならそのビットを 1 して終わり。桁あふれなら終了、としている。
例を書くと分かりやすいかもしれない。
01001111 +) 1 ---------- 01010000
ソースコード中の while や if の条件式では != 0 を省略している。厳密にはいちいち書くべきなんだけど、めんどくさいし読みにくいので。
加算
前置きが長くなったけど、まずは足し算から。
すごく簡単にやるなら、さっきの increment を使って
function add_simple(a, b){
while(b){
a = increment(a);
b = decrement(b);
}
return a;
}
と書いてしまえば終わり。decrement は increment とほぼ同じコードで実装できる。
ただ、この実装だと、b が -1 (0xffffffff) のときに42億回 while 文が回ってしまうのでダメすぎ、実用に耐えなさすぎ。
ということで、改良。
function add(a, b){
var sum = a;
while(b){
var carry = (a & b) << 1;
sum = a ^ b;
a = sum;
b = carry;
}
return sum;
}
a ^ b で各桁単独の足し算を取得しつつ、a & b で繰り上げを計算。繰り上げがある場合は、繰り上げ部分を足して、それでも繰り上がればまた足して・・・の繰り返し。
a 01011010 b +)01001001 ---------- a 00010011 <- a ^ b b +)10010000 <- (a & b) << 1 ---------- a 10000011 b +)00100000 ---------- a 10100011 b 00000000 <- b が 0 なので終了
だいぶ早くなる。
Firebug で試してみる。
>>> add(1, 1) 2 >>> add(99, 1) 100 >>> add(99, -1) 98 >>> add(-3, 5) 2
負の数でもうまく理由が分からない人は２の補数（後述）を勉強してね。
減算
これはだいぶ簡単。
// 正・負を入れ替える
function reverse_sign(a){
return add(~a, 1);
}
function sub(a, b){
return add(a, reverse_sign(b));
}
2の補数って知ってる？ で終わり。
2の補数は慣れるまで分かりにくい概念だけど、こう考えてみるのはどうだろう。
- 10進数で12桁の電卓があります
- でも、壊れていて下4桁しか表示できません
- 3 + 9999 は 10002 だけど、この電卓で表示したら 2
- 同じように 5 + 9999 = 4、9 + 9999 = 8
- この壊れた電卓では 9999 は -1 と同じ！？
- 9999 = 10000 - 1
- 10000 を足そうが引こうが表示中の値は変わらない
- 3 + 9999 = 3 + (10000 - 1) = 3 - 1
乗算
次は掛け算。桁あふれは無視してる。
function mul(a, b){
var product = 0;
while(b){
if(b & 1){
product = add(product, a);
}
a <<= 1;
b >>= 1;
}
return product;
}
筆算のやり方を思い出せば簡単。
1010
x)0101
------
1010
0000
1010
+)0000
---------
0110010
b の i ビット目が 1 なら、a を i ビット左にシフトしたものを足す、というだけの実装。
上の実装は負の値を無視してしまってるので、まじめにやるならこうなる。
// 正の数かどうか調べる
function is_positive(a){
return (a >>> 31) == 0;
}
function mul2(a, b){
if(!is_positive(a) && !is_positive(b)){
return mul(reverse_sign(a), reverse_sign(b));
}
else if(!is_positive(a)){
return reverse_sign(mul(reverse_sign(a), b));
}
else if(!is_positive(b)){
return reverse_sign(mul(a, reverse_sign(b)));
}
else{
return mul(a, b);
}
}
is_positive 関数で int が 32bit だと仮定しているあたりがかっこ悪いけど、これが一番シンプルかと。
除算
長かった。いよいよ割り算。Google の電話面接で聞かれるだけあって複雑。
0 での除算や正負は考えずに実装した。
// 比較演算子の代わり
function cmp(a, b){
var s = sub(a, b);
return s == 0 ? 0 : is_positive(s) ? 1 : -1;
}
// MSB = 最上位ビット(Most Significant Bit) を取得
function msb(i){
var ret = 0;
while(i){
i >>>= 1;
ret = add(ret, 1);
}
return ret;
}
function div(a, b){
var quotient = 0;
if(cmp(a, b) == -1){
return 0;
}
var i = sub(msb(a), msb(b));
while(is_positive(i)){
quotient <<= 1;
if(cmp(a >> i, b) != -1){
a = sub(a, b << i);
quotient = add(quotient, 1);
}
i = sub(i, 1);
}
return quotient;
}
これも筆算をイメージして実装。でも複雑なので説明する体力なし。
もっとスマートな実装はないものか... もしくはもっとアクロバティックなの。
すごい人達に期待。改良案や別の言語での実装をお待ちしています。
まとめ代わりに種明かし
こうやって記事にすると、私がすごくできる人間に見えるかもしれないけど、実はかなり苦しみました。
そんな中、非常に参考になったのが 基礎から学ぶコンピュータ というサイト。そこに書いてあることを理解して、JavaScript に移植しただけ、といっても過言ではない。
四則演算の実装といえば、コンピュータ・サイエンスの基礎中の基礎なんだけど、そこをちゃんと理解しているか聞いてくる Google 先生はさすが。普段からコンピュータの仕組みを理解した上で使っているかを問われているわけですね。
この辺の内容を基礎から勉強するなら、パタヘネがよいんじゃないでしょうか。
コンピュータの構成と設計~ハードウエアとソフトウエアのインタフェース 第3版 (上)
- 作者: デイビッド・A. パターソン
- 出版社/メーカー: 日経BP社
- 発売日: 2006-03-16
- メディア: 単行本
- Amazon のレビューを見る