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

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

如果 我 有签名类型,不可移植,因为 & 以表示的方式定义,但一元 - 我是说, += ,和 -= 是用价值来定义的如果 next version of the C++ standard mandates twos complement 但是,它将变得可移植,并且将执行与未签名情况相同的操作。

在无符号的情况下(和两个补码的情况下),很容易确认 i&-i 是2的幂(只有一位非零),并且与 我 (这也是 -i )中。因此:

• i -= i&-i; 清除的最低设置位 我 是的。
• i += i&-i; 递增(清除,但带进位到高位)的最低设置位 我 是的。

对于无符号类型,两个表达式都不会溢出对于签名类型, i -= i&-i 溢水取水 -我 什么时候 我 最初具有类型的最小值,并且 i += i&-i 溢出 += 什么时候 我 最初具有类型的最大值。

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

只要您提供的表达式在 二补 被用来表示负整数时,它是可移植的所以,第二个问题的答案是 是 依赖于负整数的表示。

为了回答您的第一个问题,因为算术表达式依赖于数据类型及其表示,我不认为只有一个算术表达式可以等效于表达式 I&I 是的。实际上,下面的代码在功能上等同于该表达式。(假设 i 属于类型 int )不过,请注意,我必须使用循环来生成相同的功能,而不仅仅是算法。

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

在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) 有一个有趣的性质是一点接近二次幂。
3. 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:有符号整数溢出显示未定义的行为。

以下是我根据其他答案所做的研究。钻头操作

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

主要用于穿越 Fenwick tree . 特别地, i&-i 如果有符号整数通过 two's complement 是的。像以前一样 pointed out by Peter Fenwick 在他最初的提议中,这不可移植到其他有符号整数表示。然而,

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

是(它也可以与 one's complement 和 signed magnitude 表示)并减少一个操作。

然而,似乎没有简单的可移植的方法来添加LSB。

i & -i 是获取整数最低有效位(LSB)的最简单方法 i 是的。
你可以读更多 here 是的。
A1:你可以阅读更多关于“数学等价物”的内容 here 是的。
A2:如果负整数表示不是通常的标准形式(即奇怪的大整数),那么 i&i 可能不是LSB。

最简单的方法是从数学等价性的角度考虑:

-i == (~i + 1)

所以 -i 反转值的位,然后添加 1 是的。其意义在于 0 一点点 i 变成 1个 S由 ~i 操作,所以添加 1个 价值导致所有这些低 一 要翻转到的位 零 同时携带 1个 向上直到它降落在 0个 比特,刚好和最低的位置一样 一 咬入 我 是的。

下面是数字6(0110,二进制)的一个例子:

i = 0110
~i == 1001
(~i + 1) == 1010
i & (~i + 1) == 0010

您可能需要手动执行每个操作几次,然后才能了解位中的模式。

下面是另外两个例子:

i = 1000
~i == 0111
(~i + 1) == 1000
i & (~i + 1) == 1000

i = 1100
~i == 0011
(~i + 1) == 0100
i & (~i + 1) == 0100

看看 + 1 导致一种“位级联”将一个带到第一个打开的位置 零 比特?

所以如果 (i & -i) 是一种提取最低 1个 bit,然后它将遵循 i += (i & -i) 和 i -= (i & -i) 是对一个值的最低1位进行加和减的尝试。

从一个值的最低1位减去它本身就可以把这个位归零。

把一个值的最低1位加到它本身并没有什么特殊的目的,它只是做它在锡上说的。

它应该是便携式的任何系统使用二的补充。