java.lang.Long 探訪 - kagamihogeの日記

1.4 から 1.5 でいくつかのメソッドが追加されています。そのへんに絞ってソース読んでいこうと思います。

追加されたメソッドの特徴は、long の値を受け取ってそれを何らかのビット演算するところ。これらのメソッドのいくらかは、javadoc によるとamazon:Hacker's Delight]（邦題:[amazon:ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか）を参考にしているとのこと。イカツイタイトルから想像できるとおり、面白い実装してます。

この本は、ある計算をコンピュータらしいやり方―ビット演算―で行う方法をまとめた本のようです。本無しでコード読むには、俺にはむつかしいアルゴリズムのようで、今のところまともに理解できたメソッドは 3 つのみ･･･。

lowestOneBit(long i)

このメソッドの役割を javadoc から抜粋。追加されたメソッドはどれもイマイチ用途が想定できないんだけど、低レベルプログラミングで使うものなんでしょうか。

指定された long 値の最下位 (「もっとも右側」) の 1 のビットの位置に最大で 1 つの 1 のビットを持つ long 値

そしてコードはたったコレだけ。

return i & -i;

見る人が見ればこれだけでわかるんだろうなぁ･･･。俺はとりあえずサッパリわからなかったので、適当な値でコードの流れ（というほど量がないんだけど）を追ってみた。



  i  = 4864

  i  = (上位省略) 0000 0001 0011 0000 0000

 -i  = (上位省略) 1111 1110 1101 0000 0000

 -------------------------------------------

 AND = (上位省略) 0000 0000 0001 0000 0000

確かに、下から 9bit 目だけ bit が立つ結果が得られている。厳密な証明は出来ないけど、補数との関係を使って上手くやってるのだと思う。

補数は、bit を「反転して +1」すると得られる。

元の数値の bit を反転したものと AND をとったところで 0 になる。しかし、反転したものに +1 をすると、下位の bit から 1 の場所は 0 になっていき、0 が最初に出た地点が 1 になる。あとは、この数値―補数―と AND をとるだけで終了になる。



  i  = 4864

  i  = (上位省略) 0000 0001 0011 0000 0000

反転 = (上位省略) 1111 1110 1100 1111 1111

 -------------------------------------------

 AND = (上位省略) 0000 0000 0000 0000 0000
反転 = (上位省略) 1111 1110 1100 1111 1111

 +1  = (上位省略) 1111 1110 1101 0000 0000

素直に感動。

highestOneBit(long i)

次は lowestOneBit と対照のメソッド。以下は javadoc から抜粋。

指定された long 値の最上位 (「もっとも左側」) の 1 のビットの位置に最大で 1 つの 1 のビットを持つ long 値。

今度のコードは先のと雰囲気は似ているけどちょっと長い。



        i |= (i >>  1);

        i |= (i >>  2);

        i |= (i >>  4);

        i |= (i >>  8);

        i |= (i >> 16);

        i |= (i >> 32);

        return i - (i >>> 1);

これもやっぱり俺にはよくわからないので、適当な値で動きを見てみた。



      i        = 198880

      i        = 0000110000100011100000

i |= (i >>  1) = 0000111000110011110000

i |= (i >>  2) = 0000111110111111111100

i |= (i >>  4) = 0000111111111111111111

i |= (i >>  8) = 0000111111111111111111

i |= (i >> 16) = 0000111111111111111111

i |= (i >> 32) = 0000111111111111111111

      i >>> 1  = 0000011111111111111111














































































-






































 i - (i >>> 1) = 0000100000000000000000

色々 bit が動いた結果、確かに一番上の bit だけ立っている結果が得られている。

左から bit を見ていって、最初に 1 が出た場所から右をすべて 1 にしているらしい。先のメソッドとはなにやら逆の雰囲気がある。それで得られた数値を更に 1 bit シフトしてやって、それと引き算すれば、欲しい結果は確かに出てくる。

このシフト演算が何をするのかは、上の例だと分かりづらいので、最上位 bit にだけ 1 が立った数値（Long.MIN_VALUE）の例を見てみる。



      i        = 0x8000000000000000L

      i        = 1000000000000000000000000000000000000000000000000000000000000000

i |= (i >>  1) = 1100000000000000000000000000000000000000000000000000000000000000

i |= (i >>  2) = 1111000000000000000000000000000000000000000000000000000000000000

i |= (i >>  4) = 1111111100000000000000000000000000000000000000000000000000000000

