（2）数据的机器级表示与处理

本章内容较多，很多问题查阅了一些博客和知乎问答，力求尽可能的详细，在语言实现层面主要是关注jvm的规范。

（一）数制和编码

1.二进制的意义和数据的基本运算

计算机采用二进制编码的原因：
1.二进制只有两种状态，在电路层面制造两个稳定状态的器件比多个稳定状态器件容易的多
2.二进制的编码，计数，运算规则简便易行
3.布尔代数的完善以及逻辑门电路的匹配

基本数据类型：
数值型数据：定点数（有符号定点整数，无符号定点整数）浮点数（单精度，双精度）
非数值型数据：逻辑数据，编码字符（字母和汉字等）

高级语言中用到的各种运算，在底层都会被编译为基础的算数运算指令和逻辑运算指令。显然如果能通过这些底层运算完成高级运算，效率会有些许提升 。
这些运算包括位运算（与：&,或：|，异或：^，取反：~,），逻辑运算（或：||，与：&&，非：！），移位运算（左移：<<，逻辑右移：>>>，算术右移:>>）。
关于位运算的技巧，见技巧篇，逻辑运算需要注意短路的问题。
另外值得注意的是移位运算中逻辑左移操作不需要考虑符号位，高位移出，低位补0。而在算术左移中，与逻辑左移处理方式一致。当无符号数或有符号数最高位移出的是1时，会发生溢出。（显然有符号数左移其正负性有可能发生变化）
右移分两种情况，逻辑右移指不考虑符号情况，低位移出，高位补0。而算术右移会使得低位移出，高位补符号位。这样能够保证负数右移，肯定还是负数；正数右移，肯定还是正数。
在不发生溢出的情况下，对于整形变量，左移N位相当于乘以2的N次幂，算术右移N位等于除以2的N次幂的整数部分（-1右移多少位还是-1,这是显而易见的因为-1是全为1的序列，低位丢弃，高位补1），正数时结果向0方向取整，负数时向负无穷方向取整。逻辑右移是无法保证结果跟原值的关系的。默认对于无符号整数采用逻辑移位，对带符号整数采用算术移位。

在不同数据类型进行转换时，需要分为扩展（小变大）和截断（大变小）两种情况。对于扩展有两种方式：0扩展和符号扩展。0扩展用于无符号数，会在新值比旧值多出来的位数部分添加足够的0。符号扩展用于补码表示的有符号数，会在新值比旧值多出来的位数部分添加足够多的符号位。由于这种机制，在java中常见小数据向大数据转换时有一个&0xff..操作，这就是为了能够把符号扩展变为0扩展，从而规避掉意想不到的错误。截断只有一种方式，就是把旧值比新值多出来的位数舍弃掉。在强制类型转换或隐式类型转换时，需要注意是否会因为截断和扩展产生隐藏的错误。

2.定点数的编码和运算

通常用机器数表示数值数据在计算机编码后的二进制数，而真值表示数值型数据实际的值。
对无符号数来说，比较简单，跳过（其实也是用补码表示的）。对于有符号数，采取补码表示，具体如下。
首先介绍一下模运算的概念：
对于以下整数，若A=B+K*M，则记为A B（mod M），A与B对模M同余
当A,B都小于模M,计算A-B时，可以用A加上-B的补码来代替
对于具有一位符号位和n-1位数值位的n位二进制整数X的补码
1.当X为正数时,X的补码等于其原码
2.当X为负数时,X的补码等于模M-|X|
在使用二进制固定位的计算机中，其实际计算时可以简单认为：
1.当X为正数时,X的补码等于其原码
2.当X为负数时,X的补码等于数值部分取反加一，符号位为1（原码也可以由补码取反加1得到）
特殊情况：当符号位为1，数值部分全为0时，取到n位二进制数能表示的最小负数。这是规定。此时它没有原码一说。其实可以简单理解为通过具备双射性质的补码，简化了减法运算，同时保证了运算结果的唯一性。

对于整数的四则运算，暂时把注意力集中在标志寄存器和溢出上。加减和乘法运算器的运算电路在计算机系统基础第二版P64有详细解释。有以下几个重要的标志位：

