Java には Integer.lowestOneBit( i ) という、intの1のビットのうち、最も右にいる「1」だけ残して残りは全て「0」にする機能があります。
例えば「100」は2進数で「1100100」。
見ての通り、2進数表記内の最も右側の「1」は右から3つ目にいます。なので、Integer.lowestOneBit( 100 ) と書くと 2進数で「100」、つまり10進数で「4」 が返ってきます。
/** 実行例 */
// 100のlowestOneBitの結果
int cnt = Integer.lowestOneBit( 100 );
System.out.println( cnt );
// => 4lowestOneBitの中の人は、こんな処理をしています。
/** lowestOneBitの中の人 */
public static int lowestOneBit(int i) {
return i & -i;
}「i & -i」
やっていることはこれだけ。非常に短い表記ですね。
「i & -i」をすることで、どうして一番右側の「1」だけが残るのでしょうか。
まず大前提として、-i は i を反転して 1を足した値になります。
例として「1」と「-1」について見てみます。
整数「1」の2進数表記はこうなります。
00000000000000000000000000000001
これの「0」と「1」を反転すると、こうなります。
11111111111111111111111111111110
これに1を足すと、こうなります。
11111111111111111111111111111111
上記の値は、「-1」の2進数表記です。
/** -1 を2進数で表示するコード */
System.out.println( Integer.toBinaryString( -1 ) );
// => 11111111111111111111111111111111というわけで、ビットを反転して1を足すと、-iになります。
単純に反転させただけの値（1の補数）をAND演算した場合にどうなるかを確認してみます。
簡単に書くと、「i」 と 「i を反転した値」を AND演算するということです。
例えば100（2進数では1100100）と、それを反転した値をANDで演算すると、こうなります。
00000000000000000000000001100100 11111111111111111111111110011011 -------------------------------- 00000000000000000000000000000000
当然のように0になります。
反転してしまえば、同じ箇所に1が立つことはないので、AND演算で1が立つことはありません。
では、2の補数（反転した値に1を加えたもの、つまり -i）をAND演算するとどうなるでしょうか。
先ほどと同じように100を例として取ります。
「 i を反転した値 」 + 「 1 」 + 「 i 」ということになるので、こんな風に書けます。
11111111111111111111111110011011 00000000000000000000000000000001 00000000000000000000000001100100 -------------------------------- 00000000000000000000000000000100
2進数に対して1を足すと、一番右に「1」が立っていれば、1つ左に繰り上がります。繰り上がった先にまた「1」が経っていれば、また1つ左に繰り上がります。
つまり、2進数で1を足すと、一番右側にある0が1になり、それより右側の値は全て0になります。
この、一番右側の「0」は、反転する前の値はもちろん「1」です。そこに「1」があったから、反転して「0」になったわけなので。
つまり、反転後に一番右側にあった「0」は反転前に一番右側にあった「1」と同じ場所にいることになります。
今、この一番右側にある「1」に対してのみ、双方の値が「1」になりました。
ということは、この両値をAND演算すれば、一番右側にある「1」のみが「1」で、それ以外は「0」になるということになります。