"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 (While implementing data structures like segment tree, binary indexed tree etc).

你能解释一下这个等式是什么意思吗?

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

推荐答案

注意:这个答案(就像方法本身一样)假设有符号整数用 two's 表示补充形式.

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

表达式 x &-x 是一种快速 - 但无可否认的神秘 - 获取由 x 中的 最低 设置位表示的值的方法(当所有其他位都清除).这有时被称为位的权重，在数字上等于 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<的二进制 (2s-comp) 表示中只能设置一个 单个位/code> 和 -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.

There are some good explanations of how this works, with many examples, here on Quora.

在您显示的 update 和 query 函数中，在 while 中增加/减少 m 的数量code> 循环因此根据(原始)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屋！