首页 文章

我=（i＆-i）做什么？它是便携式的吗？

提问于
浏览 次
16

设 i 是有符号整数类型 . 考虑

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

最初 i>0 .

  • 这些怎么办？是否只有使用算术的等效代码？

  • 这取决于负整数的特定位表示吗？

来源：setter的在线编码拼图代码（没有任何解释/评论） .

c++ integer bit-manipulation

6 回答

  • 4

    如果 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 ， += 当 i 最初具有该类型的最大值时 i += i&-i 溢出 .

    回复于
  • 0

    表达式 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;
    回复于
  • 4

    在二进制补码架构上，带有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 |

    备注：

    • 你可以推测 i&-i 只有一个位设置（它是2的幂）并且它匹配 i 的最低有效位 .

    • i + (i&-i) 有一个有趣的属性，更接近下一个2的幂 .

    • i += (i&-i) 设置 i 的最低有效未设置位 .

    所以，做 i += (i&-i); 最终会让你跳到下一个2的力量：

    | 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：有符号整数的溢出表现出未定义的行为 .

    回复于
  • 10

    以下是我通过其他答案提示的研究结果 . 比特操纵

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

    主要用于遍历Fenwick tree . 特别是，如果有符号整数通过two's complement表示，则 i&-i 给出LSB . 正如他原来的提案中已经pointed out by Peter Fenwick，这不能移植到其他有符号整数表示 . 然而，

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

    是（它也适用于one's complement和signed magnitude表示）并且只有少一个操作 .

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

    回复于
  • 9

    i & -i 是获取整数 i 的最低有效位（LSB）的最简单方法 .
    你可以阅读更多here .
    A1：你可以阅读更多关于'Mathematical Equivalents' here的信息 .
    A2：如果负整数表示不是通常的标准形式（即奇怪的大整数），那么 i & -i 可能不是LSB .

    回复于
  • 3

    最简单的思考方式是数学等价：

    -i == (~i + 1)

    所以 -i 反转该值的位，然后添加 1 . 这意味着 i 的所有低 i 位都被 ~i 操作变为 1 ，因此将 1 加到该值会导致所有低位 1 位向上移动 0 ，同时向上传送 1 直到它落入 0 会，这会恰好与 i 中最低 1 位的位置相同 .

    这是数字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 如何导致'bit cascade'携带一个到第一个打开的 0 位？

    因此，如果 (i & -i) 是提取最低 1 位的一种方法，那么 i += (i & -i) 和 i -= (i & -i) 的用例将尝试添加和减去值的最低1位 .

    从自身中减去一个值的最低1位用作将该位置零的方法 .

    将值的最低1位添加到自身似乎没有任何特殊目的，它只是在锡上执行它所说的 .

    它应该可以在任何使用二进制补码的系统上移植 .

    回复于

相关问题