SCAPP-02-信息的表示和处理

CSAPP 第二章

信息的表示和处理

三种数字表示:

  • 无符号(unsigned)编码:大于或等于零的数字

  • 补码(two’s-complement)编码:表示有符号整数最常见的方式

  • 浮点数(floating-point)编码:

溢出(overflow):计算机的表示法是用有限数量的位来对一个数字编码。因此结果太大至无法表示时,某些运算就会溢出。

2.1 信息存储

计算机使用8位的块,或者字节(byte)。作为最小的可寻址的内存单元,而不是单独的位。

机器级程序将内存视为一个非常大的数字来标识,称为它的内存。内存的每一个字节都由一个唯一的数字来标识,称为它的地址,所有可能地址的集合称为虚拟地址空间(virtual address space)。

接下来几章将讲述编译器和运行时系统是如何将存储器空间划分为更可管理的单元,来存放不同的程序对象,即程序数据、指令和控制信息。

2.1.1 十六进制表示法

一个字节是8位:

  • 对于二进制表示法,值域是 $00000000_2-11111111_2$

  • 对于十进制表示法,值域是 $0_{10}-255_{10}$

  • 对十六进制表示法,值域是 $00_{16}-FF_{16}$

练习题 2.1

A. 将ox39A7F8转换为二进制. 0011 1001 1010 0111 1111 1000

B. 将二进制 1100 1001 0111 1011 转换为十六进制。 oxE97D

练习题 2.2

$2^n=2^{i+4j}$ 可以很容易写成十六进制就是 2^i后面跟着j个0

比如:

  • $2^9$ -> $2^{1+2x4}$ -> ox200

  • $2^19$ -> $2^{3+4x4}$ -> ox80000

进制的转换

将十进制转换为16进制,其实可以理解为将十进制转换为十进制,就是除以10,余数分别是个位、百位…. 同样的道理,转换为16进制就是除以16

十六进制转换为10进制就更简单了,16的幂乘以每个十六进制数。

2.1.2 字数据大小

对于一个字长为w位的机器,虚拟地址的范围为0~$2^w-1$,程序最多访问$2^w$个字节。

2.1.3 寻址和字节顺序

在几乎所有的机器上,多字节对象都被存储为连续的字节序列,对象的地址为所使用字节中最小的地址。

假设变量x的类型为int, 位于地址0x100处,它的十六进制值为0x01234567. 十六进制的两位占一个字节,因此其地址范围 0x100~0x103.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#include <stdio.h>



typedef unsigned char *byte_pointer; // 字符指针

// 使用 typedef 来命名数据类型



void show_bytes(byte_pointer start, size_t len)

{

size_t i;

for (i=0; i<len; i++)

printf(" %.2x", start[i]);

printf("\n");

}

// size_t 表示size type,大小的类型,意味着它是sizeof运算符结果的类型



// 在C语言中,可以用指针表示法来引用数组元素。引用start[i]表示我们想要读取以start指向的位置为起始的第i个位置处的字节。



void show_int(int x){

show_bytes((byte_pointer)&x, sizeof(int));

}



void show_float(float x){

show_bytes((byte_pointer)&x, sizeof(float));

}



void show_pointer(void *x){

show_bytes((byte_pointer)&x, sizeof(void *));

}



// C 和 C++ 中独有的操作, C的“取地址”运算符 & 创建一个指针 &x, 这个指针的类型取决于 x 的类型,因此这三个指针类型分别为 int*, float*, void**, 数据类型 void * 是一种特殊类型的指针,没有相关联的类型信息。

// (byte_pointer)&x 表示强制转换,无论 &x 之前是什么类型,现在就是一个指向 unsigned char的指针。但这并不会改变真实的指针,只是编译器以新的数据类型来看待被指向的数据。



void test_show_bytes(int val)

{

int ival = val;

float fval = (float) ival;

int * pval = &ival;

show_int(ival);

show_float(fval);

show_pointer(pval);



}





int main()

{

test_show_bytes(12345);

return 0;

}

我的机器是Linux64,运行结果是这样的:

分析下为什么是这样: 12345,十六进制为 ox3039, 对于int数据采用的是4字节:

  • 二进制数表示是: 0000 0000 0000 0000 0011 0000 0011 1001

  • 在小端法机器的十六进制表示为: 39 30 00 00

  • 在大端法机器的十六进制表示为: 00 00 30 39

