Java には Integer.highestOneBit( i ) という、intの「1」のビットのうち、最も左にいる「1」だけ残して残りは全て「0」にする機能があります。
例えば「100」は2進数で「1100100」。
見ての通り、2進数表記内の最も左側の「1」は右から7つ目にいます。なので、Integer.highestOneBit( 100 ) と書くと 2進数で「1000000」、つまり10進数で「64」 が返ってきます。
/** 実行例 */
// 100のhighestOneBitの結果
int cnt = Integer.highestOneBit( 100 );
System.out.println( cnt );
// => 64highestOneBitの中の人は、こんな処理をしています。
/** highestOneBitの中の人 */
public static int highestOneBit(int i) {
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}えーと、1, 2, 4, 8, 16とシフトしたヤツをOR除算して足して……
よく分かりませんが、なんかいろいろやってるようです
パッと見て、どうしてこれで左側のビットが取れるのか分からなかったので、堅実に1行目の意味を理解することからトライしてみようと思います。
1行目の処理はこんな感じです。
「i |= (i >> 1);」
とりあえず、この処理に100を投入してみます。
/** highestOneBitの1行目の処理を、100で試してみる */
int i = 100;
// 100の2進数表記
System.out.println( Integer.toBinaryString( i ) );
// => 1100100
/** 例の処理実行 */
i |= (i >> 1);
// 処理結果の2進数表記
System.out.println( Integer.toBinaryString( i ) );
// => 1110110
// 処理結果の10進数表記
System.out.println( i );
// => 1182進数的にはこんな変化がありました。
旧 : 1100100 新 : 1110110
1ビットシフトしてOR演算しているので、「今まで1があった箇所の、1つ右の0が、1になっている」ことが分かります。
では、次に閃くターンです。閃く時は電球を持ってピコーンと言いましょう。
とりあえず1行目でやったことを意識しながら、もう1度全体を見てみます。
1: i |= (i >> 1);
2: i |= (i >> 2);
3: i |= (i >> 4);
4: i |= (i >> 8);
5: i |= (i >> 16);
6: return i - (i >>> 1);2～5行目は、1行目と同じでシフトする距離だけ違う処理をしています。
1シフトして |= すると、1の隣の0が1になってました。
ということは、2シフトすると1の2個隣の0が1になってそうな気がします。
実際に試してみましょう。
/** 結果が分かり易い数字として、72を選択 */
int i = 72;
// 72の2進数表記
System.out.println( Integer.toBinaryString( i ) );
// => 1001000
// 例の処理（2シフト版）
i |= (i >> 2);
// 処理結果の2進数表記
System.out.println( Integer.toBinaryString( i ) );
// => 1011010はい、こうなりました。
旧 : 1001000 新 : 1011010
想像した通り、旧で1だった場所の2個隣が1になってますね。
このロジックを4, 8, 16と繰り返し、最後に1シフトした値をiから引いています。
さて、ここまでの説明で、なぜこのようなロジックで、一番左側の1のビット以外を0にすることが出来るか、分かったでしょうか。
ほぼ答えまで書いてしまっているような気もしますが、残りの解説は解等編で。
1: i |= (i >> 1);
2: i |= (i >> 2);
3: i |= (i >> 4);
4: i |= (i >> 8);
5: i |= (i >> 16);
6: return i - (i >>> 1);1から5行目を見てください。
1行目、1シフトした値をOR演算することで、今、1が立っている値の1つ右を1に変えています。
2行目、2シフトした値をOR演算することで、今、1が立っている値の2つ右を1に変えています。
これを4, 8, 16と繰り返すとどうなるでしょう。
これをすると、最初に「1」が立っていた場所の1～32ビット右まで全部が「1」で埋まります。
例えば最初が「100100」だったら「111111」になります。
実際に試してみましょう。
/** 適当な数値で、1～5行目の処理を通してみる */
int i = 1565746;
// i の2進数表記
System.out.println( Integer.toBinaryString( i ) );
// => 101111110010000110010
// 当該処理
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
// 実行結果の2進数表記
System.out.println( Integer.toBinaryString( i ));
// => 111111111111111111111旧 : 101111110010000110010 新 : 111111111111111111111というわけで、見事に全部1になっています。 で、6行目で、1だけ右にシフトして、i から引いています。 1だけ右にシフトすると、今まで一番左にあった1が、1つ右にズレます。 上の例で行くと、こんな感じになります。
シフト前 : 111111111111111111111 シフト後 : 011111111111111111111
6行目の処理では、シフト前からシフト後を引いているので、こんな風になります。
111111111111111111111 011111111111111111111 --------------------- 100000000000000000000
という感じで、一番左側の「1」だけが抜き出せました。めでたし、めでたし。
シフトするだけでいろんな値が取れるもんなんだなぁと感心しました。
私のようなダメプログラマが作った場合は、きっとこんな感じの処理になるのではないかと。
public static int highestOneBit( int i ) throws Exception {
int signum = Integer.signum( i );
if( signum == 0 )
return 0;
i = Math.abs( i );
for( int j = 0; j <= 32; j++ ) {
double d = Math.pow( 2, j );
if( d <= i && Math.pow( 2, j + 1 ) > i ) {
return (int) d * signum;
}
}
throw new UnexpectedException("Wakaranai Shiranai");
}あっ、Integer.MIN_VALUEの時に落ちる・・・・