c++ - for循环中使用的位操作

Question

我在一个算法的源代码中发现了这个循环。我认为有关问题的详细信息在这里无关紧要，因为这只是解决方案的一小部分。

    void update(int i, int value, int array[], int n) {
        for(; i < n; i += ~i & (i + 1)) {
            array[i] += value;
        }
}

我真的不明白 for 循环中发生了什么，这是某种技巧吗？我发现了一种名为 Fenwick trees 的类似树，但它们看起来与我这里的有点不同。

知道这个循环是什么意思吗？

另外，发现这个:

“位 Hack #9。隔离最右边的 0 位。

y = ~x & (x+1)"

Answer 1

你是对的:bit-hack ~i & (i + 1)应该评估为一个整数，它是所有二进制 0的，除了与 i 最右边的零位对应的那个，设置为二进制 1 .

所以在 for 的每一遍结束时循环，它将此值添加到自身。由于i中的相应位为零，这具有设置它的效果，而不影响 i 中的任何其他位.这将严格增加 i 的值每次通过，直到i溢出(或变为 -1 ，如果您以 i<0 开始)。在上下文中，您可能期望它是用 i>=0 调用的，那i < n在你的索引离开 array 之前设置终止循环.

整个函数应该具有遍历 i 原始值的零位的效果从最不重要到最重要，一个一个地设置它们，并递增 array 的相应元素。 .

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