時々、利用可能な場面に遭遇します。
性質
整数演算「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 つはコンパイラの最適化(定数式)で同じコードが出ると思います。何をやっているのか？という視点ではオリジナルの方が分かり易いでしょう。
- x86 では
x == (x & -x)が!(x & (x - 1))に最適化されてました。
Python 小道具：CountTrailingZeros (CTZ)