深入理解计算机系统：
整数表示及其运算相关公式的证明

第一部分 整数表示

定义1 二进制位级表示方式

二进制数的位级表示用行向量表示.

设行向量是一个有 位的二进制数的位级表示，则有：

示例：

数0xF74的位级表示为.

定义2 二进制位级表示为无符号数和补码

定义2.1 无符号数的表示

设函数表示位二进制转无符号数，有：

 .

示例：

数表示为无符号数为3960.

注：
函数是函数的逆运算，即：
.

定义2.2 补码的表示

设函数表示位二进制转补码，有：

 .

示例：

数表示为补码为-136.

注：
函数是函数的逆运算，即：
.

性质3 无符号数与补码的最值

性质3.1 无符号数的最小值

对于位的无符号数，其最小值为.

证明：

对于式，当且仅当 时，值最小，易知值为0.

性质3.2 无符号数的最大值

对于位的无符号数，其最大值为.

证明：

对于式，当且仅当 时，值最大，即.

性质3.3 补码的最小值

对于位的补码，其最小值为.

证明：

对于式，当且仅当 ，且时，值最小，即.

性质3.4 补码的最大值

对于位的补码，其最大值为.

证明：

对于式，当且仅当 ，且时，值最大，即.

性质4 无符号数与补码的转换

性质4.1 补码转无符号数

对于补码，设函数表示补码对应相同的位的二进制位级所表示的无符号数，有：

证明：

当时，.由式和得：

. .

因此有.
则.

当时，.由式和得：

. .

两式相减得：.
即：.
则.

性质4.2 无符号数转补码

对于补码，设函数表示无符号数对应相同的位的二进制位级所表示的补码，有：

证明：

当时，.由式和得：

. .

因此有.

则.

当时，.由式和得：

.
.

两式相减得：.
则.

性质5 无符号数与补码的位拓展

性质5.1 无符号数的零拓展

设有位的二进制数，拓展位个0后得二进制数.有.

证明：

由式得：

.
.

因为，所以.

则.

性质5.2 补码的符号拓展

设有位的二进制数，拓展位个最高位后得二进制数.有.

证明：

令.

由式得：

当时：..

因为，则：.

当时：.

.

因为，则：

.

由数学归纳法，对任意都有：

.

性质6 无符号数与补码的位截断

性质6.1 无符号数的截断

设，对于一个位的二进制数，截断其个最高位后得二进制数，有：

证明：

由式得：

. .

因为当时，，则.

因此

.

性质6.2 补码的截断

设，对于一个位的二进制数，截断其个最高位后得二进制数，有：

证明：

.

由式得：

.

因此有：.

第二部分 整数运算

定义&性质7 无符号数的加法

定义7.1 无符号数加法的定义

设有一个位的二进制数和一个位的二进制数.设.

设(有的位级),.将截断至有位的，对应的有.

则记为与的位无符号数加法.