概要

Java には Integer.bitCount( i ) という、intの1のビットの数を数えるメソッドがいます。

例えば「100」は2進数で「1100100」

見ての通り、2進数表記内に「1」が3ついます。なので、Integer.bitCount( 100 ) と書くと「3」が返ってきます。

この機能がどうやって「1」の数を数えているかが気になって中身を見てみたら、個人的にとても面白いと感じる処理が書いてあったので紹介します。

bitCountの動作例

bitCountはこんな感じで動きます。

// 例として「120」を使用
// 120の2進数表示は以下
String bin = Integer.toBinaryString( 120 );
System.out.println( bin );
  // => 1111000

// 120のbitCountの結果
int cnt = Integer.bitCount( 120 );
System.out.println( cnt );
  // => 4

Integer.toBinaryStringは数値を2進数表記に直します。

120の2進数表記は「1111000」なので、bitCountした時の結果は「4」になります。

bitCountの処理

さて、それでは本題です。

以下がInteger.bitCountが内側でやっている処理です。先ほどの例で言うと、この処理に120を渡すと、1のビットの数(=4)が返るわけですが……

public static int bitCount(int i) {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}

エー、ナンデスカ、コレ???

私のような低級プログラマには、リカイし難い処理が並んでいます。

とりあえず1行目の処理を追ってみる

1行目: i = i - ((i >>> 1) & 0x55555555);

パッと見、目を引くのが「0x55555555」ですが、これを2進数に直すと、こうなります

01010101010101010101010101010101

見ての通り、0と1が交互に現れています。i から 1シフトして 0と1が交互に出るものでAND演算し、それを元あった値から引いています。

これがどう「1」の数を数えるのに繋がるのか、さっぱりわかりません

全体を俯瞰して見る

1行目を見ても何も閃かなかったので、もう1度、全体的に見てみることにします。

とりあえず左に行番号を振ってみました。

1:   i = i - ((i >>> 1) & 0x55555555);
2:   i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
3:   i = (i + (i >>> 4)) & 0x0f0f0f0f;
4:   i = i + (i >>> 8);
5:   i = i + (i >>> 16);
6:   return i & 0x3f;

1行目の「0x55555555」以外にも、特徴的な値が見えます。

「0x33333333」「0x0f0f0f0f」、「0x3f」の3つです。

これらを2進数に直すとこんな風になります。

16進数2進数
0x5555555501010101010101010101010101010101
0x3333333300110011001100110011001100110011
0x0f0f0f0f00001111000011110000111100001111
0x3f00000000000000000000000000111111

上記のうち3つの値は、1ビット交互、2ビット交互、4ビット交互に「0」と「1」が並んでいます。

それから処理を見ると、1行目で1シフト、2行目で2シフト、3行目で4、4行目で8、5行目で16シフトして、最後に0x3f、つまり右6ビット(0~63)だけを有効としています。

この辺の値を並べて、斜め上から数分間じーっと見つめてもなかなか理解できず、頭を抱えながらトイレに行ってようやく閃きました(遅い)。分かってしまえばあまりに見たまんまの処理でした。ええ、自分は阿呆だと思いました。人生やり直そうかと思いました。

ところで、トイレってなんであんなに閃くんでしょうね?

さて、いかがでしょう。ここまで見て、この処理の意味、分かりましたでしょうか?

日頃からビットと戯れている硬派なプログラマの方々には「こんなの考えるまでもないじゃん」と言われそうですが、私と同類の堕落したプログラマは苦労するかもしれません。

ていうか苦労してください。自分だけが阿呆だと思いたくないんです。

以下、解説です。閃いた(ピコーン)方はお進みください。

解説

それではbitCountの処理が、1行目からそれぞれ、どういう意味なのかを解説してみます。

分かり易い言葉にしようとしたら、若干、意訳になってしまった気もしますがその辺はスルーしてください。

