计算 Fenwick 树/二元索引树 (BIT) 中的索引

Question

Fenwick 树数据结构需要成员函数

read

。对于索引

idx

，

read

必须计算多个索引

idx[0]

、

idx[1]

、

idx[2]

、...、

idx[last]

。每个

idx[i]

都是将

idx

的 i 个最低有效非零位设置为 0 时得到的值。

例如，如果

idx

= 13 = ...00001101，则

idx[1]

= 13、

idx[1]

= 12 = ...00001100 和

idx[2]

= 8 = ...00001000。

如果我们像芬威克树上的大多数在线资源一样假设有符号整数使用二进制补码表示，则

idx[i]

很容易计算。在这种情况下，

idx[i+1] = idx[i] - (idx[i] & -idx[i]);

。这条线的理由可以在这里找到：Fenwick trees。

在 C++20 之前，使用按位

&

是实现定义的，但 C++20 现在需要使用二进制补码。这导致了以下问题：

1. 在 C++20 之前，

   idx[i+1] = idx[i] - (idx[i] & -idx[i]);

   是“不正确”的代码，这样说是否正确？
2. 使用 C++20，

   idx[i+1] = idx[i] - (idx[i] & -idx[i]);

   现在正确吗？
3. 如果（2）的答案是“否”，那么计算

   idx[]

   的有效方法是什么？如果

   idx

   没有签名，我可以直接做

   idx[i+1] = idx[i] - (((~idx[i]) + 1) & idx[i])

   吗？

Answer 1

如果

idx

未签名，我可以直接做

idx[i+1] = idx[i] - (((~idx[i]) + 1) & idx[i])

吗？

事实上，如果

idx

未签名，您可以直接执行

idx[i+1] = idx[i] - (idx[i] & -idx[i]);

，这样您就可以两全其美。

与流行的神话相反，对无符号整数取反是明确定义的，而且它完全符合您在这里需要做的事情。

这一直是安全的，而且总是方便的。无需重写否定。

来自 C++ 规范：

一元运算符的操作数应为算术或无范围枚举类型，且结果应为 是其操作数的否定。整数提升是对整数或枚举操作数执行的。这 无符号量的负数是通过从 2ⁿ 中减去其值来计算的，其中 n 是位数 在提升的操作数中。结果的类型是提升的操作数的类型。