x + = x＆-x是什么意思？

Question

我发现很多人使用x += x & -x，x -= x & -x解决了区间树问题。你能解释一下这个方程的意思吗？

void update(int m, int x) { 
    m++;
    while (m < N) {
        t[m] = t[m] + x;
        m += m & -m;
    }
}
int query(int m) { 
    int result= 0;
    m++;
    while (m > 0) {
        result = result + t[m];
        m -= m & -m;
    }
    return result;
}

Answer 1

注意：此答案（与方法本身一样）假定有符号整数以二进制补码形式表示。

该表达式x & -x是一种快速但公认的奥秘方法，用于获取最低位x（在清除所有其他位时）所表示的值。这有时被称为钻头的重量，在数值上等于2上升到钻头位置的幂（其中最低有效位是position 0）。

该方法依赖于以下事实：和- 的二进制（2s-comp）表示中只能设置一个位，而实际上这是中的最低有效位。x-xx

Quora上有许多示例，对它的工作原理进行了很好的解释。

在显示的update和query函数m中，while循环中的增加/减少量是根据（原始）中最低有效置位的位置加权的m。

请随时要求进一步的澄清和/或解释（但我不想复制/粘贴/解释我所链接的过多讨论）。

Answer 2

另一种解释方式可以如下：

让X是一个数字。那么X&-X代表the greatest power of 2 that divides X.

例子：

1. 让X = 10，然后X&-X就会给2。
2. 让X = 7，然后X&-X就会给1。
3. 让X = 4，然后X&-X就会给4。