我+ =(i&-i)做什么？它是便携式的吗？

Question

我们i是一个有符号整数类型.考虑

i += (i&-i);
i -= (i&-i);

最初的地方i>0.

1. 这些怎么办？是否只有使用算术的等效代码？
2. 这取决于负整数的特定位表示吗？

来源:setter的在线编码拼图代码(没有任何解释/评论).

Answer 1

表达式i & -i基于Two's Complement用于表示负整数.简单地说,它返回一个值k,其中除了最低有效位之外的每个位都被设置为0,但该最低有效位保持其自己的值.(即1)

只要你提供的表达式在使用Two's Complement来表示负整数的系统中执行,它就是可移植的.所以,回答你的第二个问题是,表达式是依赖于负整数的表示.

要回答你的第一个问题,因为算术表达式依赖于数据类型及其表示,我认为没有一个单独的算术表达式等同于表达式i & -i.实质上,下面的代码在功能上与该表达式相同.(假设它i是类型的int)请注意,我必须使用循环来产生相同的功能,而不仅仅是算术.

int tmp = 0, k = 0;
while(tmp < 32)
{
    if(i & (1 << tmp))
    {
        k = i & (1 << tmp);
        break;
    }
    tmp++;
}
i += k;

Answer 2

在二进制补码架构上,带有4位有符号整数:

|  i |  bin | comp | -i | i&-i | dec |
+----+------+------+----+------+-----+
|  0 | 0000 | 0000 | -0 | 0000 |   0 |
|  1 | 0001 | 1111 | -1 | 0001 |   1 |
|  2 | 0010 | 1110 | -2 | 0010 |   2 |
|  3 | 0011 | 1101 | -3 | 0001 |   1 |
|  4 | 0100 | 1100 | -4 | 0100 |   4 |
|  5 | 0101 | 1011 | -5 | 0001 |   1 |
|  6 | 0110 | 1010 | -6 | 0010 |   2 |
|  7 | 0111 | 1001 | -7 | 0001 |   1 |
| -8 | 1000 | 1000 | -8 | 1000 |   8 |
| -7 | 1001 | 0111 |  7 | 0001 |   1 |
| -6 | 1010 | 0110 |  6 | 0010 |   2 |
| -5 | 1011 | 0101 |  5 | 0001 |   1 |
| -4 | 1100 | 0100 |  4 | 0100 |   4 |
| -3 | 1101 | 0011 |  3 | 0001 |   1 |
| -2 | 1110 | 0010 |  2 | 0010 |   2 |
| -1 | 1111 | 0001 |  1 | 0001 |   1 |

备注:

1. 你可以推测i&-i只有一个位设置(它是2的幂)并且它匹配最低有效位集i.
2. i + (i&-i) 有一个有趣的特性是更接近下一个2的幂.
3. i += (i&-i)设置最不重要的未设置位i.

所以,做i += (i&-i);最终会让你跳到下一个力量:

| i | i&-i | sum |     | i | i&-i | sum |
+---+------+-----+     +---+------+-----+
| 1 |    1 |   2 |     | 5 |    1 |   6 |
| 2 |    2 |   4 |     | 6 |    2 |  -8 |
| 4 |    4 |  -8 |     |-8 |   -8 |  UB |
|-8 |   -8 |  UB |

| i | i&-i | sum |     | i | i&-i | sum |
+---+------+-----+     +---+------+-----+
| 3 |    1 |   4 |     | 7 |    1 |  -8 |
| 4 |    4 |  -8 |     |-8 |   -8 |  UB |
|-8 |   -8 |  UB |

UB:有符号整数的溢出表现出未定义的行为.

Answer 3

这是我研究的其他答案提示的内容。位操作

i -= (i&-i);   // strips off the LSB (least-significant bit)
i += (i&-i);   // adds the LSB

主要用于遍历Fenwick 树。特别是，i&-i如果有符号整数通过二进制补码表示，则给出 LSB 。正如Peter Fenwick在他最初的提议中已经指出的那样，这不能移植到其他有符​​号整数表示。然而，

i &= i-1;      // strips off the LSB

是（它也适用于一个补码和有符号幅度表示）并且少了一个操作。

然而，似乎没有简单的便携式替代方案来添加 LSB。

Answer 4

如果i具有无符号类型，则表达式完全可移植且定义良好。

如果i有符号的类型，它是不可移植的，因为&在交涉，但一元来定义-，+=以及-=在价值观方面进行定义。但是，如果C++ 标准的下一版本强制要求二进制补码，它将变得可移植，并且将执行与未签名情况相同的事情。

在无符号情况下（和二进制补码情况），很容易确认它i&-i是 2 的幂（只有一位非零），并且与的最低位具有相同的值i（这也是最低位）一点-i）。所以：

• i -= i&-i;清除 的最低设置位i。
• i += i&-i;递增（清除，但进位到更高位） 的最低设置位i。

对于无符号类型，任何一个表达式都不会溢出。对于有符号的类型，i -= i&-i溢出服用-i时i最初有型的最小值，i += i&-i溢出的+=时候i开始有型的最大值。