chapter 2

c语言是如何诞生的？

因为早起在使用Unix时，为了访问不同数据类型的低级表示，都必须使用大量的汇编代码（如c的malloc库函数分配内存功能），因此开发出c来和Unix一起使用。下图展示了c版本的迭代：

GNU：GNU‘s not Unix

gcc：GNU compiler collection（依照不同的c语言版本来进行hello.c——>hello的转化）

2.1信息的储存

大多数的计算机使用8位的块（1个字节）来作为最小可寻址内存单元，机器级程序（一个进程）将内存视为一个非常大的字节数组（见下图），每个进程都有自己的虚拟地址空间（将内存中的每个字节都用地址来标明）。

2.1.1 16进制表示法（Hexadecimal Notation）

为什么要使用16进制？

一个字节为8位，如果用二进制来描述位模式就太长，而10进制和二进制位模式的转化又太麻烦（比如 1111 我就可以表示为F而不是15）。

2进制和16进制之间的转化：

诀窍一：记住ACF的10进制

诀窍二：记住1111 的每一位为 1 2 4 8

10进制和16进制之间的转换

诀窍三：10进制转化为16进制的特殊情况（要求为2^n型）处理

诀窍四：10进制转化为16进制的一般情况：–辗转相除法

诀窍5:16进制转化为10进制

2.1.2字数据大小（Data Size）

word用来表示什么？

1.word可以用来表示指针数据的标称大小（nominal size），它与计算机系统是多少位字长的机器有关。

2.因为虚拟地址就是用一个字（32位机器一个字就是2）来编码的：比如32位机器，就可以有2^32个地址值，每个地址值都指向虚拟空间的一个字节；所以字 长决定了虚拟地址空间的最大大小（virtual address space）

3.对于字长为w的计算机而言，虚拟地址的范围就是0-2^w-1，单位长度为字节。

32位机器的虚拟地址空间为4GB 64位为16EB（1.84X10^9字节）

32位机器和64位机器的区别与联系？

1. 向后兼容 - 64位机器是可以处理32位机器编译的程序

   比如下面这个命令编译出来的prog可执行文件就可以在32位机器或者64位机器上运行

   

   而下面这个编译出来的可执行文件就只能在64位机器上运行，因为此时的程序将main memory视为一个2^64字节的虚拟地址

   

   2.下图为基本数据类型在不同位机器上的典型字节大小（具保证字节数和典型字节数见2.2），有些数据类型的确切字数依赖于程序是如何编译的。

   

   char：char类型是因为可以存储文本串中的单个字符而得名，但也可以被用来存储整数值，如果char类型要为有符号，用特地声明（加上signed）。

为了避免依赖典型字节大小，C99引入了一类数据大小是固定（不随编译器和机器变化而变化）的数据类型（如int32_t、int64_t等）

​ char*：声明了一个指向char类型对象的指针，使用的是机器的全字长。

为什么从32位机器像64位机器上移植程序会发生错误？

这一错误是对机器字的依赖性引起的，比如将指针存储在一个int型的数据类型中，对于32位来说这是可行的，因为指针大小为机器字大小，int恰好也是4个字节，而当其像64位机器移植时，int还是4个byte而指针已经变为了8个字节。

2.1.3 寻址和字节顺序(Addressing and Byte Ordering)

对于跨越多字节的程序对象（如int 为 4字节），大部分多字节对象都被存储在连续的字节序列，对象的地址为使用字节中的最小地址。

大端法（big endian）与小端法（little endian）：（ox01234567）

有些处理器使用的是大端法，有些处理器使用的是小端法，还有些新处理器使用的是双端法（bi-endian），但这些都是处理器层面上的选择，一旦操作系统确定了，字节的顺序也就固定下来了。

大部分的处理器都使用little enidan

这里的大端小端是是针对不同数据类型所占空间的大小不一样来确定的，比如int占四个字节，所以int一定会有大端小端，而char类型就是1个字节，就没有大小端一说。

下面给出一个查看指针、及任何变量地址的C描述。详情见Clion的Endian2_1_3

这个程序中最重要的是：

1.现在我们用的基本上都是小端的处理器

2.如何找一个指针的地址，及指针的强制转化

​

2.1.5 表示代码

不同的操作系统指令的编码是不一样的，所以不同类型的机器的指令和编码都是不兼容的。

2.1.6 Boolean Algebra

布尔代数的几种运算和C语言的位级运算是匹配的。

逻辑运算 运算符

NOT ～

AND &

OR ｜

