CSAPP3 2.2 整型数据类型

| 分类 Programming  CSAPP3  | 标签 Programming  《深入理解计算机系统》 

整数的数据与算术操作术语如下:

符号 类型 含义
$B2T_w$ 函数 二进制转补码
$B2U_w$ 函数 二进制转无符号数
$U2B_w$ 函数 无符号数转二进制
$U2T_w$ 函数 无符号数转补码
$T2B_w$ 函数 补码转二进制
$T2U_w$ 函数 补码转无符号数
$TMin_w$ 常数 最小补码值
$TMax_w$ 常数 最大补码值
$UMax_w$ 常数 最大无符号数
$+^t_w$ 操作 补码加法
$+^u_w$ 操作 无符号数加法
$*^t_w$ 操作 补码乘法
$*^u_w$ 操作 | 无符号数乘法  
$-^t_w$ 操作 补码取反
$-^u_w$ 操作 | 无符号数取反  

整型数据类型

C 中的有符号整型的取值范围是不对称的,负数的范围比正数的范围大 1,如 char 的为 [-128, 127]。

但是 C 标准中定义的每种有符号整型的取值范围是对称的,如 char 的为 [-127,127]。

无符号整数的编码

假设有一种整型有 $w$ 位。我们将位向量写成 $\vec x$,表示整个向量,或者写成 $[x_{w-1},x_{w-2},\cdots,x_0]$,表示向量中的每一位。把 $\vec x$ 看成一个二进制表示的数,就获得了 该向量的无符号表示。

在这种编码中,每个位 $x_i$ 都取值 0 或 1,后一种取值意味着数值 $2^i$ 应为数字值的一部分。用一个函数 $B2U_w$ 来表示:

原理:无符号数编码的定义

对向量 $\vec x = [x_{w-1},x_{w-2},\cdots,x_0]$:

函数 $B2U_w$ 将一个长度为 $w$ 位的 0、1 串映射到非负整数。例如:

$B2U_4([0101]) = 0\bullet2^3 + 1\bullet2^2 + 0\bullet2^1 + 1\bullet2^0 = 5$

当用长度为 $2^i$ 的指向右侧箭头的条表示每个位的位置 $i$ 时,位向量对应的数值就等于所有值为 1 的位对应的条的长度之和。

无符号数数值计算

$w$ 位无符号数,最小值用向量 $[00\cdots0]$ 表示,即整数值 0,最大值用向量 $[11\cdots1]$ 表示,即整数值 $UMax_w := \sum_{i=0}^{w-1} = 2^w-1$。即取值区间是 $[0, 2^w-1]$。

函数 B2U 是一个双射,从而保证了无符号数编码的唯一性。

有符号整数编码

通常用补码 (two’s-complement) 形式编码。在这种定义中,将字的最高有效位解释为负权(negative weight)。

原理:有符号数编码的定义

对向量 $\vec x = [x_{w-1},x_{w-2},\cdots,x_0]$:

最高有效位 $x_{w-1}$ 称为符号位,它的权重为 $-2^{w-1}$。符号位设置为 1 时,表示值为负,为 0 时表示非负。

函数 $B2T_w$ 将一个长度为 $w$ 位的 0、1 串映射到有符号整数。例如:

$B2T_4([0101]) = -0\bullet2^3 + 1\bullet2^2 + 0\bullet2^1 + 1\bullet2^0 = 5$

$B2T_4([1101]) = -\bullet2^3 + 1\bullet2^2 + 0\bullet2^1 + 1\bullet2^0 = -3$

当用向左指的条表示符号位的负权重,则位向量对应的数值就等于可能的向左指的条和向右指的条架起来决定。

有符号数数值计算