以一个字节为单位,十六进制一个字节占两位,所以每两个数一个字节。二进制是每8个数一个字节。

为什么浮点数 12345.0 的十六进制是这样的呢?之后会讲到~

练习题 2.5

十六进制数 ox87654321 小端法: 21 43 65 87

A. 小端法: 21 大端法:87

B. 小:21 43 大: 87 65

C. 小:21 43 65 大: 87 65 43

练习题 2.6

3510593 -> ox00359141 -> 0000 0000 0011 0101 1001 0001 0100 0001

3510593.0 -> ox4A564504 -> 0100 1010 0101 0110 0100 0101 0000 0100

最大匹配位数:

2.1.4 表示字符串

每个字符对应一个ASCII码。总共有127个ascii码。

  • 十进制数x的ASCII码正好是 0x3x, 比如要显示字符 0,其ASCII码是48,用十六进制就是0x30.

  • ‘A’‘Z’的ASCII码十进制表示是 6590,‘a’‘z’十进制是 97122,十六进制是ox61~0x7A.

  • null的ASCII码是 0,也就是0x00.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void show_bytes(byte_pointer start, size_t len)

{

size_t i;

for (i=0; i<len; i++)

printf(" %.2x", start[i]);

printf("\n");

}



const char *s = "abcdef";

show_bytes((byte_pointer) s, strlen(s));



运行结果: 61 62 63 64 65 66

2.1.5 表示代码

不同机器类型使用不同的且不兼容的指令和编码方式。

2.1.6 布尔代数简介

0和1的研究~

非、与、或、异或(表示P或者Q为真,但不同时为真时,P^Q为真)

布尔运算可拓展到位向量的运算:

a=[0110], b=[1100], 那么 a&b, a|b, a^b, ~b 分别为:

位向量可以用来表示有限集合。$[a_{w-1},…,a_1,a_0]$(注意是 $a_{w-1}$ 在左边,$a_0$ 在右边) 编码任何子集 $A\in {0,1,2,…,w-1}$. 比如 a=[00101]就表示 A={0,2}. 其实可以把 a 看做多标签的 one-hot向量。。。

练习题 2.9

蓝色|绿色 = [001]|[010] = [011] = 蓝绿色

红色 ^ 红紫色 = [100]^[101] = [001] = 蓝色

2.1.7 C语言中的位级运算

布尔位运算。

从十六进制转换为二进制,进行运算,在转换回十六进制。

练习题 2.10

任意一位向量 a,有 a ^ a = 0. 那么 a^a^b=b.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <stdio.h>



void inplace_swap(int *x, int *y)

{

* y = * x ^ * y;

* x = * x ^ * y;

* y = * x ^ * y;

}



int main()

{

int a=5, b=4;

printf("%p, %p\n",&a, &b);

inplace_swap(&a, &b);

printf("%p, %p\n",&a, &b);

printf("%i, %i\n", a, b);

return 0;

}



运行结果:

1
2
3
4
5
6
7

0x7ffe90686210, 0x7ffe90686214

0x7ffe90686210, 0x7ffe90686214

4, 5

我们发现这里其实a和b的地址没有改变,是地址对应的值在进行异或运算。 5^4=1, 5^1=4, 4^1=5. 这就是二进制运算,也就是位运算。

6^5=3, 6^3=5, 5^3=6.

不过不要误会,跟加减法没关系,原理还是二进制 a^a=0. 所以能进行交换,就是因为 a^b^a=b.

结果是:

step1 a a^b

step2 a^(a^b)=b a^b

step3 b b^(a^b)=a

练习题 2.11

将 <= 改为 < 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <stdio.h>



void inplace_swap(int *x, int *y)

{

* y = * x ^ * y;

* x = * x ^ * y;

* y = * x ^ * y;

}



void reverse_array(int a[], int cnt)

{

int first, last;

for (first = 0, last = cnt -1; first < last; first++, last--)

inplace_swap(&a[first], &a[last]);



}



int main()

{

int a[] = {1,2,3,4,5};

reverse_array(a, 5);

for (int i=0; i<5; i++)

printf("%i", a[i]);

printf("\n");

return 0;



}

