深入理解计算机系统第二章：信息的表示和处理（附DataLab实验）

字数统计: 6.1k   |   阅读时长≈ 24 分钟

深入理解计算机系统第二章：信息的表示和处理

现代计算机存储和处理的信息以二值信号表示。

2.1 信息存储

由于在计算机中，十进制对位的转化很麻烦，二进制去表示又太冗长，所以用16进制表示来规避前两种表示法的缺点。

​ 大多数计算机使用字节（byte），也就时8位的块，作为最小的可寻址内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存（virtual memory）。内存的每个字节都由一个唯一的数字来标识，称为它的地址（address），所有可能地址的集合就称为虚拟地址空间（virtual address space）。每台计算机都有一个字长（word size），指明指针数据的标称大小。因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的参数就是虚拟地址空间大小。也就是说对于一个字长为Ω位的机器而言，虚拟地址的范围为0 ~ 2^Ω^ - 1，程序最多访问2^Ω^个字节。64位字长的计算机可以向下兼容32位字长的计算机，但是反向却不行。为了避免由于依赖典型大小和不同编译器设置带来的奇怪行为，ISO C99引入了一类固定大小的数据类型，不随编译器和机器设置而变化，如int32_t和int64_t。在内存中，有两种不同存储字节的顺序，最低有效字节在最前面的方式，称为小端法；最高有效字节在最前面的方式称为大端法。

​ 字符串是一个以null（值为\x00）字符结尾的字符数组，每个字符通过ASCII编码（最常见，后面整合为Unicode字符集）。C语言使用布尔代数来表示逻辑判断的结果，也就是0，1。0代表false，1代表true。c语言支持按位布尔运算，也就是|、&、~、^，也支持逻辑运算&&、!、||和移位运算<<、>>，右移分为逻辑右移和算术右移，逻辑右移是在左端补0，而算术右移是在左端补最高有效位的值。一般对有符号数都使用算术右移。

2.2 整数表示

​ 在C语言中，整数有多种数据类型，来表示有无符号和不同大小的取值范围。无符号数是常规的编码，而有符号数往往使用补码编码。对于正整数，补码与原码相同，对于负整数，补码则是将原数按位取反，符号位填一，末位加一。所以这也是我们有时能在内存中看到一个较大数的原因。有符号数和无符号数的转换在C语言中是直接解释位的。也就是将补码当作源码去解释。也就是所谓的一般规则：数值可能会改变，但是位模式不变。在C语言中创建一个无符号常量需要在末尾加上后缀字符’U’或者’u’。

​ 一个整数的位是确定的，若想对其位进行扩展，则无符号为零扩展，也就是在开头补零，补齐扩展的位数即可。而有符号数因为是补码表示，所以其扩展是符号扩展也就是在表示中添加最高有效位的值来补足扩展的位数，逻辑类似于算术右移，即正数同零扩展，负数时扩展位补1。当我们想减少一个数字的位数时，对于无符号数则直接截断，截断有符号数，即补码数则在截断后需将最高位转化为符号位。

2.3 整数运算

​ 首先是加法。无符号数加法直接相加，但若出现溢出情况则是用相加结果减去2^Ω^（Ω为位数）。模数加法形成了一种数学结构，称为阿贝尔群（Abelian group）, 这是以丹麦数学家 Niels Henrik Abel(18021829) 的名字命名。也就说，它是可交换的（这就是为什么叫”abelian“的地方）和可结合的。它有一个单位元 0, 并且每个元素有一个加法逆元。让我 们考虑 w 位的无符号数的集合，执行加法运算+^u^w对于每个值 x， 必然有某个值-^u^w~ 满 足 -^u^w+^u^w=0。若是补码加法则需要讨论正溢出和负溢出的情况，正溢出同无符号数加法，负溢出则是用相加结果加上2^Ω^（Ω为位数），其实想想是一样的。

​ 补码的非也就是对每一位求补在加一，也就是相反数的转换。

​ 对于乘法来说，很容易出现溢出，也就是对于一个Ω位的数可能乘法结果需要2Ω的位数才能表示，这种时候计算机会使用低Ω位来作为结果。对于有符号数乘法溢出的情况，则是将这个数先模2^Ω^，也就是阶段为Ω位，再把无符号数转换为补码。