$w$ 位有符号数,最小值用向量 $[10\cdots0]$ 表示,即整数值 $TMin_w := -2^{w-1}$,最大值用向量 $[01\cdots1]$ 表示,即整数值 $TMax_w := \sum_{i=0}^{w-2} = 2^{w-1}-1$。即取值区间是 $[-2^{w-1}, 2^{w-1}-1$。

函数 B2T 是一个双射,从而保证了有符号数编码的唯一性。

练习题 2.17 p82

补全下表:

$\vec x$ hex $\vec x$ bin $B2U_4(\vec x)$ $B2T_4(\vec x)$
0xE [1110] 8+4+2=14 -8+4+2=-2
0x0 [0000] 0 0
0x5 [0101] 4+1=5 4+1=5
0x8 [1000] 8 -8
0xD [1101] 8+4+1=13 -8+4+1=-3
0xF [1111] 8+4+2+1=15 -8+4+2+1=-1
上面可见,补码的范围是不对称的, $ TMin = TMax +1$,即 TMin 没有与之对应的正数。只所以不对称是因为一半的位模式(符号位为1)表示负数,另一半(符号位为0)表示非负(0 和正数)。

最大的无符号数刚好比补码的最大值的 2 倍大 1:UMax = 2TMax + 1。-1 和 UMax 有同样的位表示(全 1 的串)。而 0 在两种表示中都是全 0 的串。

C 标准没有要求用补码来表示有符号整数,但是几乎所有机器都是这么做的。<limits.h> 中定义了一组整型常量,如 INT_MAX, INT_MIN, UNIT_MAX 等,使用它们可提高可移植性。

固定长度的整型

C99 标准在 <stdint.h> 中引入了一组固定长度的整型,声明形如 intN_t 和 unitN_t,N 通常的值可为 8、16、32、64。可用来无歧义地定义整型。

这些整型同时对应有一组宏,用来定义每个 N 对应的整型的最小和最大值,如 INT32_MIN, INT32_MAX, UINT32_MAX 等。

对这些整型使用 printf 格式输出也需要宏,从而系统能将它扩展成正确的格式中。例如,变量 x 和 y 的类型是 int32_t 和 uint64_t,它们的 printf 输出代码应为 printf("x=%" PRId32, ",y=%" PRIu64 "\n", x, y);

编译为 64 位程序时,宏 PRId32 展开为 “d”,宏 PRIu64 展开为 “lu”。当 C 预处理器遇到仅用空格(或其它空白符)分隔的字符串常量序列时,会将它们串联起来作为一个字符串。

Java 标准对整型定义是很明确的,要求整数都是有符号数,用补码表示。

有符号数的其它表示方法

原码(Sign-Magnitude): 最高有效位是符号位,用来确定剩下的位应该取负权还是正权:

反码(Ones’ Complement): 除了最高有效位的权是 $-(2^{w-1}-1)$ 而不是 $-2^{w-1}$,它和补码一样。

这种表示方法中,对数字 0 都有两种不同的编码方式。它们把 $[00\cdots0]$ 都解释为 +0,而 -0 在原码中表示为 $[10\cdots0]$,在反码中为 $[11\cdots1]$。

原码编码在浮点数中有应用。

注意补码(Two’s complement) 和反码(Ones’ complement) 中的撇号位置不同。术语补码来源于:对于非负数 $x$,我们用 $2^w-x$ (这里只有一个 2)来计算 $-x$ 的 $w$ 位表示。而术语反码:用 $[11\cdots1]-x$ (这里有多个 1) 来计算 $-x$ 的反码表示。

补码表示时,绝对值相等的正数和负数的位模式

对于 32 位的有符号数 x = 12345 = 0x3039,mx = -x = -12345 = 0xcfc7

3 0 3 9

0011 0000 0011 1001

c f c 7

1100 1111 1100 0111

要根据正数的位模式,计算出其对应负数的位模式,可以将正数的位模式,取反加 1 得到。

例如正数 12345 = 0x3039, 取反加 1 后为 0xcfc7,刚好为 -12345。

练习题 2.18 p84

反汇编器生成的程序码都使用补码形式表示数值。将下面的 32 位补码表示的十六进制值转换为等值的十进制值。

A. 0x2e0 = 2256+1416= 736

B. -0x58 = -(5*16 + 8) = -88

C. 0x28 = 2*16 +8 = 40

D. -0x30 = -48

E. 0x78 = 7*16 + 8 = 120

F. 0x88 = 8*16 + 8 = 136

G. 0x1f8 = 1256 + 1516 + 8 = 504

H. 0xc0 = 12*16 = 192

I. -0x48 = -(4*16 + 8) = -72

有符号数和无符号数的转换

C 中强制类型转换的结果保持位表示不变,只改变解释这些位的方式。

如:

short int v = -12345; /* 0xcfc7 */
unsigned short uv = (unsigned short) v;  /* 0xcfc7 */
printf("v = %d, uv= %u\d", v, uv); /* v= -12345, uv=53191 */

更一般地,可用数学化表示如下: 给定 $0 \leq x \leq UMax_w$ 中的任一整数 $x$,函数 $T2B_w(x)$ 给出 $x$ 的唯一 $w$ 位无符号表示。相似地,当 $x$ 满足 $TMin_w \leq x \leq TMax_w$ 时,函数 $T2B_w(x)$ 会给出 $x$ 的唯一 $w$ 位补码表示。

则 $T2U_w(x) := B2U_w(T2B_w(x))$ 将补码表示的有符号数转为无符号数,输入区间为 $[TMin_w, TMax_w]$,输出区间为 $[0, UMax_w]$,输入和输出间有相同的位模式。类似地,$U2T_w(x) := B2T_w(U2B_w(x))$ 将无符号数转为有符号数。

无符号表示中的 $UMax$ 有着和补码表示的 -1 相同的位模式,同时 $1+UMax_w = 2^w$。

练习题 2.19 p87

利用 练习题 2.17 时填写的表格,补全下面 $T2U_4$ 的表格。

$x$ $T2U_4(x)$
-8 8
-3 13
-2 14
-1 15
0 0
5 5

可见,在对于负数,$T2U_w(x)$ 的值是 $2^w + x$。

当补码转换为无符号数时,

因此,$B2U_w(\vec x) = x_{w-1}2^w + B2T_w(\vec x)$, $T2U_w(x) = B2U_w(T2B_w(x)) = x + x_{w-1}2^w$。

故对于 $TMin_w \leq x \leq TMax_w 的 $x$ 有:

补码到无符号数

练习题 2.20

解答 2.19 题时,$w = 4$,故当负数时的转换只需加上 $2^4 = 16$ 即可。

类似地,对于无符号数转换为补码有:

对满足 $0 \leq u \leq UMax_w$ 的 $u$ 有:

$$U2T_w(u) = \begin{cases} u, u \leq TMax_w
u - 2^w, u > TMax_w
\end{cases}

无符号数到补码

总结下,对于 $[0, TMax_w]$ 内的 $x$,数字的无符号和补码表示都相同。而在这个范围外的数值,转换时需要加上或者减去 $2^w$。

C 中的有符号数和无符号数

C 实现中一般都用补码表示有符号数,并且常数等大多数数字默认都是有符号的,要创建一个无符号常量,要加后缀 ‘u’ 或 ‘U’,如 12345U,0x1A2Bu。

当执行一个运算时,如果它的一个运算数是有符号的,而另一个是无符号的,那么 C 会隐式地将有符号参数强制类型转换成无符号数(即升级规则 promotion rule),并假设这两个数是非负的,来运行这个运算。这种方法对算术运算影响不大,并对大小比较运算影响较大,会引起 Bug。例如,对于 -1 < 0U,由于 0U 是无符号的,-1 将隐式地转换为无符号数 $UMax_w$,从而使得运算表达式为假。

练习题 2.21 p89

假设在采用补码运算的 32 位机器上,补全下表:

表达式 类型
-2147483647-1 == 2147483648U 无符号数 左边 TMin 转为 UMax,故相等 1
-2147483647-1 < 2147483647 有符号数 | 左边 TMin 右边 TMax,1  
-2147483647-1U < 2147483647 无符号数 左边转为无符号数 $2^{31}$,大于右, 0
-2147483647-1 < -2147483647 有符号数 左边 TMin, 右边为 TMin+1,故 1
-2147483647-1U < -2147483647 无符号数 左边转为无符号数 $2^{31}$,右转为$2^{31}+1$,故 1

扩展数字的位表示

  1. 无符号数进行 0 扩展,即左边补上多个 0
  2. 补码数字进行符号扩展(用归纳法证明)

练习题 2.22 p91 因此,下面的 3 个位模式都是 -5 的补码表示。 A. [1011], B. [11011], C. [111011]。

无符号数和有符号数间转换的相对顺序能够影响程序的行为,如:

short sx = -12345; /* cfc7 */
unsigned uy = sx; /* 相当于 (unsigned) (int) sx */

printf("uy=%u:\t", uy);
show_bytes((byte_pointer) &uy, sizeof(unsigned));

上面在大端法机器上输出: uy=4294954951: ff ff cf c7

这表示当把 short 转为 unsigned 时,先改变大小,变成 int,再改变类型,成 unsigned。

练习题 2.23 p92

考虑下面 2 个 C 函数:

int fun1(unsigned word)
{
    return (int) ((word << 24) >> 24);
}

int fun2(unsigned word)
{
    return ((int) word << 24) >> 24);
}