1.ZF零标志，ZF=1表示运算结果所有位为0，否则ZF=0
2.OF溢出标志，OF=1表示带符号数加减运算发生溢出，因为两个同符号数相加的结果的符号位一定等同于这两个数的符号位，所以当X和Y的最高位相同，但与结果的最高位不同时，OF=1，否则OF=0
3.SF符号标志，表示带符号数整数加减结果的符号位
4.CF进/借位标志，CF表示无符号数加减运算的进/借位。加法时，CF=1表示若最高位向上形成进位，减法时，CF=1表示若最高位向上形成借位。、
在加减乘除指令产生运算结果后都会根据结果产生以上四种标志位，并将这些标志信息保存到标志寄存器中。
在此处只是简单介绍，到第三章汇编指令时，会把标志位寄存器连同CMP指令，和检测比较结果的条件转移指令联立讲解。
注意对于有符号数，只有通过OF判断溢出，而无符号数通过进位借位CF判断溢出。
也就是说分整数加减法分为以下几种情况：
（1）无符号整数加法
result=
（2）无符号整数减法
result=
（3）有符号整数加法
result=
（4）有符号整数减法
result=
由于在机器指令层面无符号和带符号整数加减运算不加区分，因而高级语言程序执行过程中，带符号整数隐式转换为无符号整数运算时会出现意想不到的错误。java为了避免这种情况发生，不支持无符号整数类型。

而对于整数乘除运算分为如下情况：
（1）无符号整数乘法运算
result=
（2）有符号整数乘法运算
由于此时采用专门的补码乘法器运算，采用Booth乘法或改进的过的基4布斯乘法。能够保证两个n位补码的乘积结果为其对应的正确值的2n位补码。通常此时判断溢出的标准是：若高n位每一位都与低n位的最高位相同，则不溢出，否则溢出。如果要在程序中保证没有溢出而产生的错误，可以根据的关系来判断：若，则没有发生溢出，否则溢出。
（3）整数除法
只有当补码代表的最小值

3.浮点数的编码

浮点数的编码采用符号位，阶码和尾数的结合。这里主要讲一下应用最广泛的IEEE754标准。

image.png
image.png image.png
下面逐条讲解：
1.正负0
阶码和尾数全为0，符号位0或1，分别代表正0和负0，在不同情况下，有不同表现。比如对于C++和Java的float/double来说，认为+0和-0是相等的。而对于Java的Double和Float认为+0和-0不等。
2.无穷大量
阶码为最大（8位或11位全为1），尾数为0，符号位为0或1，分别表示
引入无穷大数使得计算过程中出现异常状况下程序能继续进行下去，并为程序提供错误检测功能。
在数值上大于所有有限数,小于所有有限数。无穷大数既可作为操作数也可作为运算结果，当操作数为无穷大数时，有两种处理方式：
（一）产生不发信号的非数NaN:如 等
（二）产生明确结果。如 等
3.非数NaN
NaN表示一个没有定义的数，符号位为0或1，阶码全为1，尾数不全为0。根据符号位后一位的值分为两种情况：为1时，为静止的NaN,当运算结果为此类数时，不发异常操作通知，即不触发异常处理；为0时，为发信号的NaN,运算结果为此类数时，触发异常处理。对于一些没有数学解释的计算，如,求一个负数的平方根，等会产生一个非数NaN。同时NaN与任何数值作运算，结果均为NaN。
4.规格化非0数
这是最常用的一类数，阶码在1~254（单精度）和1~2046（双精度）的数,其在计算机内计算公式在下面jvm规范里的图内。相当于将十进制数集合[-126，127]和[-1022,1023]分别双射到[1，254]和[1，2046]，在计算时需要将阶码代表的十进制值减去127或1023。可以看到在一些追求精度的运算中，普通单精度和双精度是会产生误差影响结果的。这里暂不讨论单精度和双精度的扩展格式。如果需要更高精度，建议使用BigDecimal类。同时需要注意的是，==和！=判断的标准是二进制数是否完全一致，所以等号两边如果都是数值型字面量（且没有进行任何可能影响二进制各位的操作），由于比较的依旧是常量池的存放的值，且没有任何舍入操作，所以相等。例如如下代码：

        float a=0.3f;
        double b=0.3;
        double c=0.4-0.1;
        System.out.println(a==(0.2f+0.1f));//true 单精度不够将不同的部分舍去了
        System.out.println(b==0.2+0.1);//false 双精度足够比较出不同的部分了
        System.out.println(0.3f==0.2f+0.1f);//true
        System.out.println(0.3d==0.2d+0.1d);//false
        System.out.println(b==c);//false

