(数字和 - 数字)在位编程中意味着什么？

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

如您所见,1的最小位可以使用(i) & (-i).

Answer 2

如果有人想要更一般的证据,

假设x格式为a10 ^k(这里的意思是,一些位串a,后跟一个1,后跟k个零).

-x是(根据定义)同样的事情~x + 1,所以

• x&-x =(填写)
• a10 ^k& - (a10 ^k)=(否定的定义)
• a10 ^k&〜(a10 ^k)+ 1 =(应用反转)
• a10 ^k&~01 ^k + 1 =(加1)
• a10 ^k&〜a10 ^k =(在某事物之间和它的反向之间)
• 0 ^w 10 ^k

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

关于x叶子形式的假设x = 0,在这种情况下,结果显然仍为零.

Answer 3

这两个函数是二进制索引树(Fenwick树)数据结构的修改实现.
这是两张图片,以补充MikeCAT的答案,显示我如何变量更新不同的值.

"get"函数:
假设函数输入的最大值为15,表示简单.

其上具有数字t的节点表示树阵列中的树[t].
如果你为i调用get函数,则返回值是tree [i]的总和加上所有树数组元素的总和,它们在数组中的索引是图片中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答案中解释得非常好) "更新"功能:
为简化图片,我们假设该的最大长度树阵列为16
的更新功能是有点麻烦.

它将val添加到tree [i]和所有树元素,它们的索引是图片中带有标签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;