What 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

注：此答案（与方法本身一样）假定有符号整数以two's complement形式表示。

表达式x & -x是一种快速的方法-但公认的奥秘-获取由x中的[[最低设置位表示的值的方式（当所有其他位都清除时）。有时称为位的[[weight，在数值上等于2增大到位的位置的幂（其中最低有效位是位置0）。

该方法依赖于这样的事实，即只能在x和-x的二进制（2s-comp）表示形式中设置一个

单个位

]--这实际上是是x中的最低有效设置位。Quora上有很多示例，说明了它是如何工作的。

Answer 2