本文首发于CSDN，同步到博客园

深入理解计算机系统第二章

2.1 信息的存储

• 十六进制转二进制，将十六进制的每一位转换成一个4位的二进制
  即：\([0123456789ABCDEF]_{16}\) 对应 \([0000-1111]_2\)
• 每台计算机都有一个字长\((word\ size)\)，对于一个字长为\(w\)位的机器，虚拟地址范围为\([0,2^w-1]\)
  程序最多可以访问\(2^w\)个字节
• 在当前大规模从32位字长机器到64位字长机器的迁移情况，大部分的64位字长机器都向后兼容了32位字长机器。当程序prog.c用伪指令linux> gcc -m32 prog.c编译后，该程序就可以在32位或64位机器上正确运行。而当程序prog,c用伪指令linux> gcc -m64 prog.c编译后，该程序只能在64位机器上运行。区别32位和64位程序，区别在于程序是如何编译的，而不是其依赖运行的机器类型。
• 信息的存储方式，以in a = 4666;为例，a的大小为4个字节，二进制表示为0001 0010 0011 1010，十六进制表示为0x123a。
  有效字节从低到高依次为a,3,2,1，这些字节在机器上的存储是连续的，如果最低有效字节a存储在内存地址更高的地方，那么这称为大端（高尾端）。反之最低有效字节a存储在内存地址更低的地方，这称为小段（低尾端）。
  至于大端和小端的机器，Linux32, Windows
  
• 如何打印出一个数的具体存储格式

/*
author: solego
*/
#include
using namespace std;

