第二章信息的表示和处理

你知道的，前面还是些小菜，现在卡基米确实看得有些糊涂了。这一章的主要内容在我看来，是打破传统数字的概念，理解计算机上面的数字，建立新的“直觉”，正是因为计算机里面的数字和自然状态的数字不一样，会在程序中产生不一样的行为，了解这些细节对于一口气写出正常的程序非常重要（或者及时补救说是）闲话少说，直接开始折磨

2.1 信息存储

2.1.1 十六进制表示法

由于计算机一个字节8个位，直接写一串01有一点神秘，所以我们可以用十六进制把4个位压成一个数字，这样一共有16个数字，0-9，A-F，用A-F表示10-15。用0x来说明这是个十六进制数。比如二进制数11110000可以被压缩成0xF0 只需要

2->16：划分为4个4个一组，开头不足的补0，进行转换
16->2：一变四（可以记住对应十进制数，然后化成对应4个二进制数）

2.1.3 字数据大小

不知道安装应用有没有看到x86，x64之类的字母，这些都是什么意思呢？
实际上，这里说的是计算机的字长，它决定了虚拟地址空间的最大大小，现在我们一般用的64位的设备。总之可以看成你设备的内存可以用多长的地址来表示。
那么我们不禁发问了，设备的字长不一样，我们的程序怎么保证同一变量在不同设备都正常存储呢？答案是，我们需要做到可移植性，比如c语言里就有int32_t之类指定它的数据大小。

2.1.3 寻址和字节顺序

由于一个对象可能要用好几个字节，我们通常把它存储为连续的字节序列，用第一个地址表示它的地址，但是只能放这一长串就有两种

大端法：最高有效位在前面，比如0x12345678，从低到高会存12 34 56 78
小端法：最低有效位在前面，比如0x12345678，从低到高会存78 56 34 12

两种方法没什么区别，纯粹大家习惯不同，结果都不想改，最后导致不同设备读取对方的数据发生了问题（因为顺序不同，结果拿到了反序的数据）

2.1.4 表示字符串

相反，如果是一堆char，因为它就用一字节，而且都用ASCLL码表示，所以跨平台更不容易出问题。

2.1.6 布尔代数简介

这里终于到了我们神神秘秘的布尔代数了，下面是四个常用的布尔运算，对接下来的位级运算很有用

与A是1，B是1，则A&B=1
或A是1或者B是1，则A|B=1
非A是1，则~A=0，A是0，则~A=1
异或A和B都是1或者0，则A^B=0，A和B不同，则A^B=1

现在你已经会了运算方法了，我们就可以对位向量（一堆1和0的序列）进行运算了。比如

1010&1111=1010
1000|0101=1101
1010^1100=0110
~1010=0101

位向量可以解决很多问题，比如把集合{0，1，3}表示为1101，{1，2}表示为0110，那么1101&0110=0100，说明两个集合有2这个共同元素。

2.1.7 C语言中的位级运算

这里主要说明上面的这些计算方法刚好C语言都能用，通过熟练掌握这些东西，我们可以实现一些行为，比如掩码计算（以后再说）

2.1.8 C语言中的逻辑运算

C语言中有以下3种逻辑运算符

&&（与）
||（或）
！（非）

它们不对参数进行按位计算一大串01，而是把参数当成0和1，只要不是0，剩下的1234，1.0，都当成TRUE，0，NULL，空字符串，都当成FALSE。

2.1.9 C语言中的移位运算

<<（左移）
>>（右移）

左移很简单，就是把每个位向高移动对应位数，超出最高位的丢弃，在低位补0。比如（0101）<<1 = 1010，（1010）<<2 = 1000 右移就有两种可能了，出于后面会说的特殊需求有算术右移和逻辑右移两种。两种右移都是向地位移动指定位数，超过最低位的丢弃。但是算术右移会按照开始时是1就在高位补1，如果是0就和逻辑右移一样在高位补0。

有一个有趣的点是，如果你把一个32位的东西移动了36位，C程序可能只会移动4位，因为它对移动的位数进行了取模。（不过说不准）

2.2 整数表示

接下来大的要来了

2.2.1整型数据类型

只需要知道

不同变量字节数不同，所以取值范围不同
整型分为有符号和无符号
有符号由于表示方式，负数的取值范围比正数大一

2.2.2 无符号数的编码

按照从最低位是2的0次方，从低到高不断递增1，实现把一个无符号的数变成一条位向量比如15等于2的3次方加2次方加2的1次方加2的零次方，所以15的位向量就是1111。

2.2.3 补码编码

这里特别的地方就是把最高有效位的权重改成-2^{最高位的位数-1}，现在就可以用同样的一串位向量表示负数了，实现了有符号。举例说明：

0101：2^2+2^0=4+1=5
1010: -2^3+2^1=-8+2=-6