EXCLUSIVE-OR ^ 异或

如何将位向量应用到有限集合

位向量定义

a [1101001] [0,3,5,6]

b [1010101] [0，2，4，6]

因此

2.1.7 c语言中的位级运算

位级运算和Boolean运算用相同的特性。

任何进制的位级运算都应该转换为二进制进行运算。

优先级:NOT～>AND&>XOR(exclusive or)^>OR｜

本节介绍了：

1.想要交换两个数的两种方法（指针和使用XOR- exclusive or）–>见2_1_7的code

要点：第一种实现方式较为传统

​ 第二种实现方式不需要局部变量（temp），但其实没用性能优势

2.如何交换头尾两个数 –>见2_1_7的code

要点：

数组在main里面sizeof为28 在minmax里面sizeof为4 –> 得出了如何得到数组length的方法

对于用XOR的switch，为什么不能使得first==last的原因–>说明了*p是什么的重要性

3.深刻理解与或非门的用法

4.或门和非门的真正含义及如何使用与或非门表示异或

2.1.8 C语言中的逻辑运算

逻辑运算和位级运算极易混淆，因为他们的英语符合都一样AND（&&）,OR（||）,NOT(!) ，但是逻辑运算符返回的是True（代表所有非0参数）、False（代表0）

逻辑运算和位运算的区别：

1.在特殊情况下的位运算等价于逻辑运算（如图中第二行～ox00 == 0x01）

2.如果逻辑运算的第一个求值就能确定表达式的结果，那么逻辑运算就不会继续

（如当a=0时 a&&任何东西都为0）

2.1.9 C语言中的移位运算（shift operation）

1.左移位只有一种，就是后面添0

向左移动一位 值变为2倍

2.右移位有两种

• 算术移位 向右移动一位前面补k个最高有效位的值（对有符号整数运算有利）
• 逻辑移位 向右移动一位前面填一个0 值变为原来的一半

（Java：»> logical » arithmetic）

(Java要求移位会按照取模来做 但C中没有保障)

+-法的优先级比移位要高

2.2 整数表示（Integer)

2.2.1 整数数据类型

典型的32位和64位机C语言整形数据的取值范围。

64位机：

C语言标准要求的取值范围：

由此可以看出，标准中要求的正负数的取值范围是对称的（因为其实补码都会兼容它 比如-32,767 在4Byte的补码中TMin为-32,768）

int >=2Byte

long >=4Byte

Java只支持有符号数

2.2.2无符号数的编码

1.Binary to unsigned

脑子里要经常想到这个图

Unsigned Maxmium

Unsigned Minimum == 0

函数Binary to Unsigned是一个双射（一一对应）

2.2.3补码的编码（Two’s- Complement）

目的：为了正负数都能表示

定义：

Two’s Complement 和 Unsigned的位模式是一样的。

Two’s Complement Maximum：

Two’s Complement Mininum：

Binary to Two’s Complement 在TMAX到TMIN是双射。

下图是一些重要的数字：

1.无符号数的最大值和有符号数的-1有相同的Hexideciaml表达

2.补码的范围是不对称的 TMin没有对应的正数（因为一半的位模式表示负数 一半的位模式表示非负数（0和正数））

｜TMin｜=｜TMax｜+1

3.UMax刚好比TMax的两倍大一

UMax = 2TMax + 1

C库中的<limits.h>就给出了各种类型的MAX和MIN

使用宏能保证，无论代码如何编译，都能使用正确的格式(因为宏会去读取当前定义类型（32位还是64位机器定义的）对应的字符保证打印成功)

补码（Two’s complement）分号位置的由来：（这里的2就是2^w中的2）

补码的2和Unsigned的13有相同的位表示

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

同样字长的Two’s Complement和Unsigned之间的转换数值可能会变，但是位模式一定不会变

1.T2U（Two’s Complement to Unsigned）

推导：

现在给出公式并解释上面推论中Xw-1、Uw-1（位模式中的最高位）为什么分别决定了X（补码中的十进制值）和u（无符号数的十进制表示）

1.U2T（u为十进制表示的无符号数）

因为当Uw-1为0时（无符号数中位模式的最高位），转化后的Two’s Complement在当前位模式下也一定是一个正数（u一定小于<=TMax），否则转化为补码后一定为负（因为最高位为1）。

TMax=2^(w-1)-1

2.T2U

因为当Xw-1为1时（带符号数中位模式的最高位为1），表示此时是一个负数，转化后的无符号数后当前位模式下也一定是一个正数且一定大于等于2^(w-1)。