​ 当乘以常数时，计算机为了提高效率，减少执行所需的时钟周期，会使用移位和加法运算的组合来代替乘以常数因子的乘法。举个例子就明白了：比如算式为x * 14，14 = 2^3^ + 2^2^ + 2^1^,而二的指数运算可以通过对一进行左移来完成，这样就算短了执行所需的时钟周期。而除法里除以二的幂则会使用右移，无符号数使用逻辑右移，有符号数使用算术右移。关于舍入的化都是舍入到零，也就是正数向下舍入，负数向上舍入。

2.4 浮点数

​ 浮点数为何叫浮点数是因为他的值是近似来的，所以漂浮不定。学习浮点数一定要牢记IEEE 浮点表示。我们可以通过科学计数法来理解这种表示方式，一个十进制数比如12345，它用科学计数法表示是1.2345 * 10^4^，同理对于二进制小数比如1001.001，用科学计数法来表示就是1.001001 * 2^3^，IIEEE 浮点标准用这样的形式来表示一个数。

    * 符号（sign) s 决定这数是负数（s=l）还是正数（s=0），而对于数值 0 的符号位解释作为特殊情况处理。
    *  尾数(significand) M 是一个二进制小数，它的范围是 1~2-e，或者是 0~1-e。 
    * 阶码（exponent) E的作用是对浮点数加权，这个权重是 2 的 E次幂(可能是负数)。

​ 在单精度浮点格式（C 语言 中的 float)中，s、exp 和 frac 字段分别为 1 位、k=8 位和n=23 位，得到一个 32 位的 表示 。 在双精度浮点格式(C 语言中的 double)中，s、exp 和 frac 字段分别为 1 位、k=11 位和n=52 位，得到一个 64 位的表示。

​ 表示一个数用该精度的偏置加上科学计数法的指数去填充阶码，再加上符号位和小数部分即可组成该数的IEEE 浮点表示。

​ 浮点表示中分为规格化和非规格化的数值，也就是阶码是否为零，阶码为零实际上也是给我们带来一种新的对于+-0.0的表示方式，去在需要做区分的时候区分。当阶码全为一，尾数部分为0时，则表示INF（无穷），根据符号位确定是正无穷还是负无穷。当阶码全为一，尾数部分非零时则表示NaN，表示未定义或不可表示的值。

​ 浮点数有四种舍入方式，向偶数舍入，向零舍入，向下舍入，向上舍入，向偶数舍入就是除开正常舍入，中间值向偶数（整数）舍入。

​ 在浮点运算中，要不断考虑溢出的情况，也要考虑舍入造成的精度的丢失。在位模式中，规格化非规格化，NaN，无穷都是需要讨论的地方，这在DataLab中都有具体的实现。

小结

​ 本篇正如它的标题一样介绍了计算机如何表示和处理信息。阅读此章节也是系统性的回顾了自己在逆向过程中所遇到过的一些问题：比如两正数相乘得到了一个负数，将浮点数强制类型转换成整数，数值发生很大的变化等等。这都是因为计算机对不同的数据类型有不同的存储方式，比如有符号数使用补码存储、字符串使用ASCII码记录，并且使用'\x00'去截断来代表字符串结尾、浮点数使用IEEE 浮点表示等等。而对于一个数来说，它所能表示的最大位数是固定的，所以在处理的过程中肯定避免不了结果超出位数的情况，那就需要对溢出情况进行处理。而当我们需要改变它能表示的最大位数时，也需要对原来的数值进行处理。

​ C语言出了提供基础的运算外，也提供位运算、逻辑运算还有移位运算（虽然计算机是以字节为单位操作的，但是C语言提供的运算符可以直接操作位，来更精细化地达到我们想要地效果）。这些运算不仅帮助我们实现了更多的功能，也可以帮助计算机增加计算效率：通过位运算等这些消耗较少时钟周期地运算符来代替乘除运算等，这在以后地编程中也可以有所运用，因为效率是程序工作所需要注意地一个很重要地方面。

​ 本篇中最拗人的就是浮点数的部分，因为首先浮点数的表示就是反常理的，因为IEEE 浮点表示是一个使用类似科学计数法的方式。并且浮点运算只有有限的范围和精度，而且并不遵守普遍的算术属性，所以使用浮点运算必须非常小心，若发生错误，务必在位模式下，根据浮点数的表示方式和性质理性的分析错误产生原因。

DataLab

CSAPP第二章：信息的表示和处理

bitxor

题目要求：

  • bitXor - x^y using only ~ and &
  • Example: bitXor(4, 5) = 1
  • Legal ops: ~ &
  • Max ops: 14
  • Rating: 1

答案：

1
2
3
int bitXor(int x, int y) {	
  return ~(x&y)&~(~x&~y);
}

思路：