实际上比较a,b的值是否相等时，可以当|a-b|<时，判断a和b相等。是计算机定义的最小误差值。

5.非规格化非0数
符号位0或1，阶码为0，尾数不全为0。可以看到它的计算公式是尾数部分是不需要加1的。而此时数的分布密度也从规格化的线性级变为了常数级。

那么看完了IEEE754标准部分，看一下jvm的具体实现。以下是jvm虚拟机规范中对IEEE754中要求的部分改动：

image.png
image.png
可以看到jvm是把这些运算异常生成默认结果，同时在舍入时使用四舍五入的方式。注意 只有浮点数，除以0，或者一个数除以0.0，才会得到正负无穷大，不然会抛出异常。
再看一下jvm对非数的表示是如何规定的：
image.png
也就是说非数的二进制表示默认是用4个值表示，如下（负的变一下符号位）：

              System.out.println(Integer.toHexString(Float.floatToIntBits(1/0.0f)));
              System.out.println(Long.toHexString(Double.doubleToLongBits(1/0.0)));
    分别输出：7f800000
             7ff0000000000000

最后着重看一下常量池里单精度浮点数是怎么存放的

image.png

显然s存放符号位，通过算数右移（注意不能是逻辑右移，否则无法保留符号位）后比较获得。
e是阶码，通过算术右移23位然后取掩码获得。
m是尾数，先判断阶码是否为0，为0时为非规格化数，取掩码获得23位尾数，然后左移一位是为了能够与第二种情况对齐；不为0时为规格化数，取掩码获得23位尾数，通过或操作在23位数前加隐藏位1，之后通过公式计算（150=127+23，因为这里m不是1.XXX而是1XXX，所以需要在尾数上再减去23）

4.浮点数的舍入和运算

由于浮点数无法精确表示所有数值，因此在存储前必须对数值作舍入操作。具体分为5种舍入模式，这里只介绍最常用的也是IEEE754默认的模式：
Round to nearest, ties to even（四舍五入至偶数模式）
舍入到最接近且可以表示的值，当存在两个数一样接近时，取偶数值。(如2.4舍入为2，2.6舍入为3；2.5舍入为2，1.5舍入为2。)
Q：为什么会当存在两个数一样接近时，取偶数值呢？
A：由于其他舍入方式均令结果单方向偏移，导致在运算时出现较大的统计偏差。而采用这种偏移则50%的机会偏移两端方向，从而减少偏差。

下面补充一个令人困惑的例子：

        double d = 0;

        for (int i = 1; i <= 10; i++) {
            d += 0.1;
            System.out.println(d);
            System.out.println(Long.toHexString(Double.doubleToLongBits(d)));
        }
输出：
0.1
3fb999999999999a
0.2
3fc999999999999a
0.30000000000000004
3fd3333333333334
0.4
3fd999999999999a
0.5
3fe0000000000000
0.6
3fe3333333333333
0.7
3fe6666666666666
0.7999999999999999
3fe9999999999999
0.8999999999999999
3feccccccccccccc
0.9999999999999999
3fefffffffffffff

为什么产生如此效果，首先要知道由于十进制和二进制转换的限制，十进制浮点数是无法与二进制浮点数形成双射的（无论单双精度）。IEEE754标准仅仅是规定了误差舍入的精度。一个十进制浮点数需要先转换为一个二进制数才能参与运算，而运算的结果还需要以十进制数表示。这两个步骤都会产生细微的误差，所以导致以上出乎意料的结果。由于IEEE754标准的规定，在单双精度而言，一个十进制浮点数，转化为二进制数时，其有效数字最多保留17位，更多位的数字是会被舍入的。理解了以上内容后，再来看如下内容。

image.png

