x + = x&是什么?-x是什么意思? [英] What does x += x & -x mean?

问题描述

我发现许多人都使用 x + = x&-x ， x-= x&-x 解决间隔树问题.您能解释一下该方程的含义吗?

I found that many people use x += x & -x, x -= x & -x to solve the interval tree problem. Can you explain what that equation means?

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;
}

推荐答案

注意:此答案(如方法本身一样)假定有符号整数在中表示补码形式.

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

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

The expression x & -x is a quick - but admittedly arcane - way of getting the value represented by the lowest set bit in x (when all other bits are clear). This is sometimes known as the weight of the bit, and is numerically equal to 2 raised to the power of the bit's position (where the least significant bit is position 0).

该方法依赖于以下事实:在两个 x 和 -x -这实际上是 x 中的最低有效设置位.

The method relies on the fact that there can only be a single bit that is set in the binary (2s-comp) representations of both x and -x - and this will actually be the least significant set bit in x.

在 Quora .

在显示的 update 和 query 函数中，在的同时增加/减少 m 的量 m 中最低有效位的位置，对循环加权.

In the update and query functions you show, the amount by which to increase/decrease m in the while loops is thus weighted according to the position of the least significant set bit in the (original) m.

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

Feel free to ask for further clarification and/or explanation (but I don't wish to copy/paste or paraphrase too much of the discussion I've linked).

这篇关于x + = x&是什么?-x是什么意思?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！