预备知识

原码、反码和补码的含义

为了运算方便，机器数有三种表示法，即原码、反码和补码

• 原码

  原码是一种计算机中对数字的二进制定点表示法，原码表示法在数值前面增加了一位符号位（即最高位为符号位），正数该位为0，负数为1（0有两种表示：+0和-0），其余位表示数值大小。

  举个例子，+12的原码就是00001100，-12的原码就是10001100

• 反码

  当数字用原码进行运算时，需要先判断数字正负，这样导致效率不高，如果忽略符号位直接运算，则需要用到反码，但是直接使用反码也会出现问题。

  正数的反码和原码一样，负数的反码就是在源码的基础上符号位保持不变，其他位取反

  | 十进制 | 原码 | 反码 |
  | ——— | ————- | ————- |
  | 4 | 0000 0100 | 0000 0100 |
  | -2 | 1000 0010 | 1111 1101 |

  若进行计算4-2 即4+（-2）

  0000 0100（反码）

  1111 1101（反码）

  ---

  0000 0001（反码）

  0000 0001 （原码）

  发现计算错误，所以为了解决计算不准确问题，出现了补码运算

• 补码

  正数和 0 的补码就是该数字本身。负数的补码则是将其对应正数按位取反再加 1。补码系统的最大优点是可以在加法或减法处理中，不需因为数字的正负而使用不同的计算方式。

  6+（-3）

  0000 0110 （补码）

  1111 1101 （补码）1000 0011（原码）

  ---

  0000 0011（补码）

三种重要的数字表示：

• 无符号编码基于传统的二进制表示法，表示大于或者等于零的数字。
• 补码编码是表示有符号整数最常见的方法，有符号整数即可以为正或者为负的数字。
• 浮点数编码是表示实数的科学计数法的以2为基数的版本。

整数的表示虽然只能编码一个相对较小的数值范围，但它是精确的；而浮点数虽然可以编码一个较大的范围，但这种表示是近似的。

1. 信息存储

大多数计算机使用8位的块，或者字节(byte)，作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，成为虚拟内存。内存的每个字节都由一个唯一的数字来标识，成为它的地址，所有可能地址的集合就成为虚拟地址空间。

十六进制表示法

一个字节由八位表示，二进制表示法中，值域在00000000~2~～11111111~2~。在C语言中，0x或者0X开头的数组常量通常被认为是十六进制的值。

字数据大小

每台计算机都有一个字长，指明指针数据的标称大小。字长决定的最重要的系统参数就是虚拟地址空间的最大大小。对于一个字长为w位的机器而言，虚拟地址的范围为0～2^w^−1，程序最多访问2^w^个字节。

为避免由于依赖“典型”大小和不同编译器设置而带来的奇怪行为，ISO C99引入了一类数据类型，其数据大小是固定的，不随编译器和机器设置而变化。其中就有数据类型int32_t和int64_t，它们分别为4个字节和8个字节。

寻址与字节顺序

在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。例如，一个类型为int的变量x的地址为0x100,即是说&x的值为0x100。那么，(假设数据类型int为32位表示)x的4个字节将被存储在内存的0x100、0x101、0x102和0x103的位置。

若有一个w位的整数，其位表示位[xw-1,xw-2,…,x1,x0]，其中xw-1为最高有效位，x0为最低有效位。假设w为8的倍数，则这些位都能被分为字节，其中最高有效字节包括位[xw-1,xw-2,…,xw-8],最低有效位字节包括位[x7,x6,…,x0]。有两种规则，最低有效位在最前面的方法称为小端法，最高有效位在最前面的方法称为大端法。

假设int类型变量x位于地址0x100处，它的十六进制值为0x01234567（高位字节的十六进制值为0x01，低位字节值为0x67）。地址范围0x100~0x103的字节顺序依赖于机器的类型：

大多数Intel兼容机都只用小端模式。IBM和Oracl的大多数机器则按大端模式操作。

表示字符串

C语言中字符串被编码为一个以null(值为0)字符结尾的字符数组。每个字符都由某个标准编码来表示，最常见的是ASCII字符码。在使用ASCII码作为字符码的任何系统上都将得到相同的结果，与字节顺序和字大小规则无关。因而，文本数据比二进制数据具有更强的平台独立性。