通过这种刚开始看可能有点怪的编码方法，我们实现了有符号数的表示。现在可以解答为什么有符号的数负的取值范围比正数大一。因为1开头表达-8到-1,0开头却表达0-7，被0占用了1个取值范围说是。

如果上过我们24的程序设计课，我们还知道有其他的表达方式

原码第一位表示正负号，剩下的位表示数值，比如0001表示1，1001表示-1（可能这种方式更好理解）
反码正数的反码就是它原码本身，负数的反码是它的符号位除外，其余位取反，比如1010=1101。这种方式，我们可以得到第一位表示-(2^{最高位的位数-1}-1)剩下表示2^{对应位数-1},比如1010 = -(2^3-1)+2^1=-7+2=-5(注意力够好的小伙伴可以发现，把1010加1就是1011，而这刚好是-5的补码编码)

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

有人说，C语言有强制类型转换和指针，这是最好的特性，也是最坏的特性,总之，学了这里，你不至于在无符号和有符号强转的时候出错

简而言之，底层的逻辑其实是变成位向量，然后换对方的编码方式，比如对于字长4位的机器，无符号的9转成1001,再按照补码编码变成-7，就是这个逻辑。而为了快速计算，我们可以这么想，无符号变有符号，第一位从+2的(最高位-1)次方变成-2的(最高位-1)次方了，那我们就可以-2个2的(最高位-1)次方。（9 - 2*(2^(4-1))= -7 同理，有符号变成无符号就是把第一个位从-2的(最高位-1)次方变成2的(最高位-1)次方，，我们可以直接加两个2的(最高位-1)次方。总结就是第一次抵消原本编码方式的影响，第二次采用新的表达方式。

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

这里我们需要知道的只有C语言表达式的变量只要有一个无符号的，就会把所有有符号数变成无符号的，然后进行运算，需要小心神秘的行为比如 -1被认为大于0（无符号）

2.2.6 扩展一个数字的位表示

你看，现在我们知道为什么右移有两种方式了，算术右移和逻辑右移。无符号数只要不断创建新的最高位再用0填充有符号数就看第一个是什么，1就不断补1，0就不断补0。

举例说明：补码编码1001加上新的最高位1后原本第四位的1从-8变成了8，而新加的1变成了-16，两个抵消一下相当于-8，数的值就可以不变，而拓展位表示。

2.2.7 截断数字

截断也很简单，底层就是直接丢掉对应的高位而表面上的数，无符号可以简单的取（最高位的2次方）的模有符号没有简单的办法，只能先变成无符号，取模完变回有符号。

2.2.8 关于有符号数与无符号数的建议

建议你多练说是（x

2.3 整数运算

2.3.1 无符号加法

底层就是直接进行按位加，然后溢出就截断。表面上看变成了一个滚轮，到了能表达的最大值，比如15，再加1就变成0了要检测也很简单，只要看加法结果是不是反而比原来小就行

2.3.2 补码加法

老规矩，底层就是变成位级表示，然后按位加，多了截断表面上看就是一个滚轮，但是到了最大值，再加1就变成最小值了怎么算呢，如果小于最小值，就加一个2的字节数次方，大于最大值，就减一个2的字节数次方。
要检测有没有爆，看正正相加有没有变成负，负负相加有没有变成正

2.3.3 补码的非

在2.3.1中，提到了阿贝尔群，意思是模数加法形成了阿贝尔群，它具有可交换和可结合性，就是说虽然行为怪怪的，但是有符号和无符号数的运算是符合交换律和结合率的。这里我们就定义补码的非就是和自身相加等于0的数。为了实现它，其实就是想办法让按位加溢出。截断后剩下一条0. 这里底层反而比表面难，表面只要对不是最小值的取负数，对于最小值取本身就行。底层可以按位非然后+1，或者找到最低位的1把左边全部按位非

2.3.4 无符号乘法

进行一个x*y然后取模，和加法一样，这里没讲怎么直接实现按位乘法，有点好奇。

2.3.5 补码乘法

位级等价性不是很懂，按照我的理解，就是换成无符号数进行乘法，再把结果换回有符号数没有影响。因为本质上都是变成按位乘法，然后再得到一样的位向量（截断后），只是按照不懂编码方式变回十进制数说是。

2.3.6 乘以常数

你知道的，乘法一看就比加法耗时间，我们能不能把乘法变成比较快的操作呢？众所周知，一个常数可以变成二进制，这说明它可以拆成一堆2的不同次幂的和。而对于一个数，乘以2的幂，不就是把它左移吗（所以我们可以进行如下的操作比如x * 7 = x << 2 + x << 1 + x 当然我们还可以贪 x * 7 = x << 3 - x 具体怎么贪看哪个方法耗时短，设备会替你考虑的

2.3.7 除以2的幂