题目要求用&和~两个位运算符来实现异或，则需先理解异或运算。我认为异或运算实际上是在用1标记二者的不同位。我们再来看与运算，实际上是保留相同位的值，值不同的位取0，那么我们使用非运算将其取反，则可以用0去标记同为一的位，其余位为1。而将两个操作数取反进行与运算，则跟之前相反，相同位取反，不同位仍取0，再使用非运算，这样的话原本两操作数中的同为零的位置就被0标记了，其余位为1。这样两个与非运算得到的结果互相对比可以发现，同一和同零的位置，标记是相反的，只有不相同位标记都为一。二者与运算则只会保留标记为1的不同位，就实现了异或运算。

tmin

  • tmin - return minimum two’s complement integer
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 4
  • Rating: 1

答案：

1
2
3
4
5
int tmin(void) {

  return 0x1<<31;

}

思路：

题目要求也就是返回最小的二进制补码整数。二进制补码最高位为符号位，那么最小的二进制补码就是符号位为1，其他位置全零。所以只需要右移运算将1移至最高位即可。补码的负数表示是符号位取一，其他位置取反，再加一，所以其他位置是全零。由之前的知识也可以体现，补码的范围是**[-intmax-1,intmax]**。

isTmax

  • isTmax - returns 1 if x is the maximum, two’s complement number,
  • and 0 otherwise
  • Legal ops: ! ~ & ^ | +
  • Max ops: 10
  • Rating: 1

答案：

1
2
3
4
5
6
7
8
int isTmax(int x) {
	int i=x+1;
	x=x+i;
	x=~x;
	i=!i;
	x=x+i;
  return !x;
}

思路：

这题其实入手的思路就是题目中描述的返回0，1来代表判断结果，并且允许我们使用!逻辑运算符。说明要通过!来判断非零值来返回布尔变量0，1来实现函数。题目要求判断是否为32为最大二进制补码数。最大二进制补码数为符号位为0，其余位数全一，即01111111111111111111111111111111，我们只需要将其转化成全1，再取反即可通过~来转化成0，然后!x即可返回true，也就是1。所以我们将其加1再加上其本身，即可得到全一。此时取反，再逻辑运算即可完成。但是我们会发现111111111111111111111111111111112也会符合这种情况，所以我们需要排除这种特殊情况。所以我们对x+1进行!逻辑运算，因为111111111111111111111111111111112+1的实际的值并不为零，所以先对此值进行布尔运算，即可规避此种例外。

allOddBits

  • allOddBits - return 1 if all odd-numbered bits in word set to 1
  • where bits are numbered from 0 (least significant) to 31 (most significant)
  • Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 12
  • Rating: 2

答案：

1
2
3
4
5
int allOddBits(int x) {
int mask = (0xaa << 8) + 0xaa;
mask = (0xaa << 16)+mask;
  return !(mask ^ x);
}

思路：

根据他给定的运算符，可知最后肯定还是通过逻辑运算符返回布尔代数来代表判断结果。题目中的示例中已经给出提示：allOddBits(0xAAAAAAAA) = 1。实验要求使用的整数最大不超过0xFF，所以我们使用0xAA构造0xAAAAAAAA这样一个掩码。0xAA的二进制形式是101010102，通过左移相加的方法构造出掩码，用掩码与传入参数进行异或再进行逻辑运算即可。

negate

  • negate - return -x
  • Example: negate(1) = -1.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 5
  • Rating: 2

答案：

1
2
3
int negate(int x) {
  return ~x+1;
}

思路：

负数的补码就是他的正数形式的二进制码各位取反再加一，符号位填一。正数的符号位是零，符号位填一和取反是一样的。反过来同理。

isAsciiDigit

  • isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters ‘0’ to ‘9’)
  • Example: isAsciiDigit(0x35) = 1.
  •        isAsciiDigit(0x3a) = 0.

  •        isAsciiDigit(0x05) = 0.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 15
  • Rating: 3

答案：

1
2
3
4
5
6
7
8
int isAsciiDigit(int x) {
	int negative_minimum = ~0x30 + 1;
	int negative_maximum = ~0x39 + 1;
	negative_minimum = (negative_minimum + x)>>31;
	negative_maximum = (negative_maximum + x)>>31;
	return !(negative_minimum^negative_maximum);
  return 2;
}

思路：

题目要求验证参数是否处在’0’~’9’之间，所以我们只需构造上下界的相反数与参数相加通过位运算取符号位异或判断是否相同即可。

conditional

  • Example: conditional(2,4,5) = 4
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 16
  • Rating: 3

