位编程中的(number & -number)是什么意思？

Question

例如：

int get(int i) {
    int res = 0;
    while (i) {
        res = (res + tree[i]) % MOD;
        i -= ( (i) & (-i) );
    }
    return res;
}

一个树更新函数：

void update(int i, int val) {
    while (i <= m) {
        tree[i] = (tree[i] + val) % MOD;
        i += ( (i) & (-i) );
    }
}

你能用 ( (i) & (-i) ) 解释一下它们在代码中的作用吗？

Answer 1

让我假设负值是用二进制补码表示的。在这种情况下，-i 可以计算为 (~i)+1（翻转位，然后加 1）。

例如，让我考虑i = 44。然后，在二进制中，

i           = 0000 0000 0000 0000 0000 0000 0010 1100
~i          = 1111 1111 1111 1111 1111 1111 1101 0011
-i = (~i)+1 = 1111 1111 1111 1111 1111 1111 1101 0100
(i) & (-i)  = 0000 0000 0000 0000 0000 0000 0000 0100

如你所见，可以使用(i) & (-i)计算最小位为1。

Answer 2

万一有人想要更一般的证明，

假设 x 的格式为 a10^k（这里的意思是，一些位串 a，后跟 1，再跟 k 个零）。

-x（根据定义）与 ~x + 1 相同，因此

x & -x = (填写)
a10^k & -(a10^k) = (否定定义)
a10^k & ~(a10^k) + 1 =（应用反转）
a10^k & ~a01^k + 1 = (加 1)
a10^k & ~a10^k = (AND between something and its inverse)
0^w10^k

所以我们只剩下我们假设存在的最右边的那个 1。

关于x形式的假设忽略了x = 0的情况，在这种情况下结果显然仍然是零。

Answer 3

这两个函数是 Binary index tree (Fenwick tree) 数据结构的修改实现。
这里有两张图片来补充 MikeCAT 的回答，显示 i 变量如何针对不同的值进行更新。

“获取”函数：
为了简化表示，假设函数输入的最大值为 15。

编号为t的节点代表树数组中的tree[t]。
如果您为 i 调用 get 函数，则返回值是 tree[i] 的总和加上所有 tree 数组元素，它们在数组中的索引是图片中 i 的父元素，零除外。
以下是一些示例：

get(15) = tree[15] + tree[14] + tree[12] + tree[8]
get(14) = tree[14] + tree[12] + tree[8]
get(13) = tree[13] + tree[12] + tree[8]
get(12) = tree[12] + tree[8]
get(11) = tree[11] + tree[10] + tree[8]
get(10) = tree[10] + tree[8]
get(9) = tree[9] + tree[8]
get(8) = tree[8]
get(7) = tree[7] + tree[6] + tree[4]
get(6) = tree[6] + tree[4]
get(5) = tree[5] + tree[4]
get(4) = tree[4]
get(3) = tree[3] + tree[2]
get(2) = tree[2]

上图中节点标签上的数字有属性每个节点的父节点是该节点标签减去最低有效值 1（在@MikeCAT 答案中解释得很好）
“更新”功能：
为简化图片，假设 tree 数组的最大长度为 16.
update 函数有点棘手。

它将 val 添加到 tree[i] 和所有 tree 元素，它们的索引是节点的父节点图片中带有标签i。

update(16, val) --> tree[16] += val;
update(15, val) --> tree[15] += val, tree[16] += val;
update(14, val) --> tree[14] += val, tree[16] += val;
update(13, val) --> tree[13] += val, tree[14] += val; tree[16] += val;
update(12, val) --> tree[12] += val, tree[16] += val;
update(11, val) --> tree[11] += val, tree[12] += val, tree[16] += val;
update(10, val) --> tree[10] += val, tree[12] += val, tree[16] += val;
update(9, val)  --> tree[9] += val, tree[10] += val, tree[12] += val, tree[16] += val;
update(8, val)  --> tree[8] += val, tree[16] += val;
update(7, val)  --> tree[7] += val, tree[8] += val, tree[16] += val;
update(6, val)  --> tree[6] += val, tree[8] += val, tree[16] += val;
update(5, val)  --> tree[5] += val, tree[6] += val, tree[8] += val, tree[16] += val;
update(4, val)  --> tree[4] += val, tree[8] += val, tree[16] += val;
update(3, val)  --> tree[3] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(2, val)  --> tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(1, val)  --> tree[1] += val, tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;

位编程中的(number & -number)是什么意思？

What does (number & -number) mean in bit programming?

c++

bit

bitwise-and

fenwick-tree