2.1.8 C语言中的逻辑运算

包括 ||, && 和 !, 逻辑运算认为所有非零参数为TRUE,参数0 表示 FALSE.

要注意与位运算区分开来。

习题 2.15

if ((x^y)|(x^y))

return 1

else

return 0

2.1.9 C语言中的移位运算

x << k: 表示向左移动k位,右边补0

x >> k: 有两种情况:

  • 逻辑右移:向右移动k位,左边补0

  • 算术右移:向右移动k位,左边补最高位的值。

可以看到一定是在一个字节内的,也就是以一个字节为整体。

对于有符号数:

在java中 x>>k 是算术右移, x>>>>k 是逻辑右移。

C语言中没有明确规定,但几乎所有的编译器采用算术右移。也就是补最高位的值。

对于无符号数,右移必须是逻辑右移。

移位运算符的优先级低于加法和减法。

2.2 整数表示

整数操作术语:

2.2.1 整型数据类型

32位机器:

64位机器:

跟机器相关的整型数据类型就只有 long,在64位中占8个字节。在32位中占4个字节。

可以稍微记一下这些数:

  • 有符号字符, 1个字节。 范围 $-2^7=128 \sim 2^7-1=127$

  • 无符号字符, 1个字节。 范围 $0 \sim 2^8-1=255$

  • 有符号短整型,2个字节。范围 $-2^15=-32768 \sim 2^15-1=32767$

  • 无符号短整型,2个字节。范围 $0 \sim 2^16-1=65535$

  • 有符号整型, 4个字节。范围 $-2^31=-2 147 483 648 \sim 2^31-1=2 147 483 647$

  • 无符号整型, 4个字节。范围 $0 \sim 2^32-1=4 294 967 295$

无符号的数值范围是有符号的两倍,是因为有符号数需要拿出一位来表示符号,所以就小了一倍了。比如:一个字符是一个字节,8位,无符号范围就是 $2^8-1=255$, 有符号就是 $2^7-1=127$.

然而后面介绍了补码,少一位编码是对的,但是负数的计算并不是这样哈哈哈,打脸了,并没有这么简单啦~~~ 这也解释了为啥负数是 -128, 正数是 127.

C语言标准定义的每种数据类型必须表示的最小的取值范围。

2.2.2 无符号数的编码

将二进制写成向量。

2.2.3 补码编码

为了标书负数值,最常见的就是补码(two’s-complement)形式, 将字的最高有效位解释为负权(negative weight).

最高位的权重是 $-2^{w-1}$,对该数是正是负取决定性作用。其为1时,为负;其为0时,为正。

所以w位补码能表示的范围:

$$-2^{w-1} \sim \sum_{i=1}^{w-1}2^i=2^{w-1}-1$$

重要的数字:

  • UMax 表示最大无符号数,UMin没有写,就是0啦

  • TMax 表示最大有符号数,TMin 表示最小有符号数。

可以发现:

  • 补码不对称,$|TMin| = |TMax| + 1$

  • 无符号最大值是有符号最大值的2倍大一点。比如一个字节8位为例,(2^8-1) = 2(2^7-1)+1.

练习题2.18 看不懂

2.2.4 有符号数和无符号数之间的转换

强制转换保持位值,只是转换了其解释方式。

比如32为的无符号最大值 4294967295($UMax_32$),与补码形式的-1的位模式是完全一样的。

有符号转无符号 $T2U_w$
1
2
3
4
5
6
7
8
9
10
11
12
13

int main()

{

unsigned u = 4294967295u;

int tu = (int) u;

printf("u=%u, tu=%d\n", u, tu);

}

运行结果:

1
2
3

u=4294967295, tu=-1

补码和无符号码之间的关系,以16位为例:

有符号码:

12345的二进制: 0011 0000 0011 1001

-12345的二进制数: 1100 1111 1100 0111

53191的无符号码和-12345的二进制表示一样。

可以发现 $12345 + 53919 = 2^{16}$

其实很容易推导出来, 可以得到如下关系:

从符号转无符号,如果是负数 u , 假设除了最高位的数表示为 y,那么:

$-2^{w-1} + y = u$

现在要求无符号:

