CSAPP3 2.1 信息存储

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

无符号整数 (unsigned) 基于传统的二进制表示法编码,表示大小或等于 0 的数字。有符号整数通常用补码 (two’s-complement) 编码。浮点数 (floating-point) 编码表示实数以 2 为基数的科学记数法的版本,因此是一种近似表示。

计算机用有限位来编码数字,因此,当去处结果太大时会出现溢出 (overflow)等。

十六进制表示法

一个字节(8位)由两个十六进制数表示。在进行二进制、十进制、十六进制间的转换时,只需记住 A、C、F的十进制值和对应的二进制表示,其它的都可对应快速计算出。 (A, 1010, 10), (C, 1100, 12), (F, 1111, 15)。

练习题2.1 p62

A. 将 0x39A7F8 转换为二进制。

11 1001 1010 0111 1111 1000

3 9 A 7 F 8

B. 将二进制 1100100101111011 转换为十六进制。

1100 1001 0111 1011

C 9 7 B

C. 将 0xD5E4C 转换为二进制。

1101 0101 1110 0100 1100

D 5 E 4 C

D. 将二进制 1001101110011110110101 转换为十六进制。

10 0110 1110 0111 1011 0101

2 6 E 7 B 5

当 $x$ 是 2 的非负整数 $n$ 次幂时,即 $x=2^n$ 时,$x$ 的二进制形式即为 1 后面加 n 个 0,而十六进制数字 0 表示 4 个二进制 0,因此十六进制表示时为 1 后面加 n/4 个 0。所以,当 $n$ 表示成 $i+4j$ 形式时(其中 $0 \leq i \leq 3$),可以把 $x$ 写成开头的十六进制数字为$1(i=0)$, $2(i=1)$, $4(i=2)$, $8(i=3)$,后面跟 $j$ 个 0。比如 $x=2048=2^{11}$ 时,有 $n=11=3+4*2$,从而十六进制表示为 $0x800$

练习题 2.2 p62

给出 2 的不同次幂的二进制和十六进制表示:

$n$ $2^n$(十进制) $2^n$(十六进制)
9, $1+4\bullet2$ 512 0x200
19, $3+4\bullet4$ $1024\bullet512$=524288 0x80000
14, $2+4\bullet3$ 16384=$1024\bullet16$ 0x4000
16, $0+4\bullet4$ $1024\bullet64$=65536 0x10000
17, $1+4\bullet4$ $1024\bullet128$=131072 0x20000
5,$1+4\bullet1$ 32 0x20
7,$3+4\bullet1$ 128 0x80

十六进制数字和十进制间的相互转换通过除以 16 和乘以 16 的幂进行。

练习题2.3 p62 补全下面的二进制、二进制、十六进制对应表。

十进制 二进制 十六进制
0 0000 0000 0x00
$167=10\bullet16+7$ 1010 0111 0xA7
$62=3\bullet16+14$ 0011 1110 0x3E
$188=11\bullet16+12$ 1011 1100 0xBC
32+16+7,55 0011 0111 0x37
128+8,136 1000 1000 0x88
128+64+32+16+3,243 1111 0011 0xF3
128+16+2,146 1001 0010 0x52
128+32+8+4,172 1010 1100 0xAC
128+64+32+7,131 1110 0111 0xE7

十进制和十六进制间的转换,也可以直接通过搜索引擎获取。

练习题2.4 p63

不通过转换,直接进行十六进制加减。

A. 0x503c + 0x8 = 0x5044

B. 0x503c - 0x40 = 0x4FFC

C. 0x503c + 64 = 0x503c + 0x40 = 0x507c

D. 0x50ea = 0x503c = 0xAE

字数据大小

虚拟地址用一个字来编码,因此字长决定了程序可访问的最大虚拟地址空间大小。

寻址和字节顺序

在几乎所有的机器上,多字节对象都是被存储为连续的字节序列,并且用字节中最小的地址作为对象的地址。例如,对于 4 字节的 int 变量 x 的地址为 0x100,则 x 的 4 个字节被存储在 0x100, 0x101, 0x102, 0x103 位置。

排序表示一个对象的字节有 2 种通用规则。例如有 $w$ 位的整数,其位表示为 $[x_{w-1},x_{w-2},\cdots,x_1,x_0]$,其中 $x_{w-1}$ 是最高有效位,而 $x_0$ 是最低有效位。假设 $w$ 是 8 的倍数,这些位就能被分组成字节,其中最高有效字节包含位$[x_{w-1},x_{w-2},\cdots,x_{w-8}]$,而最低有效字节包含位$[x_7,x_6,\cdots,x_0]$。

有些机器选择从最低有效字节到最高有效字节的顺序存储对象,即最低有效字节保存在最低地址位置,这种叫小端法 (little endian);而最高有效字节存储在最前面的方式,叫大端法(big endian)。

