c++ - (数字)和(-数字)的含义

Question

(number) & (-number) 是什么意思？我已经搜索过了，但无法找到含义

我想在 for 循环中使用 i & (-i)，例如:

for (i = 0; i <= n; i += i & (-i))

Answer 1

假设 2 的补码(或者 i 是无符号的)，-i 等于 ~i+1。

i & (~i + 1) 是提取 i 的最低设置位的技巧。

之所以有效，是因为 +1 实际上所做的是设置最低清除位，并清除所有低于该位的位。所以在 i 和 ~i+1 中设置的唯一位是 i 中的最低设置位(即，最低清除位在 ~i 中)。低于它的位在~i+1中清零，高于它的位在i和~i之间不相等。

除非循环体修改 i，否则在循环中使用它似乎很奇怪，因为 i = i & (-i) 是一个幂等操作:执行两次给出同样的结果。

[编辑:在其他地方的评论中，您指出代码实际上是 i += i & (-i)。因此，对于非零 i 的作用是清除 i 的最低一组设置位，并将下一个清除位设置在其之上，例如 101100 -> 110000 .对于i没有高于最低设置位的清除位(包括i = 0)，它设置i为0。所以如果它不是因为 i 从 0 开始，每个循环都会将 i 增加 至少 两倍与之前的循环非常相似，有时更多，直到最终它超过 n 并中断或转到 0 并永远循环。

编写这样的代码而不加注释通常是不可原谅的，但根据问题的领域可能这是一个“明显”的循环值序列。]