答案：

1
2
3
4
5
int conditional(int x, int y, int z) {
	x = !!x;
	x = ~x + 1;
	return (x&y)|(~x&z);
}

思路：

此题让我们模拟三目运算符，判断参数x是否为0。那么最简单用于判断的方式即是使用逻辑运算符!返回0或1。该函数是要根据0，1返回参数y或者z中的一个。很容易想到通过全零和全一来与y，z进行与运算。全一与y与运算可以保留y，那么他的非去和z与就可获得全零的结果，两式通过|关联起来即可。所以在逻辑运算符!返回运算结果后，我们通过补码的原理使其转换成相反数，返回1则转换成-1，也就是全一，返回0则转换成0，即全零。再用先前提到的与或运算构造返回值即可。

isLessOrEqual

  • isLessOrEqual - if x <= y then return 1, else return 0
  • Example: isLessOrEqual(4,5) = 1.
  • Legal ops: ! ~ & ^ | + << >>
  • Max ops: 24
  • Rating: 3

答案：

1
2
3
4
5
6
7
8
9
int isLessOrEqual(int x, int y) {
	int negative = ~x + 1;
	int plus_result = negative + y;
	int sign = (plus_result>>31)&1;
	int sign_diff_x = (x>>31)&1;
	int sign_diff_y = (y>>31)&1;
	int sign_diff = sign_diff_x^sign_diff_y;
	return (sign_diff&((x>>31)&1))|((!sign_diff)&sign);
}

思路：

既然是大小判断，那肯定少不了分类讨论：同号和异号。同号情况很好讨论，我们只需要取反对x相加即可。若异号的话，那么需要对符号位进行异或判断，一定是正数大。所以用异或判断的结果和x的符号位与运算即可讨论完成异号的情况。当然，判断是否异号的那个变量要当作一个因子类似的东西，同样要去参加对同号情况的讨论，在异号时，!因子为零，与讨论同号的式子与运算即可直接在异号时无视同号情况的讨论。

logicalNeg

  • logicalNeg - implement the ! operator, using all of 
  •          the legal operators except !
  • Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
  • Legal ops: ~ & ^ | + << >>
  • Max ops: 12
  • Rating: 4

答案：

1
2
3
int logicalNeg(int x) {
  return ((x|(~x+1))>>31)+1;
}

思路：

!是用来判断是否为零，为零返回一，非零返回零。一个非零的数，非负即正，那么他和他的相反数一定为0和1，那么两者或运算再左移取符号位一定为-1，再加一即可返回零。零与零的相反数符号位都是0，所以加一返回一。

howManyBits

  • howManyBits - return the minimum number of bits required to represent x in

  •         two's complement

  • Examples: howManyBits(12) = 5

  •        howManyBits(298) = 10

  •        howManyBits(-5) = 4

  •        howManyBits(0)  = 1

  •        howManyBits(-1) = 1

  •        howManyBits(0x80000000) = 32

  • Legal ops: ! ~ & ^ | + << >>

  • Max ops: 90

  • Rating: 4

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int howManyBits(int x) {
	int c0,c1,c2,c4,c8,c16;
	int sign = x>>31;
	x = (sign&~x)|(~sign&x);
	c16 = (!!(x>>16))<<4;
	x = x>>c16;
	c8 = (!!(x>>8))<<3;
	x = x>>c8;
	c4 = (!!(x>>4))<<2;
	x = x>>c4;
	c2 = (!!(x>>2))<<1;
	x = x>>c2;
	c1 = !!(x>>1);
	x = x>>c1;
	c0 = x;
	return (c0+c1+c2+c4+c8+c16+1);
}

思路：

该函数实现的功能是返回表示传入参数的最小二进制位数。也就是数值位加1（符号位）。我们的思路是使用二分查找法去找除开符号位为一的最高位。但是由于补码的特性，我们并不是很容易实现。所以我们先要对负数按位取反，正数保持不变。所以我们构造sign = x>>31去记录符号位。用与非运算，构造出当正数时不变，负数时按位取反的算式：x = (sign&~x)|(~sign&x)。接下来按步实施二分查找。先确定最高位是在高16位还是低16位，最高位确定落在任意一16位区间后，在确定是落在高八位还是第八位。范围不断缩小。最后将记录的位数相加再加上符号位所占的1即可。