假设 4 字节的 int 型变量 x 位于地址 0x100处,其值为 0x01234567,则其地址范围为 0x100~0x103。

那么大端法中, 从地址 0x100 到 0x103 存储的字节值依次为 0x01, 0x23, 0x45, 0x67;而小端法依次存储的是 0x67, 0x45, 0x23, 0x01

大多数 Intel 兼容机使用小端法,此时在看其字节级指令时,要注意其中给出的数值字节序。书写字节序列的自然方式是最低位字节在左边,而最高位字节在右边,这正好和通常书写数字时最高有效位在左边,最低有效位在右边相反。因此,当小端法机器的字节指令中的数值序列为 78 56 34 12 时,表示的值将是 0x12345678。

用下面的 show_types 来输出对象的字节内容:

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len){
    size_t i;
    for (i=0; i<len; i++)
        printf(" %.2x", start[i]);
    printf("\n");
}

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_int(void *x) {
    show_bytes((byte_pointer) &x, sizeof(void *));
}

练习题 2.5 p69

思考下面对 show_bytes 的三次调用:

int val = 0x87654321; byte_pointer valp = (byte_pointer) &val; show_bytes(valp, 1); /* A. */ show_bytes(valp, 2); /* B. */ show_bytes(valp, 3); /* C. */

指出在小端法和大端法机器上,每次调用的输出值。

在小端法机器上,变量从低地址开始存储的字节值为 21 43 65 87,而大端法的为 87 65 43 21。 故:

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

B. 小端法: 21 43, 大端法:87 65

C. 小端法: 21 43 65, 大端法:87 65 43

练习题 2.6 p70

使用 show_int 和 show_float, 我们确定整数 3510593 的十六进制为 0x00359141,而浮点数 3510593.0 的十六进制表示为 0x4A564504。

A:写出这两个十六进制值的二进制表示。

0000 0000 0011 0101 1001 0001 0100 0001

0 0 3 5 9 1 4 1

0100 1010 0101 0110 0100 0101 0000 0100

4 A 5 6 4 5 0 4

B: 移动这两个二进制串的相对位置,使得它们相匹配位数最多,有多少位匹配?

00000000001 101011001000101000001

010010100 101011001000101000001 00

一共有 21 位匹配。

C:串中的什么部分不相匹配?

整数中除了最高有效位 1 ,其它位都嵌在浮点数中,浮点数中有一些非零的高位不与整数中的高位匹配。

练习题 2.7 p70

下面对 show_bytes 的调用将输出什么?

const char *s = "abcdef";
show_bytes((byte_pointer)s, strlen(s));

注意字母 ‘a’ ~ ‘z’ 的 ASCII 码为 0x61 ~ 0x7A。

61 62 63 64 65 66

布尔代数

0 和 1 之间的与、或、非、异或操作。位向量的操作。

练习题 2.8 p72

给出位向量的布尔运算的求值结果。

运算 结果
a [01101001]
b [01010101]
~a [10010110]
~b [10101010]
a&b [01000001]
a|b [01111101]
a^b [00111100]
位向量可用来表示有限集合。可以用位向量 $[a_{w-1},\cdots,a_1,a_0]$ 编码任何子集 $A \subseteq {0, 1, \cdots, w-1}$,其中 $a_i=1$ 当且仅当 $i \in A$。这里我们将 $a_{w-1}$ 写在左边,$a_0$写在右边,则位向量a=[01101001] 表示集合 A = {0, 3, 5, 6}, 而 b=[01010101] 表示集合 B = {0, 2, 4, 6}。此时,位向量的 和 & 运算分别对应于集合的并和交,而 ~ 对应于集合的补。实际中,位向量可用来表示中断信号掩码。

练习题 2.9 p73

位向量的与、或、非、异或操作。

RGB 颜色的位向量为 [RGB]

A. 位向量中的每一位取反。

B. 布尔运算结果如下:

Blue Green = [001] [010] = [011] = Cyan

Yellow & Cyan = [110] & [011] = [010] = Green

Red ^ Magenta = [100] ^ [101] = [001] = Blue

C 语言中也支持位级的布尔运算

进行运算时,先将数值从十六进制转成二进制,运算后再转换回十六进制。

练习题 2.10 p74

利用位向量的 a^a=0 的属性,可用下面的程序进行两变量的值交换,而无需使用到一个临时存储变量。

void inplace_swap(int *x, int *y)
{
    *y = *x ^ *y; /* Step 1 */
    *x = *x ^ *y; /* Step 2 */
    *y = *x ^ *y; /* Step 3 */
 }

补全每步运算后的 x 和 y 值。

程序依赖两个事实,^ 操作是可交换和可结合的,以及任意的向量 a^a=0 的属性。

步骤 *x *y
初始 a b
Step 1 a a^b
Step 2 a^(a^b)=b a^b
Step 3 b b^(a^b)=a