为了实现向0的方向取整，（-1.1->-1, 1.1->1）这里有符号的会比较复杂。无符号和有符号的正值只需要大胆的右移。因为移位的行为舍去了多余的低位，相当于向下取整。而有符号的负值就麻烦了，因为右移是向下取整，但我们需要向上取整，怎么办呢？我们可以用偏置技术，按照位移的位数，给负数加上（2的位移位数次方-1），再进行右移。为什么，这样可以对于被截断的位数进行一个隐形的判断，但凡被截断的地方有一点值，就会向刚好没被截断的最低位+1，这样就会向上取整，而如果刚好被整除，也不会产生干扰，因为这个偏量刚好被截断了

2.3.8 关于整数运算最后的思考

总之，要记住关键就是变成二进制，完成位级运算，再编码回所需形式

2.4 浮点数

一直在说我们的整型，那我们的浮点数肯定要发言了。当然，还是从简单的开始

2.4.1 二进制小数

如果小数点左边是2的n次方，那小数点右边也不能搞特殊，所以，小数点右边就是负次方说是，第一个二分之一，第二个四分之一以此类推。我们可以发现这样没办法精确表示一些小数，实际上本来就是这样，小数就是只能在计算机里面无限接近，近似表达的（10进制不也有无限不循环小数吗，也是只能近似表达）

2.4.2 IEEE浮点表示

可以发现，如果浮点还是和整型换汤不换药，不是很理想于是我们有了IEEE754标准它把浮点数分成三部分：符号位、阶码字段、尾数字段

符号位：最前，0表示正数，1表示负数
阶码字段：中间，阶码（对尾数表示的小数乘以2的几次方），这不就是在说小数点位置应该在哪里吗，实际上就是这样，所以用了生动形象的比喻，浮点
尾数字段：最后，表示小数部分，表示在按照指数字段表示的数移位之前的基数

所以浮点数就是浮点数 = (-1)^{符号位} *尾数*2^{阶码} 单精度浮点阶码字段8位，尾数字段23位双精度浮点阶码字段11位，尾数字段52位虽然看起来已经结束了，但是根据字段内容的不同，解读被编码的值的规则是不一样的分三种情况：

规格化的
- 表现：阶码字段既不全为0也不全为1
- 阶码字段 = 阶码字段直接转10进制 - 2的（阶码字段长度 -1）次方 + 1 这么做是为了实现负次方的幂
- 尾数字段 = 尾数字段直接转10进制 + 1 这么做是为了实现省略小数点前面的0，因为反正这种情况下都是一，不如贪一位，让尾数更精确
非规格化的
- 表现：阶码字段全为0
- 阶码字段 = - 2的（阶码字段长度 -1）次方 + 1 这么做是为了实现和规格化平滑切换
- 尾数字段 = 尾数字段直接转10进制因为这时候表达的数非常接近0或者就是0，搞不到1说是
无穷大或者NaN
- 表现：阶码字段全为1
- 尾数字段不全为0 NaN（Not a Number）
- 尾数字段全为0 Inf（无穷大）

2.4.3 数字实例

这里假定一个8位浮点，有4个阶码位和3个尾数位 0 0000 001

首先看到它是非规格化的，经过计算公式，我们知道它的阶码为1-2^{4-1}=-6尾数为0.001（二进制）
经过向左移动小数点6位，得到0.000 000 001（二进制）
所以这个数是1/512 0 0111 110
首先看到它是规格化的，经过计算公式，我们知道它的阶码为14 - 2^{4-1}+1 =7尾数为1.110（二进制）
经过向左、右移动小数点7位，得到1110 0000.0（二进制）
所以这个数是 224.0

2.4.4 舍入

通常我们有四种舍入方式

向零舍入
向上舍入
向下舍入
以及全新的向偶数舍入

我们肯定是讨论新鲜的东西，什么是向偶数舍入呢？对于一长串的二进制，舍入到指定位数，我们看它偏向向上舍入还是舍下舍入，如果发现两种方法都一样就选能让最低有效位是0的那个这样有什么好处呢，其实就是说，一直四舍五入数据偏大，一直五舍六入数据偏小，如果选择在五的时候向偶数方向舍入，就也可以总体上50%概率五舍，50%五入

2.4.5 浮点运算

这里没有讲底层的实现，只要知道由于舍入的性质，浮点运算可以交换，但不能结合

2.4.6 C语言中的浮点数

这里需要明确

int -> float 数字不会溢出，但可能会被舍入
double -> float 数字可能会溢出,也可能会被舍入
int/float -> double 数字不会溢出，也不会被舍入
float/double -> int 数字会被向0舍入,接着可能发生溢出

2.5 小结

不想说话了，这章内容确实一大堆，我已经尽可能去提供一些自己的理解方式了

KAJIMI_BOOK