■

さっきjavaのIntegerのtoStringを読んだ。で、その過程で、IntegerのgetChars(int i, int index, char[] buf)の部分の実装(の一部)で感動したので、それを書く。あんまりjavaの話ではない。

感動した部分はこれの、

// Generate two digits per iteration
while (i >= 65536) {
    q = i / 100;
// really: r = i - (q * 100);
    r = i - ((q << 6) + (q << 5) + (q << 2));
    i = q;
    buf [--charPos] = DigitOnes[r];
    buf [--charPos] = DigitTens[r];
}

ここ

    r = i - ((q << 6) + (q << 5) + (q << 2));

コメントから推測するに、どうやら、

((q << 6) + (q << 5) + (q << 2))

で q * 100 が計算できているようなのだが、最初意味がわからなかった。

まず、ほんとにそうなってるのかとりあえずirbで確認してみる。

irb(main):001:0> i = 65536
=> 65536
irb(main):002:0> (i << 6) + (i << 5) + (i << 2)
=> 6553600

やはり、100倍になっているようだ。

で、しばらく考えて、1ビットずらすということは、2倍するのと同じだったよなーと思う。そこで元の数字の2の6乗 + 2の5乗 + 2の2乗を足してみる。

irb(main):001:0> i = 65536
=> 65536
irb(main):002:0> (i * (2 ** 6)) + (i * (2 ** 5)) + (i * (2 ** 2))
=> 6553600

やはり、これで100倍になってるみたい。

ここで、やっと気がついて、iでくくってみる。すると

irb(main):001:0> i = 65536
=> 65536
irb(main):002:0> i * ((2 ** 6) + (2 ** 5) + (2 ** 2))
=> 6553600

おお。同じだ。

たしかに64 + 32 + 4は100だ。

ということで、やっぱりビット演算だけで100倍してるみたい。すげー、っていうお話。
普通に100倍するよりもやっぱりはやいのかなー。