`(i & (i + 1)) - 1`在Fenwick树中是什么意思？

Question

在学习树状数组时，我发现了这个实现：

源代码：https://algorithmist.com/wiki/Fenwick_tree

class Fenwick_Tree_Sum
{
    vector<int> tree;
    Fenwick_Tree_Sum(const vector<int>& Arg)//Arg is our array on which we are going to work
    {
        tree.resize(Arg.size());
        
        for(int i = 0 ; i<tree.size(); i++)
            increase(i, Arg[i]);
        
    }

    // Increases value of i-th element by ''delta''.
    void increase(int i, int delta)
    {
        for (; i < (int)tree.size(); i |= i + 1)
            tree[i] += delta;
    }

    // Returns sum of elements with indexes left..right, inclusive; (zero-based);
    int getsum(int left, int right)
    {
        return sum(right) - sum(left-1); //when left equals 0 the function hopefully returns 0
    }

    int sum(int ind)
    {
        int sum = 0;
        while (ind>=0)
        {
            sum += tree[ind];
            ind &= ind + 1;
            ind--;
        }
        return sum;
    }
};

我能看到代码中有 i |= i + 1 和 ind &= ind + 1; ind--。

我知道 i |= i + 1 只是将下一个未设置的位设为1。

但是，(i & (i + 1)) - 1 到底是做什么用的呢？

这里是一些示例：

-------------------------------------
         i        | (i & (i + 1)) - 1
-------------------------------------
  0 - 0000000000  |  -1 - 1111111111
  1 - 0000000001  |  -1 - 1111111111
  2 - 0000000010  |   1 - 0000000001
  3 - 0000000011  |  -1 - 1111111111
  4 - 0000000100  |   3 - 0000000011
  5 - 0000000101  |   3 - 0000000011
  6 - 0000000110  |   5 - 0000000101
  7 - 0000000111  |  -1 - 1111111111
  8 - 0000001000  |   7 - 0000000111
  9 - 0000001001  |   7 - 0000000111
 10 - 0000001010  |   9 - 0000001001
 11 - 0000001011  |   7 - 0000000111
 12 - 0000001100  |  11 - 0000001011
 13 - 0000001101  |  11 - 0000001011
 14 - 0000001110  |  13 - 0000001101
 15 - 0000001111  |  -1 - 1111111111
 16 - 0000010000  |  15 - 0000001111
 17 - 0000010001  |  15 - 0000001111
 18 - 0000010010  |  17 - 0000010001
 19 - 0000010011  |  15 - 0000001111
 20 - 0000010100  |  19 - 0000010011
 21 - 0000010101  |  19 - 0000010011
 22 - 0000010110  |  21 - 0000010101
 23 - 0000010111  |  15 - 0000001111
 24 - 0000011000  |  23 - 0000010111
 25 - 0000011001  |  23 - 0000010111
 26 - 0000011010  |  25 - 0000011001
 27 - 0000011011  |  23 - 0000010111
 28 - 0000011100  |  27 - 0000011011
 29 - 0000011101  |  27 - 0000011011
 30 - 0000011110  |  29 - 0000011101

- StackExchange123

---

尝试对几个不同的 i 值计算这个表达式，并自行查看。提示：用二进制显示 i 和结果。 - n. m.

如果你将 i 保持在8位，你可以使用 std::cout << std::bitset<8>(i) << "\t" << std::bitset<8>((i & (i + 1)) - 1) << "\n"; 来实现。换句话说，它会做一些奇怪的事情。 - Bathsheba

我猜它的目的是测试是否所有位都被设置（除了前导零），在这种情况下返回-1。换句话说：i & (i + 1) == 0。 - Andreas H.

从上下文来看，它似乎沿着树向上导航，当你遇到-1时停止。因此，您可以绘制一个图表，其中每个结果= -1作为根，每个其他数字作为新节点，其父节点是结果。 - Rup

@Rup 不，意图是前往负责求和的下一个更小的索引。 - n. m.

Answer 1

如果i的位模式为...0111，那么i+1的位模式就是...1000。因此，i & (i+1)的意思是将i减去2^{末尾连续1的个数} - 1并将所有末尾的1变为零。例如，如果i是偶数，则i & (i+1)将等于i。另一方面，-1的意思是将所有末尾的零变为1（包括上一步中所有末尾的1变为零），并将连续的1变为零。

通过对下一个步骤进行-1操作，i & (i+1)将会使i减少前一个i值中2^{末尾1的个数}的数量。

这样做的原因是什么？它能够证明在最坏情况下找到累积和的时间复杂度将是O(log n)。

要找出这种计算背后的原因，您需要关注每个节点i将负责计算从索引i到(i - (1 << r)) + 1的范围。其中，“r表示在索引i中设置的最后一个1位”。要找到与索引i对应的总和，我们需要对0到i之间的所有相关值进行求和。请注意，由于指定的属性，我们不需要对所有索引进行求和。因此，我们需要对索引i、i - (1 << r)等进行求和。

- OmG

---

谢谢！我现在明白它应该做什么了，但是在附加代码的上下文中，这意味着什么？ - StackExchange123

@StackExchange123 请查看已更新的答案（最后一段）。 - OmG

当你说“leading”时，我认为你在整个过程中指的是“trailing”。此外，“i-2 ^ [前导1的数量]”有一个偏差；i & (i + 1) 是 i - 2^{尾随1的数量} + 1。 - Richard Smith