for循环的increment语句中的奇数位运算符

Question

鉴于此for循环:

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

它应该是什么意思？该声明的i += i & -i成就是什么？

Answer 1

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

2s互补签名系统(当我签名时)
i & -i有点黑客,快速找到应该添加到给定数字的数字,使其尾随位0(这就是为什么BIT的性能是对数).当你在2s互补系统中否定一个数字时,你会得到一个带有逆模式位的数字1.当你添加时1,所有不太重要的位都会开始反转,只要它们是1(0原始数字).0遇到的第一位(1原来的i)会变成1.

当你和两者i和-i只有那个位(最低有效1位)将保持置位并且所有较小有效(右)位将是,zero并且更高有效位将是inverse原始数.

安定将生成一个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

无符号(当我是无符号时)
它甚至可以用于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上使用.

这里有实例

同样的非混淆版本将是:

/* 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;
}

编辑
从这个答案添加:

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

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

这是有效的,因为+1实际上做的是设置最低的清除位,并清除低于该位的所有位.因此,在i和~i + 1中设置的唯一位是来自i的最低设置位(即,~i中的最低清除位).低于该比特的比特在~i + 1中是清楚的,并且高于该比特的比特在i和~i之间是不相等的.