程序员视角教科书中的无符号/有符号算术问题 [英] Unsigned / Signed Arithmetic Problems from A Programmer's Perspective Textbook
问题描述
int x = random();
int y = random();
unsigned ux = (unsigned) x;
unsigned uy = (unsigned) y;
对于以下每个C表达式，您将指示是否或 不是表达式总是产生1.如果表达式总是产生1，请描述基本的数学原理.否则，给出一个使它产生0的参数示例.
For each of the following C expressions, you are to indicate whether or not the expression always yields 1. If it always yields 1, describe the underlying mathematical principles. Otherwise, give an example of arguments that make it yield 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.
For these questions, I got that only A could yield 0 while the rest always yielded 1.
我知道这可能是错误的，我不是在寻找直接的答案，而是希望获得一些有关如何解决这些问题的常识/建议.
I know this is probably wrong and I'm not looking for direct answers but I was hoping to get some general knowledge / advice on how to approach these problems.
我有一个非常糟糕的教授，我一直在尝试在线查找资源，但我真的不知道从哪里开始或寻找什么.我知道无符号/二进制补码算术和位移的基础，但是我不知道如何应用它来找到这些问题的对策.
I have a really bad professor and I've been trying to find resources online but I don't really know where to start or what to look for. I know the basics of unsigned / two's complement arithmetic and bit-shifting but I don't know how to apply it to find counter cases for these problems.
推荐答案
C编程语言未指定整数有符号数溢出的结果；如果x是带负号的，它都没有定义x << n.
The C programming language does not specify the result of an overflow of integral signed quantities; neither it defines x << n if x is signed and negative.
但是，不考虑符号而执行算术运算并不少见，将有符号和无符号n位整数都视为二进制补码系统中以2 ^ n为模的数字.
However, it is not uncommon that arithmetic operations are performed regardless of the sign, considering both signed and unsigned n-bit integers to be numbers modulo 2^n represented in the two's complement system.
这是您锻炼时必须假设的，否则几乎没有任何意义.
This must be assumed for your exercise, which is almost meaningless otherwise.
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不同，这与打印有关，但与内部无关
计算(只要仅使用+，-，*和按位运算).
Between signed and unsigned, only the representative system of the integers
modulo 2^n differ, which is relevant for printing, but not for internal
computations (as long as only +, -, * and bitwise operations are used).
对于有符号整数，正负整数的第一位设置为 1.除打印外，有符号和无符号之间的转换都是无关紧要的.
For signed integers, exactly the negative integers have the first bit set to 1. Casts between signed and unsigned are irrelevant except for printing.
我坚持认为，这是您的练习所必需的，但是C编程语言 没有说明我的大部分主张.
I insist, this is assumed for your exercises, but the C programming language does not specifies most of my claims.
A. (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)
是真的:假定从有符号转换为无符号，不改变内部
表示，并且假设运算符忽略了
整数.换句话说，x-y == -(y-x)保留放置转换的位置.
True: the cast from signed to unsigned is assumed not to change the internal
representation, and operators are assumed to ignore the signedness of
integers. In other words, x-y == -(y-x) holds wherever casts are put.
E. ((x >> 2) << 2) <= x
是:
x
== (x >> 2) << 2 + two_last_significant_bits_of_x
== (x >> 2) << 2 + positive
>= (x >> 2) << 2
带符号的32位整数的示例:
Examples with signed 32-bit integers:
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
这篇关于程序员视角教科书中的无符号/有符号算术问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