typedef unsigned char* byte_pointer;
void show_bytes(byte_pointer start, int len) {
	for(int i = 0; i < len; ++i) {
		printf("%x\n", start[i]);
	} printf("\n");
	
int main()
{
	int x = -10;
	/*
		expect: 0x ff ff ff f6
			x(sign magnitude)   = 10000000 00000000 00000000 00001010
			x(one's complement) = 11111111 11111111 11111111 11110101
			x(two's complement) = 11111111 11111111 11111111 11110110
		   10(two's complement) = 00000000 00000000 00000000 00001010
	*/
	show_bytes((byte_pointer) &x, sizeof(x));
	return 0;
}

result:
f6
ff
ff
ff

由此可以看出来，在计算机中存储的是补码，循环是从低地址到高地址的，而优先输出最低有效字节，所以windows采用的是小端（低尾端），这里利用unsigned char大小为\(1\)字节，恰好表示出[0,255]。

• 关于位运算，值得一谈的是逻辑移位和算术移位。

数据类型	移位方向	移位方式
无符号数	左移	逻辑移位，补0
有符号数	左移	逻辑移位，补0
无符号数	右移	算术移位，补0
有符号数	右移	算术移位，负数补1，其余补0
左移采用逻辑移位，无符号数的右移采用逻辑移位
有符号数采用算术右移，负数右移左补1，其余右移左补0，这也是对应满足补码运算的。

---

2.2 整数的表示

• 计算机中的整数都是以补码形式存在的
  原码，反码和补码：

  将一个数的补码看成向量，向量的每一位为其二进制值，一个\(w\)位的向量，则有：

  对于非负数和无符号数，\(\sum_{i=0}^{w-1}x_i{2^i}\)，
  对于负数：其最高位的位权是\(-2^{w-1}\)，即\(x^{w-1}\times(-2^{w-1})+\sum_{i=0}^{w-2}x_i{2^i}\)

  这样来看，就能很好的解释\(1000\ 0000\)表示的是\(-2^7\)而非\(-0\)了。

  以\(8\)位为例
  对于有符号数：

  • 正数：符号位为\(0\)，\([0000\ 0000,0111\ 1111]\) 即\([0,2^7-1]\)
  • 负数：符号位为\(1\)，\([1000\ 0000,1111\ 1111]\) 即\([-2^7,-1]\)

• 位数相等的 有符号数和无符号数之间的互相转换

  short int a = -12345;
  unsigned short b = (unsigned short) a;
  printf("a = %d, b = %u", a, b);
  
  result:
  a = -12345
  b = 53191
  

  以上例子中short和unsigned short均为2字节，即16位

  -12345: 1100 1111 1100 0111
   53191: 1100 1111 1100 0111
  

  可以发现两者的补码是一致的，可以理解为解释这些二进制位的方式变了
  对于有符号数，最高位解释为符号位，同时最高位是\(-2^{15}\)，而对于无符号数，最高位解释为普通的位，即为\(2^{15}\)。

  关于\(w\)位的有符号数到无符号数的映射
  如果有符号数的符号位为\(0\)，那么解释不变
  如果有符号数的符号位为\(1\)，那么在解释成无符号数时，该位就是一个普通的位。
  具体到十进制来看：

\[ SToU(x)=\left\{ \begin{aligned} x,x\geq 0\\ x+2^w,x<0\\ \end{aligned} \right. \]

这是因为将负数的符号位由$-2^{w-1}$解释为$2^{w-1}$是相差了$2^w$的，而将非负数转换成无符号数，符号位无影响。

从无符号数转换成有符号数：

\[ UToS(x)=\left\{ \begin{aligned} x,x\leq 2^{w-1}-1\\ x-2^w,x\geq 2^{w-1}\\ \end{aligned} \right. \]

• 在有符号数和无符号数进行运算时，有符号数会被强制转换成无符号数来执行运算

  int a = -1;
  unsigned int b = 0;
  if(a < b) printf("a < b\n");
  else printf("a > b\n");
  
  result:
  a > b
  这里的signed int a被强制转换成了(unsigned int a)，即a = 2^32 - 1
  

• 将位数不相等的整数类型转换

  • 从字节少的强制转换成字节多的，扩展的为高位，原有的部分为低位
    对无符号数的扩展是零扩展，在扩展的数位上补0即可
    对有符号数的扩展是符号位扩展，即在扩展的数位上补符号位

    对于数据的强制类型转换，是不可改变其所表示的值的。

    int a = -1;
    long long b = a;
    a: 1111 1111 1111 1111 1111 1111 1111 1111
    b: 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
    

    需要证明这两种补码得到的结果是一样的。
    我们考虑一种简单的情况：

    a 为4位的-1，b 为5位的-1，c 为6位的-1
    a: 1111 = -2^3 + 2^2 + 2^1 + 2^0
    b: 1 1111 = (-2^4 + 2^3) + 2^2 + 2^1 + 2^0 = -2^3 + 2^2 + 2^1 + 2^0
    c: 11 1111 = (-2^5 + 2^4 + 2^3) + 2^1 + 2^0 = -2^3 + 2^2 + 2^1 + 2^0
    
    因此c = b = a，扩展到更高位依然是正确的
    对于正数来说，扩展的符号位为0，显然是不会影响结果的。
    

  • 从字节多的强制转换成字节少的，则是保留低位，直接去除高位，这样是可能改变实际值的
    对于无符号数是直接去除高位即可
    对于有符号数，先用无符号数解释，然后直接去除高位，再用有符号数来解释

    long long b = -1ll << 32;
    cout << b << "\n";
    
    int a = (int)b;
    cout << a << "\n";
    
    result:
    -4294967296
    0
  

---

2.3 整数的运算 加（减）法

• 无符号数加法 \(0\leq x < 2^w, 0\leq y<2^w\)

\[ x+y=\left\{ \begin{aligned} x+y,x+y< 2^{w}\\ x+y-2^w,x+y\geq 2^w\\ \end{aligned} \right. \]

大于等于\(2^w\)相当于溢出，溢出的部分全部被舍弃，只保留\([0,w)\)位，相当于对\(2^w\)取模，因为这里\(x+y\)的范围是\([0,2^{w+1}-2]\)，最多只会在第\(w\)位上有权，所以减去\(2^w\)即可。

判断溢出

	bool add_ok(unsigned x, unsigned y) {
		unsigned sum = x + y;
		return sum >= x;
	}
	
	证明：
	数学方面来看：
	x + y >= x, x + y >= y
	发生溢出时：
	sum = x + y - 2^w
	因为 y < 2^w
	所以y - 2^w < 0
	所以 x + y - 2^w < x
	
	对于y是同理。

• 有符号数加法，分为正溢出，即两个正数相加的结果溢出，以及负溢出，即两个负数相加的结果溢出
  \(-2^{w-1}\leq x\leq 2^{w-1}-1, -2^{w-1}\leq y\leq 2^{w-1}-1\)

\[ x+y=\left\{ \begin{aligned} x+y-2^w,x+y\geq 2^{w-1}\\ x+y,-2^{w-1}\leq x+y< 2^{w-1}\\ x+y+2^w,x+y< -2^{w-1}\\ \end{aligned} \right. \]

	对于正溢出：
	两个二进制正数 127和1：
	0111 1111
	0000 0001
	----------
	1000 0000
	
	对于负溢出：
	两个二进制负数 -128和-1
	   1000 0000
	   1111 1111
	----------
	(1)0111 1111
	
	无论是哪种：
	都可以用无符号数来解释他们，然后进行无符号数的加法
	得到结果后，再进行无符号数到有符号数的转换
	
	唯一的问题是：在解释负溢出时，得到了(w+1)位，解释成有符号数则是一个(w+1)位的有符号数，
	而我们是舍弃溢出不部分的，所以需要加上这部分，即2^w

• 加法逆元
  对于整数\(x\)，使得\(x+x'=0\)的\(x'\)就是\(x\)的加法逆元，也可以称为相反数

  • 无符号数的加法逆元
    \(0\leq x< 2^w,0\leq x'<2^w\)
    这里要涉及到溢出求逆元了，当第\(w+1\)位为\(1\)，其余均为\(0\)，特殊的是当\(x=0\)，\(x'=0\)
    否则\(x'=2^w-x\)

\[ x'=\left\{ \begin{aligned} x,x=0\\ 2^w-x,x>0\\ \end{aligned} \right. \]

• 有符号数的加法逆元
  当\(x>-2^w\)，那么对应的\(x'=-x\)
  当\(x=-2^w\)，那么对应的\(x'=x\)

\[ x'=\left\{ \begin{aligned} x,x=-2^w\\ -x,x>-2^w\\ \end{aligned} \right. \]

2.3 乘除法

• 乘法
  先做位扩展，因为两个\(w\)位的数相乘，结果是\(2w\)位的，所以需要先符号位扩展，将两者均扩展到\(2w\)位，然后进行计算，最后截取低\(w\)位即可

  如 5[101] 和3[011]
  先符号位扩展得到：5[000101]和3[000011]
  再计算
  		000101
  		000011
  ---------------
  		000101
  	   000101
  	  000000
  	 000000
  	000000
     000000
  ---------------
   00000|001111
  
  再如-3[101] 和 3[011]
  先符号位扩展得到：-3[111101]和 3[000011]
  		111101
  		000011
  ---------------
  		111101
  	   111101
  	  000000
  	 000000
  	000000
     000000
  ---------------
   00000|110111