floatScale2

  • floatScale2 - Return bit-level equivalent of expression 2*f for
  • floating point argument f.
  • Both the argument and result are passed as unsigned int’s, but
  • they are to be interpreted as the bit-level representation of
  • single-precision floating point values.
  • When argument is NaN, return argument
  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 30
  • Rating: 4

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned floatScale2(unsigned uf) {
	int index = (uf&0x7f800000)>>23;
	int sign = uf&(1<<31);
	if (index == 0)
	{
		return uf<<1|sign;
	}
	if (index == 255)
	{
		return uf;
	}
	index++;
	if (index == 255)
	{
		return sign|0x7f800000;
	}
  return (index<<23)|(uf&0x807fffff);
}

思路：

浮点数这边有很多的分类讨论。首先对于规格化的浮点数，我们只需要对其阶数加1，再与齐其他部分组合即可完成乘二操作。但若加一是无穷大，则需要将其小数部分清楚返回无穷大。对于非规格化的浮点数只需要左移一位即可。若输入为NaN则也需单独判断阶码是否全为1，返回NaN。

floatFloat2Int

  • floatFloat2Int - Return bit-level equivalent of expression (int) f
  • for floating point argument f.
  • Argument is passed as unsigned int, but
  • it is to be interpreted as the bit-level representation of a
  • single-precision floating point value.
  • Anything out of range (including NaN and infinity) should return
  • 0x80000000u.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
  • Max ops: 30
  • Rating: 4

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int floatFloat2Int(unsigned uf) {
  int sign = uf>>31;
  int exp  = ((uf&0x7f800000)>>23)-127;
  int frac = (uf&0x007fffff)|0x00800000;
  if(!(uf&0x7fffffff)) return 0;

  if(exp > 31) return 0x80000000;
  if(exp < 0) return 0;

  if(exp > 23) frac <<= (exp-23);
  else frac >>= (23-exp);

  if(!((frac>>31)^sign)) return frac;
  else if(frac>>31) return 0x80000000;
  else return ~frac+1;
}

思路：

首先考虑特殊情况：如果原浮点值为0则返回0；如果指数大于31的话，frac部分是大于等于1的，所以1<<31位就会覆盖符号位，返回规定的溢出值0x80000000；如果 exp<0，说明该浮点数整数部分为0，所以返回0。剩下的情况：把小数部分转化为整数，大于23则左移，小于23则右移。然后异或判断是否溢出：如果和原符号相同则直接返回frac，否则如果符号位为一说明为负，与原数符号相反，则原数为正值，符号位为0，说明溢出改变了符号位，所以返回越界规定的溢出值0x80000000，再否则原来为负，结果为正，则需要返回其相反数（因为我们在生成frac的时候对符号做了处理，为了方便接下来浮点数向整数的转换）。

floatPower2

  • floatPower2 - Return bit-level equivalent of the expression 2.0^x
  • (2.0 raised to the power x) for any 32-bit integer x.
  • The unsigned value that is returned should have the identical bit
  • representation as the single-precision floating-point number 2.0^x.
  • If the result is too small to be represented as a denorm, return
    1. If too large, return +INF.
  • Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
  • Max ops: 30
  • Rating: 4

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned floatPower2(int x) {
  int INF = 0xff<<23;
  int exp = 127+x;
  if (exp <= 0)
  {
    return 0;
  }
  if (exp>=255)
  {
    return INF;
  }
  return exp<<23;
}

思路：

让我们求2.0^x^,先来看2.0的位级表示，2.0可以看作2.0^1^阶码为127+1，frac部分舍去1是全零，也就是说，处理2.0^x^我们只需要改变阶码，并对阶码exp做溢出一类的判断即可。若exp<=0则返回0，因为当等于零时值就已经为零了。当exp>=255时，满足无穷大或溢出条件，返回+INF。这些判断都不满足，那么直接对构造好的阶码进行移位即可。

小结

DataLab整个实验是在感受位运算的强大，通过位运算代替我们从小学到大的那些基本运算符，实现逻辑判断，最小表示位统计等功能。在读CSAPP第二章时多少都有些磕磕绊绊，看不懂的或者看漏的可能都一眼带过了，通过实验，加强理解和运用。做实验一定要不断翻书，做题目中没有的思路，可能就是看书遗漏的点，反复翻阅，巩固细碎的知识。做实验卡壳的时候也去翻阅了很多别人写的博客，别人写的思路自己也要理解半天，但是做完了回过头来看，也能发现这东西会者不难难者不会，通过做实验去锻炼自己的位级运算的思维，计算机的学习必须需要从以前的十进制运算思维转换成二进制中对位级的运算思维。之后的实验一定要加强自己思考的过程，加深理解。

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2022-2023 Syclover.Kama
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信