剑网3生活技能-集中的近义词是什么

整数编码

一、非负整数十进制与二进制的相互转化
1． 十进制到二进制的转化
将十进制非负整数
x
转化为二进制整数

x
n1

x
2
x
1
x
0
（其中< br>x
i
{0,1}
）即解方
程
x

x
n1
2
n1


x
2
2
2
x
1
2
1
x
0
2
0
（
x
i
{0,1}
）
此方程有唯一解，可按
x
0
,x
1
,x
2
,
的顺序由下式逐一求出：
< br>0(x为偶数)
xx
i
x
i


(i0 ,1,2,)
直到
x0
为止。 并重置
x
1(x为奇数)
2

2． 二进制到十进制的转化 x
n1

x
2
x
1
x
0
 x
n1
2
n1


x
2
2
2
x
1
2
1
x
0
（
x
i{0,1}
）
3． 非负整数到定长二进制整数的相互转化
将十进制非负整 数
x
转化为定长为n的二进制整数
x
n1

x
2
x
1
x
（其中
x
i
{0,1}
）
0
即解方程
xb
k1
2
k1

b
2
2
2
b
1
2
1
b
0
2
0
（
x
i
{0,1}
）
此方 程有唯一解，可按
x
0
,x
1
,x
2
,
的顺序由下式逐一求出：

0(x为偶数)
xx
i
置
x
i


。
(i0,1,2,

,n1)< br>并重置
x
2
1(x为奇数)

注意：当
x2时，转化结果截断了。
下文中将此转化函数记为
B
n
(x)
， 定义域：
[0..21]
，值域：
{0,1}
。
1
其 反函数记为
B
n
(x
n1

x
2
x1
x
0
)
,定义域：
{0,1}
，值域：
[0 ..21]
，反函数的
nn
nn
n
表达式为：
1B
n
(x
n1

x
2
x
1
x
0
)x
n1
2
n1


x2
2
2
x
1
2
1
x
0


二、定长非负整数编码
对非负整数一特定子集进行二进制定长编码，C语言中称为 无符号整数，其码字长度
称为字长，下记为n。
1． 编码函数f

f( x)B
n
(x)
，定义域为
[0..2
n
1]
，值域为
{0,1}
n
，以n=3为例的映射关系如下：

0
000

2． 解码函数g
1
001
2
010
3
011
4
100
5
101
6
110
7
111
g(x
n1

x
1
x
0
)x
n1
2
n1

x
1
2
1
x
0
，定义域为
{0 ,1}
n
，值域为
[0..2
n
1]
。
3． 运算
算术运算：单目：－、＋＋、――；
双目：＋、－、*、、%；
关系运算：==、!=、>、>=、<、<=；
位运算：！、&、|、^、<<、>>。 < br>以算术运算为例说明：基本运算：＋、－、*、，运算规则为：
abg(f(a)f(b) )
，
其中
f(a)f(b)
为相应的限长二进制算术运算，＋、－、*可能 溢出。
其他算术运算可以基本运算导出，如：
a0a
，
a%ba(ab)b

以n=3为例：

以n=8为例：

三、定长整数编码
对整数一特定子集进行二 进制定长编码，常见的有以下四种种方案：原码方案、反码
方案、补码方案、移码方案等。

四、定长整数编码：原码方案（Sign-Magnitude System）
1． 编码函数f

0B
n1
(|x|)x[0..2
n11]
n1n1
，定义域为
[(21)..21]
，值域f(x)

n1

1B
n1
(|x|)x[ (21)..0]
为
{0,1}
，以n=3为例的映射关系如下：
-3
111
-2
110
-1
101
0
-0
100
0
000
1
001
2
010
3
011
n

2． 解码函数g
< br>x
n2
2
n2


x
1
2< br>1
x
0
(x
n1
0)
n
，定义域为< br>，值域
{0,1}
g(x
n1

x
1
x< br>0
)

n21

(x
n2
2
x
1
2x
0
)(x
n1
1)
为
[(2
n1
1)..2
n1
1]
，以n=3 为例的映射关系如下：
000
0
001
1
010
2
011
3
100
-0
101
-1
110
-2
111
-3

3． 运算
与无符号整数一样可以有算术运算、位运算、关系运算，但运算复杂。

五、定长整数编码：反码方案（One’s Complement System）
1. 编码函数f

B
n
(|x|)(x[0..2
n1
 1])
n1n1
，定义域为
[(21)..21]
，
f( x)

