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

符号なし整数の演算

 n & (-n)

で起きることは

入力	出力	下位の 0 の個数
????1	00001	0
???10	00010	1
??100	00100	2
?1000	01000	3

"?" の部分を 0 にすることです。

サンプルプログラム - C

unsigned int func1(unsigned int x)
{
    int b = 0;

    if (x == 0)
        return 0;
    while ((x & 1) == 0)
        b++, x >>= 1;
    return (1 << b);
}

unsigned int func2(unsigned int x)
{
    return (x & (-x));
}

void print_bin(unsigned int x)
{
    int i = 6;
    while (i-- > 0)
        putchar('0' + ((x >> i) & 1));
}

void test()
{
    int x;

    for (x = 0; x < 32; x++)
    {
        print_bin(x);
        putchar(':');
        putchar(' ');
        print_bin(func1(x));
        putchar(' ');
        print_bin(func2(x));
        putchar('\n');
    }
}

test() の実行結果

000000: 000000 000000
000001: 000001 000001
000010: 000010 000010
000011: 000001 000001
000100: 000100 000100
000101: 000001 000001
000110: 000010 000010
000111: 000001 000001
001000: 001000 001000
001001: 000001 000001
001010: 000010 000010
001011: 000001 000001
001100: 000100 000100
001101: 000001 000001
001110: 000010 000010
001111: 000001 000001
010000: 010000 010000
010001: 000001 000001
010010: 000010 000010
010011: 000001 000001
010100: 000100 000100
010101: 000001 000001
010110: 000010 000010
010111: 000001 000001
011000: 001000 001000
011001: 000001 000001
011010: 000010 000010
011011: 000001 000001
011100: 000100 000100
011101: 000001 000001
011110: 000010 000010
011111: 000001 000001

---

以下の記事で使用しています

• FFT: ビット列反転インデックス
• N==2^n 判定
• 0と1の組み合わせ表現一覧の順番と数値

---

また、あるプロセッサ(BSF/CTZ 相当がないリトルエンディアン)では、strlen を

1. SIMD 命令でバイト列を NULL 文字か否かで 0/1 の列に変換
2. "1" が一カ所以上出てくるまで検索
3. 「 n & (-n) 」の演算で上位ビットをクリア
4. BSR/CLZ 相当で NULL 文字の位置を特定

として高速化することができました。