`(i & (i + 1)) - 1` 是什么意思？ （在芬威克树）
What does `(i & (i + 1)) - 1` mean? (in Fenwick Trees)
在学习 Fenwick Trees 时，我发现了这个实现：
来源：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 只是设置了下一个未设置的位。
但是，(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
如果 i 的位模式类似于 ...0111，则 i+1 的位模式将是 ...1000。因此，i & (i+1) 表示 i - (2^{number of trailing ones} - 1) 并将所有尾随 1 转换为零。例如，如果 i 是偶数，则 i & (i+1) 将等于 i。另一方面，-1 表示将所有尾随零转换为 1（包括上一步的所有尾随零转换为零）并将连续的 1 转换为零。
通过为下一步执行 -1，i & (i+1) 会将 i 减少 i 的前一个值的 2^{number of trailing 1's}。
这是什么原因？它有助于表明在最坏的情况下，求累积和的时间复杂度将是O(log n)。
要找到此计算背后的原因，您需要关注每个节点 i 将负责计算索引 i 到 (i - (1 << r)) + 1。并且“r 表示索引 i 中设置的最后 1 位”。要找到索引 i 对应的总和，我们需要对从 0 到 i 的所有相关值求和。请注意，由于指定的 属性，我们不需要对所有索引求和。因此，我们需要对索引 i、i - (1 << r)、... 等等求和。
在学习 Fenwick Trees 时，我发现了这个实现：
来源：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 只是设置了下一个未设置的位。
但是，(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
如果 i 的位模式类似于 ...0111，则 i+1 的位模式将是 ...1000。因此，i & (i+1) 表示 i - (2^{number of trailing ones} - 1) 并将所有尾随 1 转换为零。例如，如果 i 是偶数，则 i & (i+1) 将等于 i。另一方面，-1 表示将所有尾随零转换为 1（包括上一步的所有尾随零转换为零）并将连续的 1 转换为零。
通过为下一步执行 -1，i & (i+1) 会将 i 减少 i 的前一个值的 2^{number of trailing 1's}。
这是什么原因？它有助于表明在最坏的情况下，求累积和的时间复杂度将是O(log n)。
要找到此计算背后的原因，您需要关注每个节点 i 将负责计算索引 i 到 (i - (1 << r)) + 1。并且“r 表示索引 i 中设置的最后 1 位”。要找到索引 i 对应的总和，我们需要对从 0 到 i 的所有相关值求和。请注意，由于指定的 属性，我们不需要对所有索引求和。因此，我们需要对索引 i、i - (1 << r)、... 等等求和。