我在算法的源代码中找到了这个循环。我认为有关问题的细节在这里不相关,因为这只是解决方案的很小一部分。

    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树或类似的东西。

07-24 09:45
查看更多