時々、利用可能な場面に遭遇します。

性質

整数演算「x & -x」は x の中で 1 のある最下位ビットだけを取得します。冗長なプログラムにすると

C

unsigned /* (x & -x) */
x_and_neg_x (unsigned x)
{
  unsigned y;

  for (y = 1; y; y <<= 1)
    if ((x & y))
      break;
  return y;
}

となります。ビット数は得られません。

最下位ビットから 0 の個数を数える X86 CPU の BSF 命令や ARM の CTZ 命令を C++20 の std::countr_zero とすると以下の処理に相当します。

C++20

y = 1 << std::countr_zero(x);  // x > 0 の場合

例: 4 ビット幅でのパターン表

	`x`	`-x`	`x & -x`
0	`0000`	`0000`	`0000`
1	`0001`	`1111`	`0001`
2	`0010`	`1110`	`0010`
3	`0011`	`1101`	`0001`
4	`0100`	`1100`	`0100`
5	`0101`	`1011`	`0001`
6	`0110`	`1010`	`0010`
7	`0111`	`1001`	`0001`
8	`1000`	`1000`	`1000`
9	`1001`	`0111`	`0001`
10	`1010`	`0110`	`0010`
11	`1011`	`0101`	`0001`
12	`1100`	`0100`	`0100`
13	`1101`	`0011`	`0001`
14	`1110`	`0010`	`0010`
15	`1111`	`0001`	`0001`

何故そうなるのか？

ここでは x を 1 以上とします。

b を最下位ビットから連続した 0 の個数とします。

x を奇数 (s = k * 2 + 1) の $2^b$ 倍とすると

+x = (+(k << 1) + 1) << b
-x = (-(k << 1) - 1) << b

x & -x = (s & -s) << b

と表せます。-s は

-s = (-k << 1) - 1
   = ((~k + 1) << 1) - 1   // -k = ~k + 1
   = (~k << 1) + (1 << 1) - 1
   = (~k << 1) + 1

だから

s & -s
  = (( k << 1) + 1) &
    ((~k << 1) + 1)
  = 1   // k & ~k = 0

x & -x
  = (s & -s) << b
  = 1 << b

となって、$2^b$ が得られます。

実例

内部の処理方法を選択可能なメルセンヌツイスタの作業中に参照していた
　　SIMD-oriented Fast Mersenne Twister
で置換可能な部分を見つけました。

SFMT.c/period_certification関数内

    const uint32_t parity[4] = {SFMT_PARITY1, SFMT_PARITY2,
                                SFMT_PARITY3, SFMT_PARITY4};

    /* 途中略 */

    /* check NG, and modification */
    for (i = 0; i < 4; i++) {
        work = 1;
        for (j = 0; j < 32; j++) {
            if ((work & parity[i]) != 0) {
                psfmt32[idxof(i)] ^= work;
                return;
            }
            work = work << 1;
        }
    }

ループ内ループを置換すると

    for (i = 0; i < 4; i++) {
        if (parity[i]) {
            psfmt32[idxof(i)] ^= parity[i] & -parity[i];
            break;
        }
    }

ループを展開すると

    /**/ if (SFMT_PARITY1) psfmt32[idxof(0)] ^= SFMT_PARITY1 & -SFMT_PARITY1;
    else if (SFMT_PARITY2) psfmt32[idxof(1)] ^= SFMT_PARITY2 & -SFMT_PARITY2;
    else if (SFMT_PARITY3) psfmt32[idxof(2)] ^= SFMT_PARITY3 & -SFMT_PARITY3;
    else if (SFMT_PARITY4) psfmt32[idxof(3)] ^= SFMT_PARITY4 & -SFMT_PARITY4;

確認はしてませんが、上記 3 つはコンパイラの最適化(定数式)で同じコードが出ると思います。何をやっているのか？という視点ではオリジナルの方が分かり易いでしょう。

前記事演算「n&(-n)」は以外と使える?

x86 では x == (x & -x) が !(x & (x - 1)) に最適化されてました。

Python 小道具：CountTrailingZeros (CTZ)