1:   i = i - ((i >>> 1) & 0x55555555);
2:   i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
3:   i = (i + (i >>> 4)) & 0x0f0f0f0f;
4:   i = i + (i >>> 8);
5:   i = i + (i >>> 16);
6:   return i & 0x3f;
1行目intの32ビットを2個ずつ16個に分割する。分割された内部のビット同士を足し合わせることで、16個のブロックがそれぞれいくつの「1」を持っているかを算出する。算出された値は、それぞれ16個のブロックに2ビットの2進数として保持される。
2行目1行目で出した16個の値の隣同士を足し合わせることで、16分割だった値を半分の8個にまとめる。この時、値は4ビットの2進数として各ブロックに保持される。
3行目同様に2行目で出した8個の値の隣同士を足し合わせて、4個の値にまとめる。この時、値は8ビットの2進数として各ブロックに保持される。
4行目3行目で出した4個の値のうち、1つ目と2つ目3つ目と4つ目を足し合わせ、2個の値にする
5行目4行目で算出された2つの値をさらに合算し、その値を一番右の8ビットの中に収める
6行目右6ビットを抜き出して、返す

というわけで、32個のビットのお隣さん同士を足し合わせて、16分割、8分割、4分割、2分割と、まとめていっているだけの話でした。

検算してみる(引数が-90000000の場合)

それでは、上の解説で書いたことが本当かどうか、検証してみましょう。

なぜ値に-90000000を選んだかというと、適当です。マイナスで大きい数字ならなんでも良かったんです。

-90000000の2進数表記はこんな感じです。

11111010101000101011010110000000

数えてみると、1は15個います。

これを使って1行ずつ、先ほど書いた解説が正しいか、検証してみましょう。 1行目 : i = i - ((i >>> 1) & 0x55555555);

/** 1行目を -90000000 で実行してみる */
int i = -90000000;
i = i - ((i >>> 1) & 0x55555555);

// 2進数表記
System.out.println( Integer.toBinaryString( i ) );
  // => 10100101010100010110010101000000

// 10進数表記
System.out.println( i );
  // => -1521392320

見ての通り、解は10100101010100010110010101000000になりました。

1行目の処理は「intの32ビットを2個ずつ16分割し、それぞれに存在する「1」の数を2ビットの2進数で保持する」という感じの処理です(この辺けっこう意訳ですが、うまく伝わる日本語が浮かばない……)。

というわけで、解を2ビットごとに16分割してみましょう。

上が処理前、下が処理後です。

旧 : 11 | 11 | 10 | 10 | 10 | 10 | 00 | 10 | 10 | 11 | 01 | 01 | 10 | 00 | 00 | 00
新 : 10 | 10 | 01 | 01 | 01 | 01 | 00 | 01 | 01 | 10 | 01 | 01 | 01 | 00 | 00 | 00

2進数で2は「10」になります。なので、上が「11」のように2つ「1」がある場合は、下が「10」になるのが正解です。

上が「00」であれば下も「00」、上が「10」か「01」であれば下は「01」になってくれればOKです。

というわけで、結果が合っているか、じーっと見て検証してみましょう。

なんかOKっぽいですね。 2行目 : i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

/** 2行目の処理を実行してみる。iには1行目の結果を入れる。 */
i = -1521392320;
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

// 2進数表記
System.out.println( Integer.toBinaryString( i ) );
  // => 01000010001000010011001000010000

// 10進数表記
System.out.println( i );
  // => 1109471760

解は01000010001000010011001000010000になりました。

1行目の結果の隣同士(という言い方は正確じゃないけど)を足した値が、2行目の処理の結果になっているはずです。

旧 : 10 | 10 | 01 | 01 | 01 | 01 | 00 | 01 | 01 | 10 | 01 | 01 | 01 | 00 | 00 | 00
新 :    0100 |    0010 |    0010 |    0001 |    0011 |    0010 |    0001 |    0000

1つ目のブロックでは、「10 + 10 = 0100」、2つ目のブロックでは「01 + 01 = 0010」になっています。

うん、合ってそうですね。 3行目 : i = (i + (i >>> 4)) & 0x0f0f0f0f;

若干ダレてきましたが、あと一息です。ここを超えれば後は単純なシフトだけ。

