我在算法的源代码中找到了这个循环。我认为有关问题的细节在这里不相关,因为这只是解决方案的很小一部分。
void update(int i, int value, int array[], int n) {
for(; i < n; i += ~i & (i + 1)) {
array[i] += value;
}
}
我真的不明白for循环会发生什么,这是某种技巧吗?我发现了一些类似的名为Fenwick的树,但它们看起来与我在这里有些不同。
有什么想法这个循环意味着什么?
另外,发现了这个:
“Bit Hack#9。隔离最右边的0位。
y =〜x&(x + 1)
”
最佳答案
您是正确的:bit-hack ~i & (i + 1)
的计算结果应为所有二进制0
的整数,但与i
的最右边零位相对应的整数除外,该整数被设置为binary 1
。
因此,在for
循环的每次通过结束时,它都会将此值添加到自身中。由于i
中的相应位为零,因此可以对其进行设置,而不会影响i
中的任何其他位。这将严格增加每次通过时i
的值,直到i
溢出(或者,如果您以-1
开头,则变为i<0
)。在上下文中,您可能希望它用i>=0
调用,并且设置i < n
会在您的索引脱离array
之前终止循环。
总体功能应具有以下作用:将i
的原始值的零位从最低有效位循环到最高有效位,将它们一一设置,并递增array
的相应元素。
Fenwick树是一种有效地累积和查询统计信息的聪明方法。如您所说,它们的更新循环看起来像这样,并且通常使用类似的位hack。当然,有多种方法可以完成这种比特摆弄,因此您的源代码肯定有可能更新Fenwick树或类似的东西。