位级运算

C语言提供了一组移位运算，向左或向右移动位模式。x<<k即x向左移动k位，丢弃最高的k位，并在右端补k个0。

对应的右移运算x>>k，机器支持两种形式的右移：逻辑右移和算数右移。逻辑右移在左端补k个0，算术右移是在左端补k个最高有效位的值。

整数表示

扩展一个数字的位表示

扩展一个数的位数，同时保持数值不变
0扩展：在数的开头添加0
符号扩展：在数的开头添加符号位
无符号数使用0扩展，有符号数使用符号扩展，值才不会改变：

• 无符号数101扩展至四位0101，还是十进制值5
• 有符号数101扩展至四位1101，还是十进制值-3

整数运算

无符号加法

两个无符号数相加，如果值超过能表示的范围（2^ω^），会对他进行截取
考虑四位无符号 1011 和 0110 相加，值10001超出范围，截取后为0001。即11 + 6 的值由17变成1
截取规则：对ω位的数，进行模2^ω^运算：17%16 = 1，与上面一致
映射规则:

补码加法

两个补码数相加，如果值超出范围（大于2ω-1或小于-2ω-1），会进行截取操作

四位补码数1010和1100相加，值10110超出范围，截取后为0110，-6+-4的值从-10变为6

补码的非

对十进制取反操作很容易：
在范围内的数x，除最小值取反还是自己外，其余数取反都为-x例如对9取反值为-9

无符号乘法

将一个无符号数截断为ω位，等价于该值模2ω

补码乘法

ω位的有符号数相乘，结果可能需要2ω才能表示。
将一个补码数截断为ω位相当于先计算该值模2^ω^，再把无符号数转换为补码
例如：

乘以常数

整数乘法指令相当慢，需要十多个时钟周期。而其他运算（加减、位级运算和移位）只需要一个时钟周期。所以把乘法优化为移位和加法的组合可以提高运行效率。

左移k位等价于乘2的k次幂：
例如：四位的数[1011]，左移2位得到[101100]，值由11变为44，相当于乘2^2^

乘一个较大的数可以把它分解为2的次幂相加的形式：
x * 14 （14 = 23 + 22 + 21）等价于（x<<3）+（x<<2）+（x<<1）

除以2的幂

除以2的幂也可以用移位运算来实现，无符号数使用逻辑右移，补码数使用算术右移

无符号数的移位总是舍入到0的结果，与整数除法的规则一致。

补码数的移位会向下舍入，例如右移4位会把-771.25向下舍入位-772，解决办法是在移位前加一个偏置量：

偏置量的值为：2^k^-1（2^k^为除数）

浮点数

二进制小数

浮点数的表示：小数点左边数字的权是正幂，得到整数值；小数点右边数字的权是负幂，得到小数值。
例如：十进制数12.34可以表示为1 10^1^+ 2 10^0^+ 3 10^-1^+ 4 10^-2^

二进制小数点向左移动一位相当于这个数被2除，向右移一位相当于乘2。

在有限长度编码下，小数的二进制表示法只能表示被写成 x * 2^y^的数，其他值只能近似表示
例如数字1/5可以用十进制0.20精确表示，但并不能精确表示为一个二进制小数，只能近似的表示它：

IEEE浮点数表示

IEEE标准规定，用: （-1）^S^ × M × 2^E^的形式表示一个浮点数。

符号：S决定这数是负数（S=1）还是正数（S=0）
阶码：E的作用是对浮点数加权，权重是2的E次幂尾数，M是一个二进制小数，M的范围大于等于1，小于2

看图好理解些，如下图，十进制数 5.5 即二进制的 101.1
①把小数点移到最高位后，变成一个大于1小于2的数，即尾数M=1.011
②移动了2位，即阶码E =2
③这个数就变为（-1)^0^× 1.011 × 2^2^的形式
④在内存里存储只需要存储符号、阶码、尾数就等于存储了这个值
因为指数可以为负，为了便于计算，规定阶码都先加上1023(2^10-1) （做实验的时候写的好像是127 。。）