整数演算： x & -x

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

# 性質

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

```c: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++:C++20
y = 1 << std::countr_zero(x);  // x > 0 の場合
```

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

|   | <code>x</code> | <code>-x</code> | <code>x &amp; -x</code> |
|--:|:-:|:-:|:-:|
| 0 | <code>0000</code> | <code>0000</code> | <code>0000</code> |
| 1 | <code>0001</code> | <code>1111</code> | <code>0001</code> |
| 2 | <code>0010</code> | <code>1110</code> | <code>0010</code> |
| 3 | <code>0011</code> | <code>1101</code> | <code>0001</code> |
| 4 | <code>0100</code> | <code>1100</code> | <code>0100</code> |
| 5 | <code>0101</code> | <code>1011</code> | <code>0001</code> |
| 6 | <code>0110</code> | <code>1010</code> | <code>0010</code> |
| 7 | <code>0111</code> | <code>1001</code> | <code>0001</code> |
| 8 | <code>1000</code> | <code>1000</code> | <code>1000</code> |
| 9 | <code>1001</code> | <code>0111</code> | <code>0001</code> |
| 10 | <code>1010</code> | <code>0110</code> | <code>0010</code> |
| 11 | <code>1011</code> | <code>0101</code> | <code>0001</code> |
| 12 | <code>1100</code> | <code>0100</code> | <code>0100</code> |
| 13 | <code>1101</code> | <code>0011</code> | <code>0001</code> |
| 14 | <code>1110</code> | <code>0010</code> | <code>0010</code> |
| 15 | <code>1111</code> | <code>0001</code> | <code>0001</code> |


## 何故そうなるのか？

ここでは <code>x</code> を <code>1</code> 以上とします。

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

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

```C:
+x = (+(k << 1) + 1) << b
-x = (-(k << 1) - 1) << b

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

と表せます。<code>-s</code> は

```C:
-s = (-k << 1) - 1
   = ((~k + 1) << 1) - 1   // -k = ~k + 1
   = (~k << 1) + (1 << 1) - 1
   = (~k << 1) + 1
```

だから

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

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

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


## 実例

[内部の処理方法を選択可能なメルセンヌツイスタ](https://qiita.com/ikiuo/items/113f4a3657d1e74e5b17) の作業中に参照していた
　　SIMD-oriented Fast Mersenne Twister
で置換可能な部分を見つけました。

```C: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;
        }
    }
```

```C:ループ内ループを置換すると
    for (i = 0; i < 4; i++) {
        if (parity[i]) {
            psfmt32[idxof(i)] ^= parity[i] & -parity[i];
            break;
        }
    }
```

```C:ループを展開すると
    /**/ 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)」は以外と使える?](https://qiita.com/ikiuo/items/41b2df2e1db35a7b2bab)

- x86 では <code>x == (x &amp; -x)</code> が <code>!(x &amp; (x - 1))</code> に最適化されてました。

Python [小道具：CountTrailingZeros (CTZ)](https://qiita.com/ikiuo/items/2ea6f3c4fb3b40f328dc)