上面的推理隐含地假设了 x 和 y 代表不同的位置。但当 x 和 y 值指向相同的位置时,会将值设置为了 0,如题 2.11 如示。

练习题 2.11 p74

在 2.10 的 inplace_swap 函数的基础上,你写出下面的函数来将一个数组中的元素头尾两端依次对调。

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]);
}

该代码当数组是偶数长度时是正确的,如输入 1 2 3 4, 输出为 4 3 2 1,但对奇数长度时会出错,如输入 1 2 3 4 5,输出 5 4 0 2 1,会把中间的值设置为了 0。

A. 对于长度为奇数的数据,长度 $cnt = 2k + 1$,函数最后一次循环时,变量 first 和 last 的值都为 k。

B. 这时调用 inplace_swap 时,由于 a^a = 0,所以将元素设置为了 0。

C. 对 reverse_array 代码做哪些简单改动能消除这个问题。

只需将 first <= last 调整为 first < last 即可。

位级运算可用于掩码计算,发 ~0 将生成一个全 1 的掩码。

练习题 2.12 p75

对于下面的值,写出变量 x 的 C 语言表达式。代码要对任何字长 $w \geq 8$ 都能工作。我们给出了当 x=0x87654321 及 $w=32$ 时表达式求值的结果。

A. x 的最低有效字节,其它位均置为 0。[0x00000021]。 x & 0xFF

B. 除了 x 的最低有效字节外,其它的位都取补,最低有效字节保持不变。 [0x789ABC21]

x^ (~0xFF)

C. x 的最低有效字节设置成全 1,其它字节都保持不变。 [0x876543FF]

x 0xFF

练习题 2.13 p75

bis(位设置)函数和 bic(位清除)函数都输入一个数字字 x 和一个掩码字 m,并返回一个结果 z。bis 将在 m 为 1 的每个位置上将 x 对应的位设置为 1,而 bic 将 m 为 1 的每个位置上将 x 对应的位设置为 0。只使用 bic, bis 实现按位 和 ^ 运算。提示:写出 bis, bic 运算的 C 表达式。
/* Declarations of funs implementing operations bis and bic */
int bis(int x, int m);
int bic(int x, int m);

/* bis(x,y): 返回 x|y
 bic(x,y): 返回 x & (~y) */
 
/* Compute x|y using only calls to funs bis and bic */
int bool_or(int x, int y)
{
    int result = bis(x,y); /* bis 即为 | 操作 */
    return result;
}

int bool_xor(int x, int y)
{
    /*
    异或操作:相同为 0,不同为 1:
    xor: bic(x,y) | bic(y,x)
    */
    int result = bis( bic(x,y), bic(y,x));
    return result;
}

C 语言中的逻辑运算

逻辑运算将非零认为 TRUE(值为 1),FALSE 值为 0,并且运算时,当前面的参数求值能确定表达式结果时,就立即返回,不对后面的进行求值。

练习题 2.14 p76

假设 x=0x66, y=0x39,填写下表各值:

x = 0110 0110

~x= 1001 1001

y = 0011 1001

~y= 1100 0110

表达式 表达式
x & y 0010 0000=0x20 x && y 1
x | y 0111 1111=0x7F x || y 1
~x | ~y 1101 1111=0xDF !x || !y 0
x & !y 0 x && ~y 1

**练习题 2.15 p76 **

只使用位级和逻辑运算,编写一个 C 表达式,它等价于 x==y。即当 x 和 y 相等时返回 1,否则返回 0。

相等时,异或操作将为 0,刚表达式为 !(x^y)

C 语言中的移位运算

逻辑右移在左端补 0,算术右移在左端补最高有效位的值,以保持有符号整数的符号值。C 标准没有规定使用哪种右移,但是几乎所有的编译器/机器都对有符号数使用算术右移。对于无符号数,右移必须是逻辑的。

而 Java 有明确定义,x>>k 为算术右移,而 x>>>k 为逻辑右移。

当位移量 k 大于数据类型的位数时,C 标准没有定义如何做,但一般是移位 $k mod w$ 位,而 Java 中是明确移位 $k mod w$ 位的。

练习题 2.16 p77

移位运算时最好使用二进制表示。填写下表值:

x hex x bin x«3 bin x«3 hex x»2(逻辑) bin x»2(逻辑) hex x»2(算术)bin x»2(算术) hex
0xC3 1100 0011 0001 1000 0x18 0011 0000 0x30 1111 0000 0xF0
0x75 0111 0101 1010 1000 0xA8 0001 1101 0x1D 0001 1101 0x1D
0x87 1000 0111 0011 1000 0x38 0010 0001 0x21 1110 0001 0xE1
0x66 0110 0110 0011 0000 0x30 0001 1001 0x19 0001 1001 0x19

参考


上一篇     下一篇