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

你是对的：bit-hack ~i & (i + 1) 应该计算为一个整数，它是所有二进制 0 的整数，除了对应于 [=12= 最右边的零位的那个], 设置为二进制 1.

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

之前终止循环

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

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

Answer 2

update函数迭代并设置i的0位从最左边的零到最右边的零，并将value添加到第i个元素array.

for 循环检查 i 是否小于 n，如果是，~i & (i + 1) 将是一个除最右边的位外所有二进制 0 的整数（即 1）。然后 array[i] += value 将 value 添加到迭代自身。

将 i 设置为 8 并进行迭代可能会让您明白一些事情。

Answer 3

假设从右到左，x 中有一些 1 位、一个 0 位，然后是更多位。

如果加上x+1，则右边所有的1都变为0，0变为1，其余不变。例如 xxxx011 + 1 = xxxx100。

在 ~x 中，你有相同数量的 0 位、一个 1 位和其他位的倒数。按位 and 产生 0 位，一个 1 位，并且由于其余位与它们的否定相加，因此这些位为 0。

所以 ~x & (x + 1) 的结果是一个有一个 1 位的数字，其中 x 最右边的位为零。

如果你把它加到 x 上，你就把最右边的 0 变成了 1。所以如果你重复这样做，你就会把 x 中的 0 位从右到左变成 1。

for循环中使用的位操作

Bit operation used in a for loop

c++

algorithm

for-loop

bit-manipulation