总结：在0-TMax（2^(w-1)-1）之间的无符号和补码相同，其余要加上或者减去一个2^w。

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

C语言中无条件的支持U和T，而且T基本都是以补码的形式出现，如果声明变量或者常量时使用默认（变量比如int 常量比如1234）都表示为有符号数，要声明变量或者常量为无符号数时都要加上u（比如变量unsigned int 常量1234U）

C语言允许无符号和有符号之间的类型转化，且默认的底层逻辑都是位模式不变。

一个有符号数和一个无符号数进行运算就会将两数看成无符号数处理。

TMin常写作（-TMax-1）方便理解。

2.2.6 扩展一个数的位表示

1.无符号数的扩展

2.补码数的扩展

重点：符号扩展不会改变补码的数值

证明扩展一位不会改变即可

2.2.7 截断数字

1.无符号（unsigned）的截断

推导：

2.补码的截断

注意：上图中x=B2U 书里写错了

1.先将补码转化为对应的无符号数

2.对无符号数进行截断

3.获得截断后的无符号数

4.再将无符号数转化为有符号数

两种截断的总结：

2.2.8关于Unsigned 和 Two’s Complement的建议

1.有符号数到无符号的隐式转化（因为算式中只要出现无符号 补码表示的有符号数就会被当作无符号数）容易产生错误

因此使用无符号数时 要注意运算结果是否有可能为负数 如果会出现负数的场合就不能使用有符号数

2.因为c是machine level的语言 不可能说不出现无符号数 因此我觉得在c中使用无符号数的利是远远大于弊的。

3.size_t默认为unsigned（32位 unsigned int 64位 unsigned long）

2.3 整数的运算

了解整数的运算可以写出更加可靠的code。

2.3.1 无符号加法

溢出：完整的整数结果不能放到数据类型的字长限制中

对于无符号的加法，如果加起来的结果大于等于2^w 就会丢弃最高位第（w+1）位，因此要减2^w。

搭配下面两幅图来理解：

无符号数的溢出检测：

无符号数求反：

因为求反的定义为：a+b == 0

在计算机中15再加1就清0，因此定义x在+X下的逆元为下面的式子。

2.3.2补码的加法

因为补码加法可以说是对无符号加法的扩充（见下图 相当于增加了负半轴），因此在机器级别的指令，通常用相同的指令来处理。


补码加法运算：

（巧妙的使用推到过程，不必讨论一个大于0一个小于0的情况）

只有在x y都同时大于0的情况下才会发生正溢出（原因看书）

只有在x y都同时小于0的情况下才会发生负溢出（原因看书）

补码溢出检测：

2.3.3补码的非

为什么x=TMin时，补码的非等于TMin，因为此时TMin+TMin = 0溢出后把最高位划去（第w+1位）

补码非的位级表示:

方式一：

对每一位求非，再将整体结果加一（用Two‘s Complement转换为Decimal）

方式二：

找到最右边的1，对1的右边求非

2.3.4无符号数乘法

2.3.5 补码乘法

Notice：mod运算都转化为positive

无符号乘法和补码乘法的等价性：

2.3.6 乘以常数

通常情况下，整数的乘法需要多个time cycle，因此优化整数的乘法至关重要，常把乘法因子当作移位和加法运算的合集来处理。

对于固定字长的左移k位，这就和无符号\补码乘法非常的 了。

与2的幂相乘的无符号\补码乘法也是这种形式。（因为无符号和补码位级操作等价 对补码求相当于将其转化为无符号数数再求）

对于连续的从n->m的二进制的K（X*K）

2.3.7 除以2的幂

通常情况下，整数除法比乘法需要更多的time cycle，因此除以2的幂也可以用移位运算来表示。

而且整数除法通常都是向下舍入正值，向上舍入一个负值。

除以2的无符号 –rounding down

推导见Note

除以2的有符号数（Two’s Complement）–rounding down

对于有符号数，对负数我们常使用向上舍入，对正数使用向下舍入，但由于有符号数的向下舍入和Unsigned的向下舍入有类似的推导过程，使用这里给出有符号数的向下舍入，对于正数和无符号数过程一样，对于负数使用算术右移。

除以2的有符号数 –(rounding up )

除以2的有符号数 –(NEG - rounding up POS - rounding down)

练习2.42

Note:除法的除数不能向乘法的因子一样拆分来对任意的除数进行除操作。

2.3.8 总结

Unsigned和Two‘s Complement的加法和减法有完全相同的位级行为，乘法和除法有非常类似的位级行为。

