c++ - "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

Note: This answer (like the method itself) assumes signed integers are represented in two's complement form.

表达式x & -x 是一种快速 - 但不可否认的神秘 - 获取由最低设置位表示的值的方法x(当所有其他位都清除时)。有时这被称为位的权重，在数值上等于2的位位置次方(其中最低有效位是位置0)。

该方法依赖于以下事实:在两个 x< 的二进制 (2s-comp) 表示中只能设置一个单个位/code> 和 -x - 这实际上是 x 中最低有效设置位。

关于其工作原理，有一些很好的解释，并附有许多示例，请参见 Quora .

在您显示的 update 和 query 函数中，在 while 中增加/减少 m 的量因此，code> 循环根据(原始)m 中最低有效设置位的位置加权。

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