有符号类型的位移运算符

7

我正在尝试理解有符号和无符号类型的按位运算符行为。根据ISO/IEC文档,以下是我的理解。

左移运算符

  • E1 << E2 的结果是将E1左移E2个位。

  • 因为左移而空出来的位将会用0填充。

  • 对于E1作为有符号非负数:如果该值可以被结果类型表示,则E1 << E2的结果是E1乘以2的E2次方。

  • Q1:那么对于有符号负数呢?

  • Q2:在以下情况中,“模减”的意思是什么?“如果E1具有无符号类型,则结果的值为E1× 2E2,对结果类型可表示的最大值进行模运算加一”。

右移运算符

  • E1 >> E2的结果是将E1右移E2个位。

  • 对于E1作为有符号非负数/无符号数:结果的值是E1除以2的E2次方的整数部分。

  • Q3:对于有符号负整数,我看到一些书定义空出来的位置将用1填充。请详细说明有符号负整数上使用右移运算符的作用。

4个回答

8

Q1:左移运算符在有符号整数类型的负值上的行为是未定义的,当有符号整数类型的正值结果 E1 * 2^E2 在类型中不可表示时,其行为也是未定义的。

这在标准(n1570草案)的第6.5.7节第4和5段中明确提到:

4 E1 << E2 的结果是将 E1 左移 E2 位;空出的位用零填充。如果 E1 具有无符号类型,则结果的值为 E1 × 2^E2 ,对结果类型中可表示的最大值再加一取模后的余数。如果 E1 具有有符号类型且非负值,E1 × 2^E2 可以在结果类型中表示,则该值为结果;否则,其行为是未定义的。

Q2:对于无符号整数类型中可表示的最大值加一取模的缩减意味着左移时左侧被移出的位被简单地丢弃。

从数学上讲,如果无符号类型的最大值为 2^n - 1(它总是这种形式),则将 E1 左移 E2 位的结果是范围在 0 到 2^n - 1 的值 V,使得差异为:

(E1 * 2^E2 - V)

可以被 2^n 整除,也就是说,它是当你将 E1 * 2^E2 除以 2^n 后得到的余数。

Q3: 对于有符号整型的负值进行右移操作的结果是由各个实现定义的。最常见的行为(至少在二进制补码机器上)是算术右移,即结果是商向下取整(朝负无穷方向)。

5 右移运算符 E1 >> E2 的结果是将 E1 向右移动 E2 位。如果 E1 是无符号类型或者 E1 是有符号类型且值非负,则结果的值为 E1 / 2^E2 的整数部分。如果 E1 是有符号类型且值为负数,则结果的值是由各个实现定义的。


在 C89 中,对于所有具有比有符号类型多一个数据位的无符号类型的平台以及无符号类型中的最高有效位处于有符号类型的符号位所在位置的情况下,左移负值的行为被明确定义; 在其他平台上的行为实际上是实现定义的。C99 将其更改为未定义行为,但原理并未提及此更改,更不用说提供任何理由。因此,是否定义取决于是否使用了面向常见目标的 C89 兼容平台。 - supercat

5
  • 关于问题1:
    如果E1是负数,那么行为是未定义的。

  • 关于问题2:
    无符号算术运算是“循环”的,即它会绕回到UINT_MAX + 1变成0。就好像每个计算都是在模UINT_MAX+1下进行的。另一种思考方式是,超出左边界的多余位被简单地舍弃了。

  • 关于问题3:
    如果E1是负数,结果是由实现定义的。也就是说,它取决于你的机器/编译器/选项,但是行为必须在某个地方有文档记录(“定义”),通常是编译器手册。两种流行的选择是用1填充左侧的传入位(算术移位)或用0填充(逻辑移位)。


2
如果你真的想了解位移操作符,请看这些简单的规则:
1)在左移中,E1 << E2,右侧所有空位将被填充为零,无论数字是有符号还是无符号,都会移入零。
2)在右移中,E1 >> E2,左侧所有空位,如果数字是正数,则为0,如果数字是负数,则为1。请记住,无符号数字永远不会是负数。另外,一些实现可能在某些机器上即使数字为负数也用0填充它们,因此永远不要依赖这个。
所有其他情况都可以通过这两个简单的规则来解释。 现在,如果您想知道移位后结果的值,请手动在纸上写出数字的位表示,并使用这两个规则在空位输入位。然后您就能更好地理解位移操作的工作原理。
For example lets take int i = 7;
i<<2
now i = 0000 0000 0000 0000 0000 0000 0000 0111
perform two left shits according to rule 1 would be:

0000 0000 0000 0000 0000 0000 0001 1100

这将给它一个值为28(E1 * 2E2 = 7 * 2 * 2 = 28),与比特模式所表示的相同。

现在让我解释一下“减少模数”的事情,如果你在移位一个大数字,那么左边的位将会丢失,“减少模数”补偿了这一点。因此,如果你的结果值大于数据类型可以容纳的最大值,左边的位将会丢失,然后: result = (E1*2*E2) % (最大值 + 1)。

对于其他各种情况,只需记住上述规则,你就会很好 :)


你忘记了另一个规则:因为一些处理器有一个“向左移动N位”的指令,但只适用于N小于字长的值,如果要移动的位数超过左操作数的大小,则一切皆有可能。 - supercat

1
Q2: "value reduced modulo X" 在数学中意味着 "value mod X",在 C 语言中可以写成 "value % X"。这部分只是解释了整数溢出的工作原理。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接