for循环中使用的位操作

Question

我在算法的源代码中发现了这个循环.我认为有关这些问题的详细信息与此无关,因为这只是解决方案的一小部分.

    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)"

Answer 1

你是对的：位黑客~i & (i + 1)应该评估为一个整数，该整数都是二进制的0，除了与最右边的零位相对应的整数之外i，该整数被设置为二进制1。

因此，在循环的每次传递结束时for，它都会将该值添加到自身中。由于 中的相应位i为零，因此具有设置它的效果，而不影响 中的任何其他位i。i这将严格增加每次传递的值，直到i溢出（或者变成-1，如果您从 开始i<0）。在上下文中，您可能会期望它是用 调用的i>=0，并且i < n设置为在索引离开 之前终止循环array。

整个函数应该具有以下效果：i从最低有效位到最高有效位迭代原始值的零位，将它们一一设置，并递增 的相应元素array。

芬威克树是一种有效积累和查询统计数据的巧妙方法；正如你所说，他们的更新循环看起来有点像这样，并且通常使用类似的位黑客。肯定有多种方法可以完成这种位摆弄，因此您的源代码肯定有可能正在更新 Fenwick 树或类似的东西。