$2^{w-1}+y = u+ 2*2^{w-1}= 2^w + u$

无符号转有符号 $U2T_w$

$TMax_{w} = 2^{w-1}-1$

当 $u > TMax_w$ 时,显然转换为有符号应该是负的。

无符号:

$2^{w-1}+y = u$

有符号:

$-2^{w-1} +y = u-2*2^{w-1}=u-2^w$

2.2.5 C语言中的有符号数和无符号数

一般都默认为是有符号数,要创建一个无符号数,必须加上后缀 ‘u’ 或 ‘U’.

显示的强制转换:

隐式的强制转换:

输出 %d, %u, %x 分别表示十进制、无符号十进制和十六进制。所以在printf输出时,也会发生转换。 总之,记住输出的类型只是一种解释形式,底层的位值是不变的。

当执行运算时,一个运算数是无符号的,一个是有符号的。那么有符号的会隐式的转换为无符号进行计算。 比如32位机器中 -1 > 0u. 这里的-1是 4294967295u

2.2.6 拓展一个数字的位表示

  • 无符号拓展 $B2U_w(\overrightarrow u)=B2U_{w’}=(\overrightarrow u’)$ 在表示的开头添加 w’-w 个0
  • 有符号拓展 $B2T_w(\overrightarrow x) = B2T_{w’}(\overrightarrow x’)$ 在表示开头添加 w’-w 个 $x_{w-1}$

对于无符号很好理解,添加0后值不会改变。但对于有符号的负数,添加1之后,其值也是没有改变的。比如有符号 [101] 表示 -4+1=-3. 扩展一位 [1101]= -8+4+1= -3. 这是因为每扩展一位 $-2^w+2^{w-1}=-2^{w-1}$. 所以不变~~

2.2.7 截断数字

截断无符号数,其实就是取模运算

$x=B2U_w(\overrightarrow x), x’=B2U_k(\overrightarrow x’)$

则 x’=x mod $2^k$. 即对 2^k 取余。

截断有符号数

$[x_{w-1},x_{w-2},…,x_0]$

先按照无符号数截断,也就是对 $2^k$ 取余。然后在转换为有符号数。

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

练习题 2.25

出现错误是因为 length 是无符号数,当length=-1时,会转换为 2^31-1. 循环会无限循环下去。 将 unsigned lenght 修改为 int length 即可。

练习题2.26

strlen 返回的 size_t 是unsigned int, 所以 相减为-1之后会转换。 所以改为 int (strlen(s)- strlen(t)) > 0;

无符号数有时候会很有用的。

2.3 整数运算

2.3.1 无符号加法

x, y是无符号数,0 < x,y < $2^w-1$. 如果溢出,说明 $2^{w} \le x+y < 2^{w+1}-2$. 需要 w+1 位才能表示出来。

s = x + y. 当溢出时,s = x + y - 2^w

溢出时,w+1位为1,丢弃它相当于从和中减去了 $2^w$。正常情况下,w+1 位为0,不会影响。

检测无符号溢出的条件:

如果溢出:$s = x + y -2^w$, 那么 $s = x+(y-2^w) <x$, 同样 $s = y+(x-2^w)<y$

习题 2.27

1
2
3
4
5
6
7
8
9
10
11

int uadd_ok(unsigned x, unsigned y)

{

unsigned s = x + y;

return s >= x;

}

无符号数求反

模数加法形成一种数据结构,称为阿贝尔群,也就是求 x 的逆元 $-^u_w x$. 什么意思呢,就是 这个逆元加上 x 对2^w 取模等于 0.

所谓模数加法,超过了模 $2^w$, 就是除以模 $2^w$ 的余数

练习题2.28

| x 十六进制 | x 十进制 | $-^u_4x$ 十进制 | $-^u_4x$十六进制 |

| ———- | ——– | ————— | —————- |

| 0 | 0 | 0 | 0 |

| 5 | 5 | 11 | B |

| 8 | 8 | 8 | 8 |

| D | 13 | 3 | 3 |

| F |15 | 1 | 1 |

2.3.2 补码加法

注意跟无符号数正溢出的区别,无符号数溢出之后是去掉 w+1 位,但是有符号数正溢出时,$x+y<2^w$,w位还是要考虑的,只是变为负数了。所以是 $x+y-2*2^{w-1}$, 而不能认为是 $x+y-2^{w-1}$