n1

B
n
(|x|)求反(x[(21 )..1])
值域为
{0,1}
n
。所谓求反，指将码串逐位01互换。
以n=3为例的映射关系如下：
-3
100
2. 解码函数g
-2
101
-1
110
0
-0
111
0
000
1
001
2
010
3
011

x
n1
2
n1


x
1
2
1
x
0
(x
n1
0)< br>n
，定义域为
，值域
{0,1}
g(x
n1
x
1
x
0
)

n11

(x< br>n1
2

x
1
2x
0
)(x
n1
1)
为
[(2
n1
1)..2
n11]
，以n=3为例的映射关系如下：
000
0
001
1
010
2
011
3
100
-3
101
-2
110
-1
111
-0

3. 运算
复杂程度有改进。如，加减法时，符号位与数字位可统一处理，具体略

六、定长整数编码：补码方案（Two’s Complement System）
1． 编码函数f

B
n
(|x|)x[0..2
n1
1 ]
n1n1n
，定义域为
[2..21]
，值域为
{0,1 }
。
f(x)

n1
B(|x|)求补x[2..1]

n
☆ 两长度为n的01串
y
1
、y
2
互补

y
1
y
2

[00

0 ]
；一个可称为另一个的
补；

☆
y
的补的求法： 三个等价公式：
y
各位求反再加
[001]
或者
[000]y
或
者减
[001]
再各位求反。
快速计算方法：找到最右边的1，右边各位（含最右边的1）不变，左边各位
求反。如

以n=3为例的映射关系如下：
-4
100

2． 解码函数g
-3
101
-2
110
-1
111
0
000
1
001
2
010
3
011

x
n1
2
n1


x
1
2
1
x
0
(x
n1
0)< br>
g(x
n1

x
1
x
0
)< br>
n11

(x
n1
2

x1
2x
0
1)(x
n1
1)
定义域为
{0,1}
n
，值域为
[2
n1
..2
n1
1]
，以n=3为例的映射关系如下：
000
0
001
1
010
2
011
3
100
-4
101
-3
110
-2
111
-1

3． 运算
算术运算：单目：－、＋＋、――；
双目：＋、－、*、、%；
关系运算：==、!=、>、>=、<、<=；
位运算：！、&、|、^、<<、>>、>>>。
4． 算术运算
－(单目)：
ag(f(a))
。
＋：
abg(f(a) f(b))
，其中
f(a)f(b)
为相应的限长二进制加法运算。
－：
aba(b)
即
abg(f(a)f(b))
。
*：
abg(f(a)f(b))
，其中
f(a)*f(b)
为相应的限长二进制乘法运算。
：
abg(f(a)f(b))
，其中
f (a)f(b)
的计算可转化为原码后再计算，计算
完成后再转化为补码，

抛出异常

[00

0]

f(a)f(b)


f(|a|)f(|b|)


(f(|a|)f(|b|)) 求补
(f(b)[00

0])
(f(a)[00

0 ])
(f(a)与f(b)符号位相同)
(f(a)与f(b)符号位不同)

（其中等号右边的
f(|a|)f(|b|))
为限长二进制除法运算）

%：
a%ba(ab)b
。
、%只在一种情况下溢出 ：
a2
n1
,b1
，但可能抛出异常：
b0
。
乘法可进一步优化，如Booth一位乘、Booth二位乘，除法也可将符号位和数字位
统一 处理，如恢复余数法、加减交替法。此处略，可另开辟章节专门叙述。
以n=3为例：

以n=8为例：

5． 移位运算
6． 加减溢出判断
通常有 三种方法：(1)通过参加运算的两个操作数的符号与结果的符号来判断；(2)
单符号位法；(3)双 符号位法
7． 注解
“补码”一词在文献中可根据上下文做两种不同的解释：有符号二进 制数的一种
表示方案或二进制数的一种运算。本文中用“补码表示”和“求补”加以区别
8． 等价的编码函数

B
n
(|x|)x[0..2
n1
1]
f(x)

n1
B(|x|)求补x[2..1]
n


B
n
(x)x[0..2
n1
1]< br>


nn1
B(2x)x[2..1]

n
B
n
(x)[2
n1
..2
n1
1 ]
定义域为
[2..2
n1n1
1]
，值域为
{0 ,1}
n

n1n1
其中
B
n
(x)xn1

x
2
x
1
x
0
（定义域：< br>[2..21]
，值域：
{0,1}
n
）由下列过
0(x为偶数)
xx
i
程定义：置
x
i


