【CSAPP】笔记-Cp2-1-信息存储

CSAPP（深入理解计算机系统）第二章“信息的表示和处理”第一部分“信息存储”的笔记和课后习题。
Github的同步工程在这

计算机本质上是开关电路，底层就是MOSFET等的打开、关断和饱和为基础所构成的一系列变化，“开”和“关”可以抽象为0和1两种状态，计算机中的一切都是有0和1构成的，信息的存储也不例外。

信息在计算机中以0和1的系列表示，再高一点就是bytes序列，不过没有本质区别。单纯的0、1序列没有任何意义，意义是我们所赋予的，我们人为地定义一些数据类型，再通过这种定义01序列转义，便可以使它们表现出具体的含义。

比如，1111这个二进制数，如果是无符号整形，它代表15，如果是有符号整形，则是-1，如果是定点位为3的定点数，则是7.5。
同时，这种由4个bit构成的一个数，其值域为0~15，是一个十六进制数，十六进制数在计算机中十分重要。

一般来讲，有符号数用补码表示，小数由浮点数表示，不过在一些特殊的领域，比如FPGA，定点数使用地更为广泛，定点化问题也是值得关注的。

原始数据类型

和代数定义基本相同，可以分为：

整数： 有符号整数和无符号整数，在C中，可以按照位宽分为很多类型，有8bits的char，有32bits的int，也有64bits的int等，但它们都遵循一个规则。

小数： 在计算机软件中，小数都是有符号的，也可以根据位数进行划分，在C中，有32bits的float，有64bits的double等。

注：在C中，指针本身定义为一个全字长的变量。其它详见下面几节。

溢出和误差

溢出是指——运算结果的大小超越了该类型的数所能表示的最大值。比如对于一个无符号char型变量，如果给他赋予一个超过255的值，则发生了溢出，结果会被截断（当然有的编译器会发现这个错误）。

误差则是指浮点数和定点数系统的有限，对于整数，总是存在一个二进制数可以作为十进制数的对应，但对于小数或者分数则并非如此，例如0.2这个数，你就无法找到一个二进制的数来表达他，只可能在有限的精度下非常接近它。

总而言之，整数在计算机中是有限但精确的，而小数是无限却近似的。

指针

指针提供了引用数据结构的元素的机制，它指向某个存储块的第一个字节的虚拟地址。
指针包含一个值和一个类型，值就是指向对象的地址，而类型则是对象的类型。

在C中，用T *p定义一个名为p的指针，T可以使任意基本的数据类型，用p可以获取p的首字节地址，*p可以直接获取该变量。而使用&可以获取任何一个变量的首字节地址，它返回一个指针变量，如果定义的是一个int型指针变量，那么p指向的对象实际占据的地址空间就是p、p+1、p+2和p+3。
根据不同的系统，这四个字节的排序各有不同。低字节在前的称为小端LE，反之则为大端BE，这可能是一个坑，要注意。

比如&p=0x100，则同时p指向的对象为int型，表示0x01234567，则： 1. 大端表示，0x100 ~ 0x103地址分别为 0x01 ~ 0x67。 2. 小端表示，0x100 ~ 0x103地址分别为 0x67 ~ 0x01。

一般来说，x86 系列 CPU 都是 little-endian 的字节序，PowerPC 通常是 big-endian，网络字节顺序也是 big-endian还有的CPU 能通过跳线来设置 CPU 工作于 Little endian 还是 Big endian 模式。

指针的引用可以用数组表示法来表示，比如对于int *p，p[1]取得是&p后1*4个字节开始的int型变量，和数组的使用十分相似。 指针的只允许被赋值指针型变量，也就是一个&返回的一个变量的地址或者由*定义的数据。

char *p;
char i = 10;
p = &i;
printf("%d", p[0]);
printf("%d", *p);

结果都是10。

强制类型转换

cast，强制类型转换，可以将一个类型的数据以另一种类型的形式表现出来。在系统编程中极为重要。

void show_as_float(int p){
    printf("%f", (float) p);
}

位宽

处理器位宽决定了虚拟存储器的寻址范围，n位的寻址范围是 2ⁿ。

sizeof(T)函数可以给出当前系统中，类型T占据的字节数。由于不同系统对各种基本类型赋予的位宽可能不同，为了避免麻烦，在c++中应尽量使用stdint包中的uint_8t等类型。

字符串

字符串也是对二进制流的一种编码，它被编码为一个以null(值为0)字符结尾的字符(char)数组。每个字符都需要指定编码，常见的为ASCII码，当然，多用unicode，善待程序员（对Python我就是在说你）。

逻辑运算与位运算

逻辑运算是布尔代数中的一部分，基本包括与预算、或运算、非运算、异或运算，可以用于进行一些基本的逻辑运算。这也是数字电路的基础，其实很简单。
逻辑运算也有各种运算定律、化简方法（卡诺图）等，可以自行研究。

一般的，在软件中，逻辑运算通常有两种，单目运算&等和双目运算&&等，前者是位运算，返回原始类型的值，后者是逻辑运算，返回逻辑值。所以单目运算符常常可以被用于位屏蔽和掩码等，比如0xff & 0x0f就屏蔽了前者的前四位。

除以上，还有一种位相关的操作，被称为移位操作，移位操作一般分为逻辑移位（无符号扩展）和算数移位（有符号扩展），也有被称为循环移位的存在但不在此讨论。移位即将一个二进制数的所有位向左或向右平移若干位，他可以用于替换一些特殊的乘除法，速度快很多。比如除以二可以用左移两位表示。

需要注意的是，在C中，如果移动的位数超过了字长w，可能会造成类似循环移位的异常状况，所以要尽量避免。

一般情况下，加减乘除逻辑运算位运算移位操作都可以直接对应为CPU的一条指令。

习题

所有有代码的练习都以以题号为名字的单个文件内。

代码位于CSAPP-Chapter2内。

1，2，3，4，

略过。

5

A：
BE -> 0x87
LE -> 0x21

B:
BE -> 0x8765
LE -> 0x2143

C:
BE -> 0x876543
LE -> 0x214365

6

这实际上是浮点数和整形的模型问题，略过。

7

为各个字符对应的ascii码，略过。

8

基本逻辑运算，略过。

9

颜色的补就是把每一位取反，B是基本逻辑运算，略过。

10

异或运算满足自反率：

$$A \oplus A \oplus B = B$$
$$A \oplus B \oplus B = A$$

11

原来函数只能对偶数个数元素的数组工作，是因为对于奇数个数元素的数组，会出现first = last的状况，这种状况下实际上是数组中间的元素自己和自己做运算，即inplace(&a[first], &a[first])，此运算将返回0。
返回0是因为以上三步运算中，步骤1使得a = a, b = 0，步骤2使得a = a, b = a，步骤3使得a = a, b = 0，由于inplace函数的两个参数指向同一个元素，所以对b赋值的结果会覆盖对a的赋值，所以结果为0。
如何改动请见代码，将奇数作为特殊情况即可，也就是，将first <= last改为first < last。

12

// A
x & 0x000000ff
// B
x ^ 0xffffff00
// C
x | 0x000000ff

13

本质上：

bis(x, y) = or(x, y)
bic(x, y) = and(x, ~y)

int bool_or(int x, int y){
    return bis(x, y);
}

可以用逻辑代数通过or求得xor：

xor(x, y) = or(and(x, ~y), and(y, ~x))

int bool_xor(int x, int y){
    return bis(bic(x, y), bic(y, x));
}

14

基本运算，略过。

15

详见代码。

16

基本运算，略过。