ビット操作については「http://www.nminoru.jp/~nminoru/programming/bitcount.html」も参考にされたい。
・最右の1であるビットを0にする
「x & (x - 1)」は最右の1であるビットを0にする。
xが00011000の場合はx-1は00010111になるので、「x & (x - 1) = 00011000 & 00010111 = 00010000」
・2^n-1の形式であるかどうかを調べる
「x & (x + 1)」は符号なし整数に置いて、2^n-1の形式であるかどうかを調べることができる。
2^n-1の形式とは「00111111」や「00000111」といった、2^nの形から1を引いたものである。
この計算の結果が0であれば「2^n-1の形式である」といえる。
・最右の1であるビットの部分だけを1にする
「x & (-x)」は最右の1であるビットだけを残す。
xが00100110だとすると、-xは11011010である。
ここで上記の計算をすると「x & (-x) = 00100110 & 11011010 = 00000010」である。
・最右の0であるビットの部分だけを1にする
「~x & (x + 1)」は最右にある0であるビットだけを1にする。
xが10100111である場合は、「~x & (x + 1) = 01011000 & 10101000 = 00001000」。
・最右にある0の並びを1の並びにしたものを返す
「~x & (x - 1)」「~(x | -x)」「(x & -x) - 1」の３つがある
・最右の1であるビットとそれに続く0の並びの部分を1にしたものを返す
「x xor (x - 1)」
・最右の連続した1のビットをオフにする
「*1 + 1) & x」
*1:x | (x - 1
