系统

整数的带余除法定理 余数在计算机中非常重要，二进制计算机只能用有限数目的二进制位处理和表示数据。当数据超出这个限制时，会被截断。这个特点可以用余数描述，而余数本身是由整数除法定义的。在小中学阶段就会学习余数，但主要是学习如何求余数，没有提到除法和余数的严格定义，以及对整数的严格定义。这部分内容属于数学中的整数理论。整数集中的除法和余数是由如下事实定义的，其本身也是一个定理，是整数理论的重要基础： a) 整数的带余除法定理：设\(a,b(b>0)\)为任意整数，存在唯一整数对\(q,r\)，使\(a=bq+r\)，其中\(0\leq r < b\)； 其中\(q,r\)是商和余数，计做\(a\div b = q……r\)，读作a除以b等于q余r。需注意的是上述定义包含了被除数为负的情况，而小中学阶段没有讨论过这种情况。另外这种除法和平时做数学计算的除法有一些区别：… 阅读全文

无符号整数的机器级表示 计算机是通过二进制位存储和传输数据的。虽然这些二进制位适合表示二进制数，但还是有一定区别，比如寄存器和总线的位数通常是固定的，另外对于负号、小数点、分数等等都不能直接表示，需要规定一些规则计算机才能处理。这些规则中，最简单的就是对无符号整数的表示，无符号整数顾名思义就是没有符号的整数，也就是自然数。这种表示和数学上的表示几乎没有区别，只需要预先规定好占用的位数，并且需要高位补0，比如在4位无符号整数表示下，3要写作0011，而3对应的二进制数是11。 一般的k位无符号整数，能表示的十进制数范围是闭区间的\([0,2^k–1]\)。   无符号整数的加法 之前讨论行波进位加法器时，没有规定如何处理最低位进位输入、最高位进位输出，这里规定为“忽略最高位进位的输出，最低位进位输入始终保持0”。当两个\(k\)位无符号整数码输入到\(k\)位加法器(\(k\)个1位加法器组成的行波进位加法器)，若结果未超出\(k\)位，那么加法器的输出就是正确的和。但若超出\(k\)位(两个\(k\)位无符号整数码经过加法器最多只能超出1位)，则加法器会忽略掉最高位的进位，剩下的\(k\)位才是最终输出，这种情况称为加法器的溢出，可通过余数描述。在这种规定下，这种\(k\)位加法器就能做\(k\)位无符号整数码的加法，具体这样描述：… 阅读全文

有符号整数的机器级表示 使用二进制位表示能带负号的有符号整数时，需要额外占用1个位来表示正负。有如下3种公认的表示方案： 1) \(k\)位原码：最高的第\(k\)位表示符号，称为符号位。0表示正数，1表示负数。剩下的位称为数值位，按\(k-1\)位无符号整数的方式表示绝对值。注意在原码下0有两个码，比如在4位下0有0000和1000的2种表示。这时会定义前者为负的-0，后者为正的+0(也就是0分为正数和负数两个)。\(k\)位原码的取值范围是\([ -(2^{k-1}-1), 2^{k-1}-1 ]\)； 2) \(k\)位反码：正数(含+0)为其原码，负数(含-0)为其原码“符号位不变，其他位取反”。反码取值范围和原码一样； 3) \(k\)位补码：正数(含+0)为其原码，负数(含-0)为其反码+1。补码中的-0会溢出，比如4位反码1111的原码会溢出，使其变为0000，也就是-0和+0一样，所以补码无需区分-0与+0。这里还有个问题是补码1000的意义不明确，在补码中会直接规定其表示-8。故4位补码的能表示-8~7，其中只有1个补码表示0，一般的\(k\)位补码的取值范围是\([… 阅读全文

定点小数的机器级表示 前面讨论过用无符号整数码和补码表示整数，如果约定这两种码的固定位置有小数点，那这两种码也能表示这种数，称为定点数(定点小数)。这样一来整数就是定点小数的特例，整数可看作是小数点在最低位右边的定点小数。一般来说可以约定小数点在最高位之前(纯小数)到最低位之后(整数)的任意的\(k+1\)个位置上。 定点整数和数学中整数的区别不大，除了不能处理无穷。但定点小数和数学中的小数则有区别，定点小数的取值范围更像“以二进制0.1(\(2^{-1}\))、0.01(\(2^{-2}\))…为步长的整数”。比如1个4位的码1111，将其看作无符号整数码，表示15。将其看作小数点定在第2位之前的无符号小数码，表示\(15\times 2^{-2}\)。虽然计算机不直接存储小数点位置，为方便也可写作11.11。… 阅读全文

浮点数的机器级表示 （1） （2） 前面讨论的都是定点数，其特点是小数点位置静态不可变，且小数点位置本身没有硬件来存储。浮点数则是完全不同的结构，因为每个浮点数必须记录自身小数点的位置，“浮点”这个名字就是是指小数点位置可变。于是设计浮点数的表示方案会更复杂，而且小数的数学性质本身也更复杂一些，比如前面讨论过，小数进制转换天生就有精度丢失问题。 目前权威的浮点数方案是数值专家William Kahan主导的IEEE754，采用科学记数法以\((-1)^s\cdot M \cdot 2^N\)计数，科学记数法中的基数与指数在IEEE754中称为尾数与阶数。在计算机中会从高位到低位存储\(s,N,M\)，对\(s,N,M\)的具体规定如下： 1) \(s\)：符号位，表示浮点数的符号，规则是0正1负； 2) \(M\)：即尾数(指小数的尾数)；… 阅读全文