c++ - (number & -number) 在位编程中是什么意思？

Question

例如:

int get(int i) {
    int res = 0;
    while (i) {
        res = (res + tree[i]) % MOD;
        i -= ( (i) & (-i) );
    }
    return res;
}

树更新函数:

void update(int i, int val) {
    while (i <= m) {
        tree[i] = (tree[i] + val) % MOD;
        i += ( (i) & (-i) );
    }
}

你能解释一下他们在代码中使用 ( (i) & (-i) ) 做了什么吗？

Answer 1

让我假设负值使用二进制补码表示。 在这种情况下，-i 可以计算为 (~i)+1(翻转位，然后加 1)。

例如，让我考虑 i = 44。然后，在二进制中，

i           = 0000 0000 0000 0000 0000 0000 0010 1100
~i          = 1111 1111 1111 1111 1111 1111 1101 0011
-i = (~i)+1 = 1111 1111 1111 1111 1111 1111 1101 0100
(i) & (-i)  = 0000 0000 0000 0000 0000 0000 0000 0100

如您所见，可以使用 (i) & (-i) 计算出最小位 1。