c++ - for循环的增量语句中的奇数位运算符

Question

鉴于此 for 循环:

for(++i; i < MAX_N; i += i & -i)

它应该是什么意思？ i += i & -i 语句完成了什么？

Answer 1

在二叉索引树(或 BIT)实现中经常观察到此循环，这对于在对数时间内更新范围或点以及查询范围或点很有用。此循环有助于根据索引中的设置位选择合适的存储桶。有关更多详细信息，请考虑从其他来源阅读有关 BIT 的信息。在下面的文章中，我将展示这个循环如何帮助根据最低有效设置位找到合适的存储桶。

2s互补签名系统(当i签名时)
i & -i快速找到应该添加到给定数字以使其尾随位为 0 的数字有点技巧(这就是为什么 BIT 的性能是对数的)。当你否定 中的一个数字时，2s complementary system ，你会得到一个添加了反码位的数字1给它。当您添加 1 ，只要它们是 1，所有不太重要的位都会开始反转(原编号为 0)。第一 0遇到的位(原始 i 中的 1)将变为 1 .

当你和双方i和 -i ，只有该位(最不重要的 1 位)将保持设置，所有次要(右)位将是 zero更重要的位将是 inverse原号码。

Anding 将产生 2 的幂添加到数字 i 时的数字将清除最低有效设置位。 (根据BIT的要求)

例如:

i = 28
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+
                      *
-i
+---+---+---+---+---+---+---+---+
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+
  I   I   I   I   I   S   Z   Z
Z = Zero
I = Inverted
S = Same
* = least significant set bit

i & -i
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Adding
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
                      x
x = cleared now

无符号(当 i 无符号时)
它甚至适用于 1s complementary system或任何其他表示系统，只要 i是 unsigned原因如下:

-i将采用 2^{sizeof(unsigned int) * CHAR_BITS} - i 的值。因此，最低有效设置位的所有位将保持 zero ，最低有效位也将保持为零，但之后的所有位将因进位而反转。

例如:

i = 28
     +---+---+---+---+---+---+---+---+
     | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
                           *
-i
   0   1   1   1   1   1   <--- Carry bits
     +---+---+---+---+---+---+---+---+
   1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
     +---+---+---+---+---+---+---+---+
   - | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
   ----------------------------------------
     +---+---+---+---+---+---+---+---+
     | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
       I   I   I   I   I   S   Z   Z
Z = Zero
I = Inverted
S = Same
* = least significant set bit

i & -i
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Adding
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
                      x
x = cleared now

无需 bithack 的实现

您也可以使用i += (int)(1U << __builtin_ctz((unsigned)i))在 gcc 上。

Live example here

相同的非混淆版本是:

/* Finds smallest power of 2 that can reset the least significant set bit on adding */
int convert(int i) /* I purposely kept i signed as this works for both */
{
    int t = 1, d;
    for(; /* ever */ ;) {
        d = t + i; /* Try this value of t */
        if(d & t) t *= 2;  /* bit at mask t was 0, try next */
        else break; /* Found */
    }
    return t;
}

编辑
从 this answer 添加:

Assuming 2's complement (or that i is unsigned), -i is equal to ~i+1.

i & (~i + 1) is a trick to extract the lowest set bit of i.

It works because what +1 actually does is to set the lowest clear bit, and clear all bits lower than that. So the only bit that is set in both i and ~i+1 is the lowest set bit from i (that is, the lowest clear bit in ~i). The bits lower than that are clear in ~i+1, and the bits higher than that are non-equal between i and ~i.