概要

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 );
  // => 4

lowestOneBitの処理

lowestOneBitの中の人は、こんな処理をしています。

/** lowestOneBitの中の人 */
public static int lowestOneBit(int i) {
  return i & -i;
}

「i & -i」

やっていることはこれだけ。非常に短い表記ですね。

「i & -i」をすることで、どうして一番右側の「1」だけが残るのでしょうか。

-i の説明

まず大前提として、-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演算した場合

単純に反転させただけの値(1の補数)をAND演算した場合にどうなるかを確認してみます。

簡単に書くと、「i」 と 「i を反転した値」を AND演算するということです。

例えば100(2進数では1100100)と、それを反転した値をANDで演算すると、こうなります。

00000000000000000000000001100100
11111111111111111111111110011011
--------------------------------
00000000000000000000000000000000

当然のように0になります。

反転してしまえば、同じ箇所に1が立つことはないので、AND演算で1が立つことはありません。

2の補数でAND演算した場合

では、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」になるということになります。