可以看到对于计算机是可以保存多于17位的，但
注意到0.3是17位而其他是16位。这其实说明round-trip字符串会选择最短的字符串~

image.png
这并不是0.1,0.2...0.9，1的真正转化，这种计算的目的是保留到小数点后一位时仍然可以round-trip，比如0.3可以和0.299999999999999988897769753748434595763683319091796875相互转化，只有0.30000000000000004才能和真实值round-trip。

也就是说一个二进制浮点数运算的结果是通过十进制数round-trip来逼近这个结果，取其中最短的字符串，所以才造成了这个奇怪的现象。

4.非数值数据

逻辑数据只能进行逻辑运算，注意逻辑数据不一定只有1位。完全可以将一个n位数据看做由n个一位数据组成。在需要提取某一项或者进行置位操作时，通过掩码完成。（java中的boolean类型其实就是通过byte类型取最低位掩码实现的）
字符类型首先介绍最常见的ASCII码。它是用8位表示128个字符（最高位为保留位，可以作为奇偶校验值或其他用途）。比较值得注意的是在进行大小字母转换时，大小写字母区别在于在从高位数第三位，这一位为0则是大写字母，这一位为1则为小写字母。所以在大小写转换和统计大小写字母个数时，完全可以通过掩码操作将这一位变换或者作为判断条件。比如大小写互换可以通过^0x20，统计小写字母个数可以通过判断&0x20!=0。
在ASCII码之外还有GBK，UTF-8,UTF-16-UTF-32等等编码，在有关编码的文章进行讲解。

5.数据的存放和排列

数据的基本单位有比特（bit），字节（byte），此外还有一个特殊的：字（word）。字在不用种类计算机上会有很大区别。例如x86处理器把一个字定义为16位。而字长通常指cpu内部用于整数运算的数据通路的宽度。它的长度应等于整数运算的运算器和通用寄存器宽度。说某种机器是32位或64位就是指字长。字和字长是两个不同的概念。
值得注意的是，在表示容量时，用K表示1024，而在表示速度，距离，频率时，用k表示1000。经常使用的最小带宽单位是以b而非B为基础的。

下面来说一说存储的排列方式。
由于大端法和小端法的区别，一般使用最低有效位和最高有效位来表示最低位和最高位。
大端法指数据的最高有效字节存放在小地址单元中，而小端法相反。例如假设变量x类型为int型，位于地址0x100的地方，其16进制值为0x12345678，地址范围为0x100到0x103字节。

image.png

这正好和我们平时书写习惯一致，先书写最高有效字节，再依次写其余字节。这是MIPS等指令机器采用的方式。

image.png

这是最常见的x86指令机器采用的方式。
需要注意的是计算机内部采用的方式是一致的，但在系统间通信尤其是网络通信时，必须注意相互转换。此外，音频视频和图像等文件格式或处理程序也涉及字节顺序问题。同时在阅读汇编程序时，也需要注意大端和小端的区别。
下面是一段C程序用来展示

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len)
{
    size_t i;
    for (int i = 0; i < len; i++)
        printf(" %.2x", start[i]);
    printf("\n");
}

void show_int(int x)
{
    show_bytes((byte_pointer)&x, sizeof(int));
}

void show_float(float x)
{
    show_bytes((byte_pointer)&x, sizeof(float));
}
void show_pointer(void *x)
{
    show_bytes((byte_pointer)&x, sizeof(void *));
}

void test_show_bytes(int val)
{
    int ival = val;
    float fval = (float)ival;
    int *pval = &ival;
    show_int(ival);
    show_float(fval);
    show_pointer(pval);
    byte_pointer val1=(byte_pointer)&val;
    show_bytes(val1,1);
    show_bytes(val1,2);
    show_bytes(val1,3);
}

int main()
{
    int num = 0x123456;
    test_show_bytes(num);


    return 0;
}

输出结果为：
 56 34 12 00
 b0 a2 91 49
 f4 fd 61 00 00 00 00 00
 56
 56 34
 56 34 12

可以看到同一个数据，采用不同的方式去解读会产生不同结果，在三次对show_bytes的调用分别接收到了
可以看到我使用的机器采用的是小端法。