但是负溢出,就会溢出到 w+1 位了,那么去掉 w+1 位,就是 $x+y+ 2^w$ 了

推导的话,因为不论有符号还是无符号,都是相同的位级表示,二进制的加法也是进位同样的方式。 只是解释方式不一样而已。所以可以将有符号转换为无符号数进行 $+^u_w$ 的模 $2^w$ 的模数加法运算,然后在转换为有符号数即可。

补码溢出的条件

习题 2.30

补码溢出判断:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int tadd_ok(int x, int y)

{

int sum = x+y;

if ((x>0 && y>0 && s<=0) || (x<0 &&y<0 && s>=0))

return 0;

return 1;

}



习题 2.31

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/* Determine whether arguments can be added without overflow */

/* WARRING: This code is buggy */

int tadd_ok(int x, int y)

{

int sum = x+y;

return (sum-x == y) && (sum-y ==x);

}

无论正确与否,都是返回 1. 模数加法形成了一种数据结构,称为阿贝尔群(Abelian group). 因此代码中的判断,无论溢出与否,都是成立的,都返回 1;

具体推导如下:

如果 x+y 溢出, $sum = x+y-2^w$,

那么 $sum-x = y-2^w$.

因为 $y < 2^{w-1}-1$, 则 $y-2^w< -2^{w-1} -1$, 仍然负溢出。

所以 $sum-x= y-2^w+2^w = y$.

习题 2.32

x -y 不溢出时,返回1.

1
2
3
4
5
6
7
8
9
10
11

/* Determine whether arguments can be subtracted without overflow */

/* WARNNING: This code is buggy. */

int tsub_ok(int x, int y){

return tadd_ok(x, -y);

}

x 和 y 取什么值是,会产生错误的结果?

当 $y = TMin_w = -2^{w-1}$ 时, $-y = 2^{w-1}$ 原本应该是正数的,但已经溢出了,转换成了负数。 $-y = y$.

此时对于 tadd_ok(x, -y) 来说,当 x 为负时都认为溢出,返回 0,而 x 为非负时,都认为没有溢出返回 1。而情况恰恰相反,tsub_ok(x, TMin),当 x 为 负数时,应认为没有溢出,返回 1,而 x 为非负时,应认为溢出返回 0.

2.3.3 补码的非

因为补码又负数,所以一般情况下,其逆元就是 -x, 而对于 $TMin_w$, $-TMin_w$ 会溢出,就不属于一般情况了。

练习题 2.33

| x 十六进制 | x 十进制 | $-^t_4x$ 十进制 | $-^t_4x$十六进制 |

| ———- | ——– | ————— | —————- |

| 0 | 0 | 0 | 0 |

| 5 | 5 | -5 | -5 |

| 8 | -8 | -8 | 8 |

| D | -3 | 3 | 3 |

| F | -1 | 1 | 1 |

第二种方法: 执行位级补码非,然后加1

对于无符号数或有符号数,非(或者逆元),他们的位模式是一样的。都是位模式取反+1, 对任意整数 非(逆元)-x 和 其位模式取反(位级补码非)加1 ~x+1 都是一样的。

2.3.4 无符号乘法

$0\le x,y \le 2^w-1$, $0\le x\cdot y z^{2w}-2^{w-1}+1$ 需要2w 位来表示。将其截断为 w 位,等价于计算该值模 $2^w$.

$$x*^u_w y = (x\cdot y)mod\ 2^w$$

2.3.5 补码乘法

补码乘法和无符号的乘法运算的位级表示是一样的。

对于 $TMin_w\le x,y\le TMax_w$ 有:

$$x*^t_wy=U2T_w((x\cdot y)mod\ 2^w)$$

原理是:

$$T2B_w(x^t_wy)=U2B_w(x’ ^u_w y’)$$

x’,y’ 是x,y的无符号转换后的数。

证明略。

虽然完整的乘积的位级表示可能不同,但截断后是一样的。

练习题 2.34

| 模式 | x | y | $x\cdot y$ | 截断后的 $x\cdot y$ |

| —— | ——– | ——– | ———– | ——————- |

| 无符号 | [100]=4 | [101]=5 | [10100]=20 | [100]=4 |

