数制

介绍：

此处指的数制指一般计算机系统中数字的表示方式。限于篇幅和实验需求，这里暂且只介绍整数的表示方式。

进制：

进位制（positional notation 或 place-value notation），是一种编码数的方式。这里我们不形式化地介绍这个概念，只描述一个在应用层面较为准确的概念。在下面的说明中，默认十进制表示是个先验概念，如无特殊记号指明，所有数均为十进制表示。同时我们约定：在下面的说明中，位都是从==0==开始编号的。不难修改相关定义使得位从 1 开始编号。

一个 n 位 b 进制数（base-b number）为一个字符串 (bn−1bn−2…b1b0)(b），其中 bi∈{0,1,…,b−1}。定义其表示的值为

(bn−1bn−2…b1b0)b=∑bi×b^i^(i从0取到n-1，水平有限，打不出正规的∑来)

其中 bi称为第 i位的位权。当不特殊指明位数时，代表在当前上下文中，位数不重要。b进制数也称作基数（base）为 b 的数。

比如 10b(16)=1×16^2^+0×16^1^+11×16^0^=267，给出了267在十六进制下的表示。在十以上进制中，为了不造成解读上的困难，通常使用英文字母来表示 10及其以上的数。比如十六进制中的 a,b,c,d,e,f分别代表十进制的 10,11,12,13,14,15。字母的大小写一般不重要。

由于十六进制的广泛使用，人们规定了一种十六进制数的表示，即在数前加 0x 以区分十进制数。比如 (5a)(16)可以写作 0x5a。

进制转换:

对于一个数x，

若x本身已为10进制数，想要转换为b进制数，可以==通过不断求模b并在一次求模后用x整除b的结果代替x的方式来求出x在b进制下的每一位，直到x变为0时停止操作，则此时得到的字符串即为所求==。例如，7（10） 转换为十六进制数就是先模一次16，得到1放在其十六进制下的个位，整除16后得到1，1再模16得到1，放在其十六进制下的十位，1整除16得到0，停止操作，则17（10） =0x11（16）；

若x本身不为十进制数，想要转换为b进制数，

若b为10，则就为就将x第i位上的数乘以其原本a进制下的a^i^ 求和后得到的结果即为所求。例如，0x11(16) 转换为10进制数，就是将16^0^ *1+16^1^ *1=17得到0x11在十进制下的数。

若b不为10，则先将x转换为10进制数，再通过第二段的方法转换为相应进制下的数即可。

原码:

由于计算机采用开关元件，现代计算机均使用二进制位的序列（bit sequence）来表示数，包括小数。实际上，历史上前苏联曾经尝试开发过==三进制==计算机，想深入了解的可以自行搜索。

在数学上表示整数时，我们使用前缀负号（-）来表示负数。那么用二进制表示整数的最直观的想法，就是将其绝对值直接转为二进制，再用最高位表示正负号。这种表示方法被称作原码。举例来说，如果将1和−1表示为3位原码，则结果分别是 001 和 101。显然 n 位的原码系统可以表示 [−2^n−1^+1,2^n−1^−1] 内的整数。

不过注意到，上述表示中,0有两种表示方法（正0和负0），这是原码带来的不便之一。其次，如果要做运算的话，原码不能直接相加，需要根据符号位做相应判断：同号绝对值相加，异号绝对值大的减去绝对值小的，最后置符号位。因此，在现代计算机中涉及整数的计算，一般不使用原码。

根据 Wikipedia 上的资料，由于原码十分直观，因此在早期的计算机中得以使用。除此以外，==原码在数制中的另一大用处即为表示浮点数的有效数字，也是当今几乎所有计算机表示浮点数的标准==。其具体考量留待补码时做进一步说明。

反码：

设数制的位宽为 n≥1，如果将负数的绝对值的二进制==按位取反（~）==的话，我们就得到了反码系统（one’s complement）。

对于 n 位的反码系统，其可以表示的数的范围为 [−2^n−1^+1,2^n−1^−1]。

举例来说，在 3位反码系统中，1与−1的表示方法分别为 001 和 110。

注意到，00 在反码的表示中也有两种表示方法，分别为全0和全1。

尝试后容易发现，在反码系统中可以通过加法直接运算两个数的反码，但是需要一次循环进位（end-around carry），即如果有进位溢出（指两个n位数相加产生了第n位的进位，位的标号从0开始），则需要将该溢出进位当作1加入结果中。具体例子请参见这里。

因为上述不便，现在的绝大部分计算机都不采用这种方式。

作为一个题外话，来谈谈反码运算溢出的问题。如果两个同号数相加变成一个异号数，则发生溢出，两个异号数相加不可能发生溢出。

补码：

介绍:

为了弥补反码的缺点，人们发明了补码（two’s complement）。一个n位的补码实际上是一个数在模2^n^意义下的表示。

形式化地，在n位补码系统中，串 an−1an−2…a0表示的值是：

w=−an−1 * 2^n−1^+∑ai * 2^i^ (i从0到n-2)

对于n位的补码系统，其可以表示的数的范围是[−2^n-1^,2^n−1^−1]。

可以注意到，在补码中,0只有唯一的表示，即全0。因为2^n^是一个n+1位的数(二进制下），而补码长度只有n位，舍弃最高位之后恰好又全是0，所以0的表示是唯一的。补码的运算本质上是在模2^n^ 意义下的运算。不处理进位溢出，恰好相当于模2^n^。所以对于补码来说只需做正常的加法即可。

举例来说，在3位补码系统中,1的表示是 1comp=``001，−1~comp~=111。而 0~comp~=1~comp~+−1~comp~=(001+111`)%2^3^=000=0comp。

对于一个负数，知道其绝对值，如何得到其补码呢？可以做2^n^(即二进制下在有效位数全为0的情况下，有效位最高位的下一位（超出有效位数范围了）置1的情况）减去其绝对值（例如，在3位补码系统中，−1comp=111，2^3^ comp=1000 ,2^3^ comp-−1comp =1000-111=001=1comp )，或将其绝对值逐位取反(~)后加上1(始终在二进制形式下）。

因为 −x=2^n^−(2^n^+x)，所以如果想得到一个负数的绝对值，只需要用 2^n^减去其补码表示即可，亦即按位取反再加1。

补码的溢出判定准则和反码相同：两个同号数相加如果得到一个不同号数，则发生溢出；两个异号数相加不会出现溢出。在实际判断中，为了不区分是否是同号数相加还是异号数相加，设第n位符号位（此处从1开始编号）产生的进位为carryMSB，第n−1位最高数位产生的进位为 carryMSB−1，发生溢出当且仅当 carryMSB⊕carryMSB−1=1。该溢出准则引用自维基百科补码页中关于溢出检查的部分。

上段公式中的 MSB 为最高有效位 Most Significant Bit 的缩写，意为一个二进制数中有最大位权的位。举例来说，如果位是从0开始标号的话，则n位二进制数的 MSB 为第n−1位。(001)2为一个3位二进制数，其 MSB 为第2位。更详细的信息可以参见这里。

浮点数中的原码：

在原码中曾经提到过，在浮点数中表示有效数字时采用原码。既然整数的加减运算在补码中是一样的，那么为什么不同样使用补码表示浮点数中的有效数字呢？这里以个人之见谈谈其中的直觉。

根据这里的说明，单位一不同时，用补码反而会较为麻烦。举例来说，乘二的幂次在原码表示中是十分简单的，只需将绝对值部分进行移位即可。而在补码表示中，乘二的幂可以通过左移解决，但是除二的幂就会出现问题，比如五位补码 −9comp=(10111)2右移两位（右移时高位补进的位根据原来最高位补，例如， −9comp=(10111)2右移两位得到(11101)2之后期望得到 −2comp，但实际上得到的却是 −3comp。为了得到正确结果，则需要将补码转换成原码再进行操作，所以在浮点数这种因为对齐幂次需要而对有效数字进行频繁调整的表示方法中，采取补码表示反而不如直接采用原码。这就是在浮点数标准中，表示有效数字使用原码而非补码的原因。

作为题外话，浮点数的幂因为考虑到比较的需要，采用的是移码（offset binary）表示，具体参见这里。

小数点表示方法

隐含表示，小数点位置固定 （即定点数）

• 定点小数：小数点在最高位数值位前，绝对值小于1，例如：01100000（小数点固定位在最高位即符号位之后时）是十进制的0.75。

• 定点整数：小数点在最低位数值位后，没有小数部分

如：01100000是十进制的192，小数点固定为在最低位之后。

浮点数的表示

浮点数一般表示方式：阶码加尾数。

例：（175.125）10=（10101111.001）2 =0.10101111001*2^01000^。

阶码：01000（用定点整数表示）

尾数：0.10101111001（用定点小数表示）

[阶码符号位] [阶码的数值部分] [尾数符号位] [尾数的数值部分]

IEEE 754

符号位（Sign）、阶码(Exponet)、尾数(Mantissa).

单精度浮点数（32位）：[S,1位] [E,8位] [M,23位]

双精度浮点数（64位）：[S,1位] [E,11位] [M,52位]

S:1位，0：正数，1：负数。

E：用移码表示，n位阶码偏移量为2^n-1^-1。如8位阶码偏移量为0x7f（即127），11位阶码偏移量0x3ff（即1023）,移码相当于是给补码中所有数加上使补码中表示负数最小值的数在溢出或不溢出的情况下得到全为0的形式的数，所得到的一组二进制数，相当于原码的表示但数从小到大为负数最小到正数最大。

M:用原码表示，尾数必须==规格化==成小数点左侧一定为1，并且小数点前面这个1作为隐含位被省略。这样单精度浮点数尾数实际上为24位。

规格化数（尾数）形式：M=1.m

浮点数精度

单精度浮点数表示公式：(-1)^s^ * 1.m * 2^E-127^

双精度浮点数表示公式：(-1)^s^ * 1.m * 2^E-1023^

IEEE 754关于浮点数表示的约定（以单精度为例）

E	M	浮点数N
1<=E<=254	M!=0	表示规范浮点数N=(-1)^s^ * 1.m * 2^E-127^
0	0	0
0	M!=0	表示非规范浮点数(尾数小数点左侧不是1，而是0)N=(-1)^s^ * 0.m * 2^-126^
255	0	无穷大，由s决定正无穷大还是负无穷大
255	M!=0	NaN(Not a Number)用于处理计算中出现的错误情况，如0.0除以0.0

例1：

（175.125）10=（10101111.001）2 =1.0101111001* 2^111^=(-1)^0^ * 1.m * 2^E-127^,m=0101111001

S=0

E=(2的幂次以补码形式表示+偏移量)00000111+01111111=10000110

m=01011110010000000000000

浮点数二进制编码为：

0 100，0011，0 010，1111，0010，0000，0000，0000（0x432f2000)

例2：

（-0.0449219）10=（-0.0000101110）2=(-1)^1^ * 1.01110 * 2^E-127^

S=1

E=01111010

m=01110000000000000000000

浮点数二进制编码为：

1 011，1101，0 011，1000，0000，0000，0000，0000

(0xbd380000)

浮点数表示的范围与精度

处于负下溢出和正下溢出之间的数值会被直接判断为机器0

格式	单精度规格化 (-1)^s^ * 1.m * 2^E-127^	单精度非规格化(-1)^s^ * 0.m * 2^-126^
负数min	S=1,E=254,m=11……11，约为-3.4*10^30^	S=1,E=0,m=11……11,-(1-2^-23^)*2 ^-126^
负数max	S=1,E=1,m=0,-2^-126^	S=1,E=0,m=000……1,-2^-23^*2^-126^=-2^-149^
正数min	S=0,E=1,m=0,2^-126^	S=0,E=0,m=000……1,-2^-23^*2^-126^=2^-149^
正数max	S=0,E=254,m=11……11，约为3.4*10^30^	S=0,E=0,m=11……11,(1-2^-23^)*2 ^-126^

精度问题

一般float的有效位（精度）为6~7位,double的有效位为15~16位。