i |= (i >>  8) = 1111111111111111000000000000000000000000000000000000000000000000

i |= (i >> 16) = 1111111111111111111111111111111100000000000000000000000000000000

i |= (i >> 32) = 1111111111111111111111111111111111111111111111111111111111111111

i >>> 1        = 0111111111111111111111111111111111111111111111111111111111111111


































































































































































-
















































































i - (i >>> 1)  = 1000000000000000000000000000000000000000000000000000000000000000

「最初に 1 が出た場所から右をすべて 1」の様子がこれだとよくわかる。

「i |= (i >> x) 」は「i に bit が立っている場所から、右方向へ少なくとも x*2 個分 1 が連続する数値になる」ように処理を行う。x = 1, 2, 4, 8, ... 32 と順にすることで、bit が連続する個所を少しずつ増やしていっている。

つまりは

i |= (i >> 1) → bit が 2 連続で立ってない場所はなくなる。
i |= (i >> 2) → bit が 4 連続で立ってない場所はなくなる。
i |= (i >> 4) → bit が 8 連続で立ってない場所はなくなる。
...
i |= (i >> 32) → bit が 64 連続で立ってない場所はなくなる。

ということをしている。

また、最後の i >>> 1 だけ違うシフト演算を使っているのがミソ。これによって「最上位の bit 位置から右にすべて bit がたっている」数値から「最上位の一つ右の bit 位置からすべて bit がたっている」数値が得られる。あとは引き算するだけ。

うーん･･･これもすごい。

signum(long i)

とりあえず読めたメソッドはこれで最後。下記は javadoc から抜粋。

指定した long 値の符号要素を返します (指定した値が負の場合、戻り値は -1。

コードはこれまた簡潔極まりない。

return (int) ((i >> 63) | (-i >>> 63));

これも適当な値で動きを見てみる。

i = 120
i = 0000000000000000000000000000000000000000000000000000000001111000
-i = 1111111111111111111111111111111111111111111111111111111110001000

- - - - -

i>>63 = 0000000000000000000000000000000000000000000000000000000000000000
-i>>>63 = 0000000000000000000000000000000000000000000000000000000000000001

- - - - -

OR = 0000000000000000000000000000000000000000000000000000000000000001
OR = 1

i = -120
i = 1111111111111111111111111111111111111111111111111111111110001000
-i = 0000000000000000000000000000000000000000000000000000000001111000

- - - - -

i>>63 = 1111111111111111111111111111111111111111111111111111111111111111
-i>>>63 = 0000000000000000000000000000000000000000000000000000000000000000

- - - - -

OR = 1111111111111111111111111111111111111111111111111111111111111111
OR = -1

これは割と見たままというか。

63bit の算術シフトは、もっとも左の bit が立っていれば―マイナスの数であれば―ぜんぶ 1 で埋まる。そうでなければ―プラスの数であれば―ぜんぶ 0 になる。
63bit の論理シフトは、もっとも左の bit が立っていれば―マイナスの数であれば―最下位 bit だけ 1 になる。そうでなければ―プラスの数であれば―ぜんぶ 0 になる。

表にまとめるとこんな感じ。

iの符号	i >> 63	-i >>> 63	ORの結果
プラス	0	1	1
マイナス	-1	0	-1

ホント、上手いなぁ･･･という感想しか出てこないです。

http://mindprod.com/jgloss/benchmark.html

signum のパフォーマンス

ところでこの signum。他にも解きかたがありそうな気がする。単純に if 文 3 つ並べるだけでもいいハズだし。やっぱり簡潔なコードは早いのかな？と思ったので速度計測してみた。

結論からいうと、割に遅い。単純に if 文 3 つのやり方と比べてみたが、入力値を色々変えてもやっぱり遅い。

うーん？と思ってたけどそこは web の出番。海の向こうにはやはり似た疑問を持たれた方がいて、詳細なまとめを作られていました。

benchmark : Java Glossary

様々な signum の実装を、様々なハードウェア・ソフトウェア設定（最適化など）環境で計測しています。このページの重要な部分をまとめると、

Long#signum は 32 bit 環境下ではかなり遅い
Long#signum は 64 bit 環境下ではかなり早い
Long#signum は非常に簡潔なコード

ということらしい。やはり 32bit 環境で 64bit の演算するのはどうしても遅くなっちゃうみたいだねぇ。

コレは誰がどんな環境で使うかわからない「Java API」なわけで。つまりは最も簡潔なコード選択したのは素晴らしい判断なんだろうなぁ。