在编程中(数字和数字)是什么意思?
例如:
int get(int i) { int res = 0; while (i) { res = (res + tree[i]) % MOD; i -= ( (i) & (-i) ); } return res; }
树更新function:
void update(int i, int val) { while (i <= m) { tree[i] = (tree[i] + val) % MOD; i += ( (i) & (-i) ); } }
你能用( (i) & (-i) )
来解释他们在代码中做什么吗?
这两个函数是二叉树索引树(Fenwick树)数据结构的修改实现。
这里有两张图片来补充MikeCAT的答案,显示了我如何为不同的值更新variables。
“获取”function:
为了简化表示,假定函数中input的最大值为15。
数组t中的节点表示树数组中的树[t] 。
如果为i调用get函数,则返回的值是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答案中解释得非常好) “更新”function:
为了简化图片,假设树数组的最大长度是16。
更新function有点棘手。
它将val添加到树[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;
让我假设负值是用二进制补码表示的。 在这种情况下, -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)
来计算。
如果有人想要更通用的certificate,
假设x
的格式为a10 k (这里的意思是一些位串a,接着是1,接着是k个零)。
-x
是(根据定义)与〜x ~x + 1
,所以
- x&-x =(填写)
- a10 k & – (a10 k )=(否定的)
- a10 k &〜(a10 k )+ 1 =(应用倒置)
- a10 k &〜a01 k + 1 =(加1)
- a10 k &〜a10 k =(在某物与其相反之间)
- 0 w 10 k
所以我们只剩下那个我们认为存在的最右边的一个。
关于x
的forms的假设忽略了x = 0
的情况,在这种情况下结果显然仍然为零。