c - Unsigned/Signed Arthmetic Problems from A Programmer's Perspective 教科书

Question

int x = random();
int y = random();

unsigned ux = (unsigned) x;
unsigned uy = (unsigned) y;

对于以下每个 C 表达式，您要指出是否或not the expression always yields 1. 如果它总是产生 1，请描述基本的数学原理。否则，给出一个使它产生 0 的参数的例子。

A. (x<y) == (-x>-y) 
B. ((x+y)<<4) + y-x == 17*y+15*x
C. ~x+~y+1 == ~(x+y)
D. (ux-uy) == -(unsigned)(y-x)
E. ((x >> 2) << 2) <= x

---

对于这些问题，我得到只有 A 可以产生 0，而其余的总是产生 1。

我知道这可能是错误的，我不是在寻找直接的答案，但我希望获得一些关于如何解决这些问题的一般知识/建议。

我有一个非常糟糕的教授，我一直在尝试在线查找资源，但我真的不知道从哪里开始或寻找什么。我知道无符号/二进制补码算术和位移的基础知识，但我不知道如何应用它来找到这些问题的反例。

Answer 1

C 编程语言没有指定整数有符号量溢出的结果；它既没有定义 x << n如果x有符号且为负。

但是，考虑到带符号和无符号的 n 位整数都是以二进制补码系统表示的以 2^n 为模的数字，执行算术运算而不考虑符号的情况并不少见。

您的练习必须假定这一点，否则几乎没有意义。

8 位整数示例:

unsigned domain: (0..127), ( 128..255)
signed   domain: (0..127), (-128..-1)

以二进制表示:

unsigned domain: 00000000..01111111 and 10000000..11111111
signed   domain: 00000000..01111111 and 10000000..11111111

有符号和无符号之间，只有整数的代表系统模 2^n 不同，与打印相关，但与内部无关计算(只要只使用 + 、 - 、 * 和按位运算)。

对于有符号整数，恰好负整数的第一位设置为1. signed 和 unsigned 之间的转换是无关紧要的，除了打印。

我坚持，这是你练习的假设，但是 C 编程语言没有具体说明我的大部分主张。

一个。 (x<y) == (-x>-y)

被 x == INT_MIN 反驳, y == INT_MIN + 1 ,因为INT_MIN == -INT_MIN .

B. ((x+y)<<4) + y-x == 17*y+15*x

正确:

   ((x+y) << 4     ) + y-x
== ((x+y) * 0x10000) + y-x
== ((x+y) * 16     ) + y-x
== 17 * y + 15 * x

C. ~x+~y+1 == ~(x+y)

正确:

x + ~x + 1 == 0
~x + 1 == -x
~(x+y) + 1 == -(x+y)
~(x+y) + 1 == -x + -y
~(x+y) + 1 == ~x + 1 + ~y + 1
~(x+y) == ~x + ~y + 1

D. ((unsigned)x-(unsigned)y) == -(unsigned)(y-x)

True:假设从 signed 到 unsigned 的转换不会改变内部表示，并且运算符被假定为忽略的符号整数。换句话说，x-y == -(y-x)在任何地方都适用。

E. ((x >> 2) << 2) <= x

正确:

   x 
== (x >> 2) << 2 + two_last_significant_bits_of_x
== (x >> 2) << 2 + positive
>= (x >> 2) << 2

带符号的 32 位整数示例:

x              == 5
x              == 00000000000000000000000000000101 in base2
x >> 2         == 00000000000000000000000000000001 in base2
(x >> 2) << 2  == 00000000000000000000000000000100 in base2
(x >> 2) << 2  == 4

x              == -5
x              == 11111111111111111111111111111011 in base2
x >> 2         == 11111111111111111111111111111110 in base2
(x >> 2) << 2  == 11111111111111111111111111111000 in base2
(x >> 2) << 2  == -8