整数编码一、非负整数十进制与二进制的相互转化1．十进制到二进制.docVIP

整数编码 非负整数十进制与二进制的相互转化 十进制到二进制的转化 将十进制非负整数转化为二进制整数（其中）即解方程 （） 此方程有唯一解，可按的顺序由下式逐一求出： 并重置直到为止。 二进制到十进制的转化 （） 非负整数到定长二进制整数的相互转化 将十进制非负整数转化为定长为n的二进制整数（其中）即解方程 （） 此方程有唯一解，可按的顺序由下式逐一求出： 置并重置 。 注意：当时，转化结果截断了。 下文中将此转化函数记为，定义域：，值域：。 其反函数记为,定义域：，值域：，反函数的表达式为： 定长非负整数编码 对非负整数一特定子集进行二进制定长编码，C语言中称为无符号整数，其码字长度称为字长，下记为n。 编码函数f ，定义域为，值域为，以n=3为例的映射关系如下： 0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 解码函数g ，定义域为，值域为。 运算 算术运算：单目：－、＋＋、――； 双目：＋、－、*、/、%； 关系运算：==、!=、、=、、=； 位运算：！、、|、^、、。 以算术运算为例说明：基本运算：＋、－、*、/，运算规则为：，其中为相应的限长二进制算术运算，＋、－、*可能溢出。 其他算术运算可以基本运算导出，如： ， 以n=3为例： 以n=8为例： 定长整数编码 对整数一特定子集进行二进制定长编码，常见的有以下四种种方案：原码方案、反码方案、补码方案、移码方案等。 定长整数编码：原码方案（Sign-Magnitude System） 编码函数f ，定义域为，值域为，以n=3为例的映射关系如下： -3 -2 -1 0 1 2 3 -0 0 111 110 101 100 000 001 010 011 解码函数g ，定义域为，值域为，以n=3为例的映射关系如下： 000 001 010 011 100 101 110 111 0 1 2 3 -0 -1 -2 -3 运算 与无符号整数一样可以有算术运算、位运算、关系运算，但运算复杂。 定长整数编码：反码方案（One’s Complement System） 编码函数f ，定义域为，值域为。所谓求反，指将码串逐位0/1互换。 以n=3为例的映射关系如下： -3 -2 -1 0 1 2 3 -0 0 100 101 110 111 000 001 010 011 解码函数g ，定义域为，值域为，以n=3为例的映射关系如下： 000 001 010 011 100 101 110 111 0 1 2 3 -3 -2 -1 -0 运算 复杂程度有改进。如，加减法时，符号位与数字位可统一处理，具体略 定长整数编码：补码方案（Two’s Complement System） 编码函数f ，定义域为，值域为。 两长度为n的0/1串互补；一个可称为另一个的补； 的补的求法：三个等价公式：各位求反再加或者或者减再各位求反。 快速计算方法：找到最右边的1，右边各位（含最右边的1）不变，左边各位求反。如 以n=3为例的映射关系如下： -4 -3 -2 -1 0 1 2 3 100 101 110 111 000 001 010 011 解码函数g 定义域为，值域为，以n=3为例的映射关系如下： 000 001 010 011 100 101 110 111 0 1 2 3 -4 -3 -2 -1 运算 算术运算：单目：－、＋＋、――； 双目：＋、－、*、/、%； 关系运算：==、!=、、=、、=； 位运算：！、、|、^、、、。 算术运算 －(单目)：。 ＋：，其中为相应的限长二进制加法运算。 －：即。 *：，其中为相应的限长二进制乘法运算。 /：，其中的计算可转化为原码后再计算，计算完成后再转化为补码， （其中等号右边的为限长二进制除法运算） %：。 /、%只在一种情况下溢出：，但可能抛出异常：。 乘法可进一步优化，如Booth一位乘、Booth二位乘，除法也可将符号位和数字位统一处理，如恢复余数法、加减交替法。此处略，可另开辟章节专门叙述。 以n=3为例： 以n=8为例： 移位运算 加减溢出判断 通常有三种方法：(1)通过参加运算的两个操作数的符号与结果的符号来判断；(2)单符号位法；(3)双符号位法 注解 “补码”一词在文献中可根据上下文做两种不同的解释：有符号二进制数的一种表示方案或二进制数的一种运算。本文中用“补码表示”和“求补”加以区别 等价的编码函数 定义域为，值域为 其中（定义域：，值域：）由下列过程定义：置并重置。 证明：先证明当时 再证明当时， 。 若，则， 若，则，故， 证毕。 解码函数自然也有多种写法： 定长整数编码