/** 3行目の処理を実行してみる。iには2行目の結果を入れる。 */
i = 1109471760;
i = (i + (i >>> 4)) & 0x0f0f0f0f;

// 2進数表記
System.out.println( Integer.toBinaryString( i ) );
  // => 00000110000000110000010100000001

// 10進数表記
System.out.println( i );
  // => 100861185

解は00000110000000110000010100000001になりました。3行目の処理は、2行目とほぼ同じ、隣同士の値を足し合わせています。

旧 : 0100 | 0010 | 0010 | 0001 | 0011 | 0010 | 0001 | 0000
新 :    00000110 |    00000011 |    00000101 |    00000001

1ブロック目、0100 + 0010 なので 0110 でOKです。
2ブロック目、0010 + 0001 なので 0011 でGOODです。
3ブロック目、0011 + 0010 なので 0101 でPERFECTです。
4ブロック目、0001 + 0000 なので 0001 以外あるわけねーだろ、このJ○pがって感じです。 すいません、疲れてきました……

とりあえず、OKのようです。

4行目 : i = i + (i >>> 8);

これは楽ですね。8シフトして足してるだけですから。

一応、ちゃんと説明してみます。せっかくここまで書いたので勢い的に。

/** 4行目の処理を実行してみる。iには3行目の結果を入れる。 */
i = 100861185;
i = i + (i >>> 8);

// 2進数表記
System.out.println( Integer.toBinaryString( i ) );
  // => 00000110000010010000100000000110

// 10進数表記
System.out.println( i );
  // => 101255174
旧 : 00000110 | 00000011 | 00000101 | 00000001
新 : 00000110 | 00001001 | 00001000 | 00000110

4行目の処理の目的は「左1~8ビットと左9~16ビットを、それから左17~24ビットと左25~32ビットを合算する」ことです。

1ブロック目と3ブロック目は後で切り捨てられる運命なので、シカトします。

「新の2ブロック目」は、「旧の1ブロック目」+「旧の2ブロック目」になっていて欲しいです。

「旧の1ブロック目 : 110 = 6」 + 「旧の2ブロック目 : 11 = 3」 = 「1001 = 9」になります。

ということで、「新の2ブロック目 = 1001」でOKです。

同様に「新の4ブロック目」は「旧の3」と「旧の4」が相手なので「5 + 1 = 6 = 110」になります。 5行目 : i = i + (i >>> 16);

4行目で1ブロック目と2ブロック目、3ブロック目と4ブロック目を合算しました。その値は今、2ブロック目と4ブロック目に入っています。

5行目では、その合算したもの同士をさらに合算します。

/** 5行目の処理を実行してみる。iには4行目の結果を入れる。 */
i = 101255174;
i = i + (i >>> 16);

// 2進数表記
System.out.println( Integer.toBinaryString( i ) );
  // => 00000110000010010000111000001111

// 10進数表記
System.out.println( i );
  // => 101256719
旧 : 00000110 | 00001001 | 00001000 | 00000110
新 : 00000110 | 00001001 | 00001110 | 00001111

さて、今回の計算は1個だけです。

旧の2ブロック目と4ブロック目を足した値が、新の4ブロック目になりやがります。

というわけで「1001」 + 「110」 = 「1111」 = 15

これが解になります。 6行目 : return i & 0x3f;

5行目で出た答えのうち、1~3ブロックは邪魔なので、余分なビットは削除します。

たぶん0xff(8ビット)でも結果は同じになると思いますが、intが32ビットしかないので0x3f(0~63)にしているのだと思います。

i = 101256719;
System.out.println( i & 0x3f );
  // => 15

というわけで、めでたく15という解にたどり着きました。

総評

わかってみれば単純な話でしたが、回答にたどり着くまで結構迷いました。精進しないとですね。

ていうか、自分のような下級プログラマが同じ処理作れって言われたら、迷わずこんな処理書いてんじゃないかなぁと思いました。

return Integer.toBinaryString( i ).replaceAll("0", "").length();

ダメダメじゃのぉ。