提问人：mbang 提问时间：8/19/2023 最后编辑：mbang 更新时间：8/19/2023 访问量：39
在 Fenwick 树/二进制索引树 （BIT） 中计算索引
Computing indices in Fenwick tree/Binary Indexed Tree (BIT)
问：
Fenwick 树数据结构需要一个成员函数。对于一个索引，必须计算几个索引 ， ， ， ...， .每个值都是将 i 最低有效非零位设置为 0 时产生的值。readidxreadidx[0]idx[1]idx[2]idx[last]idx[i]idx
例如，如果 = 13 = ...00001101，那么 = 13，= 12 = ...00001100，并且 = 8 = ...00001000.idxidx[1]idx[1]idx[2]
如果我们假设，就像大多数关于芬威克树的在线资源一样，有符号整数是用二的补码表示的，那么很容易计算。在这种情况下，.这条线的理由可以在这里找到：芬威克树。idx[i]idx[i+1] = idx[i] - (idx[i] & -idx[i]);
在 C++20 之前，使用按位是实现定义的，但现在似乎 C++20 需要使用 2 的补码。这就引出了以下问题：&
- 在 C++20 之前，说“不正确”的代码是否正确？
idx[i+1] = idx[i] - (idx[i] & -idx[i]); - 使用 C++20，现在正确吗？
idx[i+1] = idx[i] - (idx[i] & -idx[i]); - 如果（2）的答案是否定的，那么什么是有效的计算方法？如果未签名，我可以做吗？
idx[]idxidx[i+1] = idx[i] - (((~idx[i]) + 1) & idx[i])
答：
0赞
harold
8/19/2023
#1
如果未签名，我可以做吗？
idxidx[i+1] = idx[i] - (((~idx[i]) + 1) & idx[i])
事实上，如果是无符号的，你可以做，这样你就可以两全其美。idxidx[i+1] = idx[i] - (idx[i] & -idx[i]);
与流行的神话相反，否定无符号整数是明确定义的，而且它完全可以满足您在这里需要它执行的操作。
这一直很安全，而且总是很方便。没有必要重写否定。
从 C++ 规范：
一元 - 运算符的操作数应具有算术或无作用域枚举类型，结果 是对其操作数的否定。对整数或枚举操作数执行整数升级。这 无符号量的负数是通过从 2N 中减去其值来计算的，其中 n 是位数 在提升的操作数中。结果的类型是提升操作数的类型。
评论
0赞
mbang
8/19/2023
我不太了解微优化，但积分提升 + 减法不会比按位不 + 加法慢吗？这种猜测是基于这样的假设，即 CPU 架构可能没有针对整体提升进行优化。
1赞
harold
8/19/2023
@mbang这只是高层次的标准，并不代表实际的实现。当以任何相关 CPU 为目标时，否定无符号整数生成的代码与否定有符号整数的代码完全相同。例如，在现代 x64 上，整个事情（所有 3 个操作）很可能被编译为一条指令。（如果允许编译器使用现代指令）
评论