。
(i0,1,2,

,n1)
并重置
x
2
1(x为奇数)

证明：先证明当
x[2..1]
时
B
n
(2
n
x)B
n
(|x|)

n1

B
n
(2
n
x)B
n
( 2
n
|x|)
B
n
(2
n1

< br>2
1
2
0
1(x
n1
2
n1< br>

x
1
2
1
x
0
2
0
))
B
n
((1x
n1
)2
B
n
(|x|)
再证明当
x[2
n1
..2
n11]
时，
n1


(1x
1
)2 (1x
0
)21)
10

[x]
补
x
n1

x
1
x
0
x(x
n1
)2
n1
x
n2
2
n2


x
1
2
1
x
0
2
0
。
若
x[0..2
n1
1]
，则
x
n1
0
，
[x]
补
x
n1

x
1
x
0
x02
n1
x
n2
2
n2
< br>
x
1
2
1
x
0
2
0
x(x
n1
)2
n1
x
n2
2
n 2


x
1
2
1
x
0
20
若
x[2..1]
，则
2x[2..21]
，故
x
n1
1
，
n1nn1n

[x]补
x
n1

x
1
x
0
x2
n
x
n1
2
n1
x
n2
2< br>n2


x
1
2
1
x
02
0

x(x
n1
)2
n1
x< br>n2
2
n2


x
1
2
1< br>x
0
2
0
证毕。
解码函数自然也有多种写法：

x
n1
2
n1


x
1
2
1
x
0
g(x
n1

x
1
x
0
)

n11

(x
n1
2

x
1
2x
0
1)

x
n 1
2
n1


x
1
2
1
 x
0


nn11

2x
n1
2 

x
1
2x
0
(x
n1
)2
n1


x
1
2
1
x
0< br>
七、定长整数编码：移码方案
1． 编码函数f
(x
n10)
(x
n1
1)
(x
n1
0)

(x
n1
1)
(x0)

[shift]B
n
(x)

f(x)B
n
(xshift)
或
f(x)


[shift]B
n
(|x|)(x0)（其中
shift
为约定的偏移量，
[shift]B
n
(s hift)
，通常取
shift2
nn
n1
或2
n1
1
）
定义域为
[shift..21shift]
，值域 为
{0,1}
，以n=3为例约定偏移量为3时的
映射关系如下：
-3
000
-2
001
-1
010
0
011
1
100
2
101
3
110
4
111

2． 解码
1
g(x< br>n1

x
2
x
1
x
0
)Bn
(x
n1

x
2
x
1
x
0
)shift

1

B
n
(x
n 1

x
2
x
1
x
0
[shift])( x
n1
1)
或
g(x
n1

x
2< br>x
1
x
0
)


1

B
n
([shift]x
n1

x
2
x1
x
0
)(x
n1
0)
定义域为
{0,1 }
n
，值域为
[shift..2
n
1shift]
，以n=3为例约定偏移量为3时的
映射关系如下：
000
-3
001
-2
010
-1
011
0
100
1
101
2
110
3
111
4

3． 运算
移码用于浮点数的阶码，主要运算是比较大小和加减运算，移码对这些运算比较
简单。
比较大小：字典比较
1])
加法运算：
abg(f(a)f(b)[011
1])
减法运算：
abg(f(a)f(b)[011
4． 溢出判断：
通过参加运算的两个操作数的符号与结果的符号来判断。
最高位也可以看成符号位，但含义与 补码方案相反，1表示正数。溢出只能出现在
同号的加法和异号的减法，同号加法溢出当且仅当结果符号 与操作数符号不同，异号
减法溢出当且仅当结果符号与第一操作数符号不同。
5． 例
以n=3(shift=3)为例

以n=4(shift=7)为例

八、原码方案、反码方案、补码方案、移码方案的比较
原码：符合人类习惯，但加减乘除复杂（符号位与数字位分开处理），0的编码有2个；
反码 ：加减简单（符号位与数字位统一处理，需循环进位），但乘除要区分符号位与
数字位，0的编码有2个 ；
补码：加减乘除简单（符号位与数字位统一处理且不需循环进位），0的编码统一；
移码 ：比较运算简单，0的编码统一，加减运算与补码运算复杂度相当，但乘除也要
区分符号位与数字位。
九、其他方案
BCD码，格雷码，……。不同的方案适应不同的应用要求。
十、变长整数编码
略