假设在采用补码的 32 位机上运行,且有符号数是算术右移,无符号数是逻辑右移。填写下表。

w fun1(w) fun2(w)
0x00000076 (int)0x00000076=118 0x00000076=118
0x87654321 (int)0x00000021=33 0x00000021=33
0x000000C9 (int)0x000000C9=201 0xFFFFFFC9=-54
0xEDCBA987 (int)0x00000087=135 0xFFFFFF87=-120

fun1 中是在无符号数上右移地,是逻辑右移,fun2 中 word 先被转换成了有符号数 int,故是算术右移。

B. 函数 fun1 完成提取 word 的低 8 位的功能。fun2 完成提取后,还进行符号扩展。

数字截断

  1. 无符号数的截断直接截去高位多余的位,例如截断到 k 位,相当于进行了 mod $2^k$ 操作。
  2. 有符号数的截断也是直接截去高位多余的位,但是数值要进行补码数值的解析。

练习题 2.24 p93

假设将一个 4 位的数(0~F) 截断到 3 位数据(0~7)。填写下表。

原始值 hex 截断值 hex 原始值(无符号) 截断值(无符号) 原始值(补码) 截断值(补码)
0(0000) 0(000) 0(0000) 0(000) 0(0000) 0(000)
2(0010) 2(010) 2(0010) 2(010) 2(0010) 2(010)
9(1001) 1(001) 9(1001) 1(001) -7(1001) 1(001)
B(1011) 3(011) 11(1011) 3(011) -5(1011) 3(011)
F(1111) 7(111) 15(1111) 7(111) -1(1111) -1(111)