| 补码 | [100]=-4 | [101]=-3 | [1100] = 12 | [100]=-4 |

| 无符号 | [010]=2 | [111]=7 | [1110]=14 | [110]=6 |

| 补码 | [010]=2 | [111]=-1 | [110] =-2 | [110]=-2 |

练习题 2.35

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* Determine whether arguments can be multiplied without overflow */



int tmult_ok(int x, int y)

{

int p = x*y;

/* Either x is 0, or dividing p by x gives y * /

return !x || p/x == y;

}



见题 2.31,我们不能用减法来检验加法是否溢出,但这里可以用除法为检验乘法是否溢出。

证明 ??

练习题 2.36

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int tmul_ok(int x, int y)

{

/* Compute product without overflow*/

/* 这一行的强制类型转换至关重要。如果写成 int64_t p = x*y; * /

/* 就会用 32 位值来计算乘积(可能溢出),再符号扩展到 64 位*/

int64_t p = (int64_t) x * y;

/* See if casting to int preserves value*/

return (int)p == p;

2.3.6 乘以常数

在大多数机器上,整数乘法指令相当慢,需要10个或者多个时钟周期。而加法、减法、位级运算和移位只需要1个时钟周期,因此编译通常把乘法转换为移位和加法的组合运算。

1.先考虑乘以 2 的幂

与2的幂的无符号乘法:

x << k 产生数值 $x*^u_w 2^k$

与2的幂的补码乘法: 补码与无符号的位级操作等价,因此补码运算的2的幂的乘法也类似。

x << k 产生数值 $x*^t_w 2^k$

无论是补码还是无码,都可能溢出。即使溢出,通过移位和乘法的结果也是一致的,截断就好了。

对任意数的乘法可写成:

$x14 = x(2^3+2^2+2^1)$

或者 $x14 = x(2^4-2^1) = (x<<4)-(x<<1)$

练习题 2.38

(a<<k)+b, 其中k可以为0,1,2,3, b可为0或a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

a 的倍数 LEA 指令

2a (a<<1)+0

3a (a<<1)+a

4a (a<<2)+0

5a (a<<2)+a

8a (a<<3)+0

9a (a<<3)+a

乘法还可以这么看, x*K. 编译器将k的二进制表达为一组0和1交替的序列。

n表示第一段开始的n个连续的1,n-1表示第二段连续的1。

比如以8位为例,14 可以写成 [(0000)(111)(0)],从第3位开始到第1位为连续的1.

那么 x*14=(x<<3)+(x<<2)+(x<<1)

或者 x*14=(x<<4)-(x<<1)

很神奇。。。

练习题2.40

练习题2.41

编译器A、B两种形式选择哪一种: 选择操作次数少的。

2.3.7 除以2的幂

除法更慢,需要30多个时钟周期。也可以采用移位运算实现。只不过是右移。无符号是逻辑右移(补0),补码是算术右移(补1)

定义向下取整 $\lfloor a \rfloor=a’. a’\le a\le a’+1$. 对于非负整数是满足除法的,但 $\lfloor -3.14 \rfloor = -4$ 是不满足的。

除以2的幂的无符号除法

x>>k 等价于 $\lfloor x/2^k\rfloor$

除以2的幂的补码除法

算术右移,对与正数来说,最高有效位是0,与无符号的逻辑右移是一样的。

但对于负数来说,最高有效位是1,右移后效果如下图:

$[x_{w-1},..,x_{w-1},x_{w-2},…,x_k]$ 是 $\lfloor x/2^k\rfloor$ 的补码表示,但是它不是向零舍入。需要使用“偏置”来修正这种不合适的舍入。

(x+(1<<k)-1)>>k 等价于 $x/2^k$ 向上取整。

偏置技术利用了如下属性: $\lceil x/y \rceil = \lfloor (x+y-1)/y \rfloor$

推导: 假设 x = qy+r.

$\lfloor (x+y-1)/y\rfloor=q+\lfloor(r+y-1)/y\rfloor$

当r=0时,也就是能整除,$\lfloor(r+y-1)/y\rfloor=0$. 这也是要-1的原因,不然对于整除的时候就不符了。

当r>0时,y>r>1,$\lfloor(r+y-1)/y\rfloor=1$, 结果相当于 q+1

所以,当 y=2^k 时, (x+(1<<k)-1)>>k = $\lceil x/2^k\rceil$

总结: 对于使用算术右移的补码机器,C表达式:

(x<0 ? x+(1<<k)-1 : x) >> k

练习题2.42

写一个函数 div16,对于整数参数 x 返回 x/16 的值。要求不能使用除法、模运算、乘法、条件语句 (if 和 ? : )、比较运算符、循环等。假设 int 为 32 位,补码,算术右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int div16(int x){

/* (x+bias) >> k

对于 x 为正数, bias=0

对于 x 为负数, bias=(1<<4)-1=15*/

int bias = (x>>31) & 0xf;

printf("%d", bias);

return (x+bias) >> 4;

}

练习题 2.43

下面的代码中,省略了常数 M 和 N 的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#define M /* Mystery number 1 */

#define N /* Mystery number 2 */

int arith(int x, int y)

{

int result = 0;

result = x*M + y/N;

return result;

}

用某个 M 和 N 的值编译上面代码后,编译器将优化乘除操作。下面是产生的机器码翻译回 C 的结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/* Translation of assembly code for arith */

int optarith(int x, int y)

{

int t = x;

x <<= 5;

x -= t; /* x = x*2^5 -x,使用了形式B的优化:(x<<(n+1))-(x<<m),

这里 n=4, m=0, 从而 M = [11111] = 31*/

if (y < 0) y += 7; /* y + (1<<3)-1*/

y >>= 3; /* Arithmetic shift,从而 N 为 2 的 3 次方,即为 8*/

return x+y;

}

M=31, N=8

2.3.8 关于整数运算的最后思考

整数运算实际上是一种模运算形式。 整数表示的有限字长限制了运算结果的取值范围,从而可能会溢出。无论是补码表示还是无符号数,它们的加减乘除操作,在位级上都完全一样或非常类似。

C 中的 unsigned 数据类型变量,在运算中会隐式地要求将其它参数先转换成 unsigned 数据类型再计算,从而会导致难以察觉的 BUG。

习题2.44

A. x=TMin_w 时为假, $x = -2^{w-1}-1 = -2^{w-1}-1+2^w=2^{w-1}-1 >0$

B. 举反例就是两边都为假。左边 (x&7)=7=[000…0111], 那么最后三位都为1. 右边 x<<29 >0,那么倒数第三位为0. 所以不存在同时两边都为假的x。

C. 当 $x=2^31-1$, $x*x=2^62-2$,溢出,截断之后最高位为1,肯定小于0

2.4 浮点数

2.4.1 二进制小数

小数的二进制表示法只能表示 $x\times 2^y$ 的数,其他的只能近似表示。二进制表示的长度可以提高表示的精度。 例如 $\dfrac{1}{5}$ 可以用十进制0.20精确表示,但并不能准确的用二进制表示。

$0.111…1_2$ 表示刚好小于0的数。用 $1.0-\epsilon$ 表示

2.4.2 IEEE浮点表示

  • 符号位 s

  • 阶码(exponent)E的作用是对浮点数加权。

  • n为小数字段 $frac=f_{n-1}\cdots f_1f_0$, 编码出来的也依赖与阶码段的值是否为0

单精度: s, exp, frac字段为 1,8,23 位

双精度: s,exp, frac字段为 1,11,52 位

1.规格化的值

exp的位模式不全为0,也不全为1。 阶码字段被解释为以偏置形式的有符号整数。

阶码的值 $E=e-Bias$, e是无符号数,为表示是 $e_{k-1}\cdots e_1e_0$. Bias等于 $2^{k-1}-1$.

所以单精度范围:

$e_{max}=2^8-2, e_{min}=1$

$E_{max}=2^8-2-2^7+1=127$

$E_{min}=1-(2^7-1)=-126$

2.非规格化的值

阶码全为0, E=1-Bias.

3.特殊值

  • 当阶码全为1时,小数域全为0,得到的值表示无穷。s=0时是正无穷,s=1是负无穷。
  • 阶码全为1, 小数域非0,表示NaN.

2.4.3 数字示例

作者

Xie Pan

发布于

2018-06-09

更新于

2021-06-29

许可协议

评论