加法位级行为完全相同

乘法完整的位级表示可能不同，但是截断后乘积的位级表示是相同的。

除以2的幂的区别在于

Unsigned - 用的是逻辑右移

Two’s Complement - 正数时用算数右移（其实也可以是逻辑右移 因为二者一样 w-1位为0） 负数时+2^k-1再逻辑右移 目的是为了正数rounding down 负数 rounding up

2.4 浮点数

浮点数在取实数运算的近似值的时候是很有用的。

2.4.1 二进制小数

注意对于形如0.11111……的数是刚好小于1的数，通常用1-ε来表示。2-ε表示1.11111……（2）

也可以用公式表示：1-2^（-n)

2.4.2 IEEE浮点表示

IEEE的基本规则

1.Normalized Values

可以获得额外的精度位，因为1.f……中的1可以省略。

表示的数并不是均匀分布，而是E不变时（e不变），f均匀增大时均匀分布；当E变化后越来越稀疏。

所以可以总结说：部分均匀分布，总体上越来越稀疏。

2.Denormalized Values

可以获得数值0的表示方法，因为Normalized里面M不可能为0；

可以非常均匀的表示那些非常接近0的数，因为M均匀变化而且E不变。

3.Sepcial Values

可以用来表示无穷（+∞、-∞ 当两个非常大的数相乘时 或者除以0时）

可以用来表示NaN，表示结果不是实数或者无穷（如根号-1 或者∞-∞）

为什么要设置biased？

因为通过biased可以实现从最大Denormalied数（e为0 E为1-Biased M为1-ε）到最小Normalized数（此时的e为1 E为1-Biased M为1.0）的平滑转化而且还没有大的差距。

这个特点很巧妙的让Normalized和Denormalized平滑过度。

float 和 double

各种形式值的分布（6bit）：

有趣的现象：

当我们将下表的位表示看作无符号数，那么可以看出他们是按照升序进行排列的这样浮点数的排序就可以按照整数进行排序。

而当s=1（符号位）时，处理负数有难点，因为开头有1并且是按照降序进行排列的。

2.4.4 rounding

因为表示方法限制了浮点数的范围和精度，所以浮点数的运算只能近似的表示实数运算。为了能合理的表示我们所给出的实数，所以引入舍入。

除了round-to-even以外的其他三种方式都有明确的确界，而向偶舍入看起来更像是一个随机的舍入。

不过这是我们的错觉，在统计偏差中，向上舍入会使得平均数比这些数本身的平均值略高，而向下舍入会使得平均数比这些数本身的平均值略低，而round-to-even就忽略了这种偏差，在50%时间里它会向上舍入，在50%时间里它会向下舍入。

Round-to-nearst == round-to-even:唯一的决策点就在于两个结果的中间数视。

对于二进制来说中间数要学会转化过来：

2.4.5 浮点运算

浮点（也是abelian group）运算也有逆元，无穷和NaN是个列外。

浮点单元的设计者使用特殊的技巧来避免执行精确的计算，而且保证了达到精度要求的舍入。

对于浮点加法和乘法运算：有交换率（有可能溢出得到∞）

无结合率（加法乘法都无结合性）： – 这是浮点运算缺失的最重要属性。

(3.14+1e10)-1e10 evaluates to 0.0

3.14+(1e10- 1e10) evaluates to 3.14

有单调性：（加法和乘法都有结合性）(无符号加法和补码加法不具有这个属性)

对于任意的a>=b,都有x（除了NaN）x+a>=x+b

2.4.6 C语言中的浮点数

对于使用c语言的机器都是使用向偶舍入的舍入方式。

int、float、double之间的转换：

int->float 数字不会溢出但是可能被舍入

在练习2-49中我们已经知道了不能准确连续描述的最小正整数公式，而E的作用只是给想要的小数点移动，当大于这个值之后friction field不能再变化，当friction field不变化的时候通过E的变化并不能得到连续的值。

Int->float or ->double ：因为double有更高的精度，所以可以保留更多的精确数值

Double -> float:可能溢出，因为精度小还可能被舍入

float - > double or ->int: 值将会向0舍入或者溢出

如果从浮点数转化为整数没有找到一个合适的近似值（溢出）将会出现：[10….0000]

2.5 小结

1.无符号数和有符号数之间的转化有相同的位模式

2.几种位级运算和算术运算组合的聪明方法

见2.3.3

见P74页

[0, . . . , 0, 1, . . . , 1] = (1«k)-1