有关有符号数与无符号数的建议

当表达式中含有无符号数时,有符号数将自动隐式转换成无符号数,这将可能导致漏洞。避免这类错误的一种依法是绝不使用无符号数,实际上,除了 C 外很少有语言支持无符号整数。

只有当想把字仅仅看做是位的集合而没有任何数字意义时,无符号数才非常有用。

练习题 2.25 p94

下列代码试图计算数组 a 中所有元的各,当参数 length 等于 0 时,运行这段代码应该返回 0.0,但实际上会遇到内存错误。为什么?改进?

/* WARNING: This is buggy code */
float sum_elements(float a[], unsigned length)
{
    int i;
    float result = 0;
    
    for (i=0; i <= length -1; i++)
        result += a[i];
    return result;
}

由于 length 是无符号数, 故 length -1 在当 length 为 0 时将不是 -1 ,而是 UMax,故会遇到内存出错。

改进:将 length 声明改为 int 即可。或者判断改为 i<length

练习题 2.26 p94

要写一个函数用来判定一个字符串是否比另一个更长。前提是要用字符串库函数 strlen,它的声明为: size_t strlen(const char *s);,最开始你写的函数是这样的:

/* Determine whether string s is longer than string t */
/* WARNING: This function is buggy */
int strlonger(char *s, char *t) {
    return strlen(s) - strlen(t) > 0;
}

当进行一些测试时,似乎一切正确。进一步研究发现在头文件 stdio.h 中数据类型 size_t 是定义成 unsigned int 的。

A. 在当 s 的长度小于 t 的长度时,结果会不正确。

B. 这是因为,在 A 情况下,负数会隐式转成了正数。

C. 修改: 改为 return strlen(s) > strlen(t);

参考


上一篇     下一篇