# 使用2's complement 编码整数

**Published by:** [Aulee](https://paragraph.com/@aulee/)
**Published on:** 2023-11-05
**URL:** https://paragraph.com/@aulee/2-s-complement

## Content

从前我们讨论过用于在系统间传递整数的DER格式，即将任意整数编码为一串bytes的方法。本篇讨论用于在系统内对整数进行编码的格式。该格法既要方便对这些整数的存储，也要方便实现对整数的运算。 我们可以自然地用二进制数来编码正整数。因为任意整数皆可转化为正的二进制数： $$x = a_0 \cdot 2^n + a_1 \cdot 2^{n-1} + ... + a_{n-1} \cdot 2^1 + a_n \cdot 2^0$$ 其中$$a_0a_1…a_{n-1}a_{n}$$就是－串由1或0组成的二进制数。$$n＋1$$为事先给定的二进制数的长度，决定了可以编码二进制数的容量。编码负整数我们需要一个额外的比特位来区分正数和负数。以0表示正数，以1表示负数。这个比特位称为sign bit。由sign bit和其他比特位相配合，以编码正负整数。有三种不同的编码方法：sign magnitude，1’s complement，和2’s complement。其中2’s complement拥有最好的计算性质，这里重点讨论。2’s Complement用2’s complement编码正负整数的方法与一般的编码正整数的方法基本类似，只在一点上相区别：最高位的比特数对应一个负的数值，而其他位的比特数仍然对应正的数值。即， $$x = a_0 \cdot (-2^n) + a_1 \cdot 2^{n-1} + ... + a_{n-1} \cdot 2^1 + a_n \cdot 2^0$$ 这使得可被编码的数的范围沿数轴向下移动了$$2^n$$，即由$$0,…,2^{n+1}-1$$移动到$$-2^n,…,2^n-1$$。 将负整数编码为二进制数 使用2’s complement，将负整数（设为$$-z$$）编码为二进制数的方法如下：1. 将对应的正整数（$$z$$）编码为二进制数。2. 计算上述二进制数的补数（complement），即所有0替换为1，所有1替换为0。3.对上述二进制数加1。例如，怎样将$$-5$$编码为4个比特位的2’s complement二进制数？1. $$5$$的二进制编码为$$0101$$。2. 对应的补数为$$1010$$。3. 再加$$1$$得$$1011$$。可以验证1011即为-5的2’s complement二进制编码： $$-2^3+2^1+2^0=-5$$原理解释（证明）在上述2’s complement 的第2步中求$$z$$的补数的运算相当于计算： $$-2^n+2^{n-1}+...+2^1+2^0-z$$ （注意上述第1项为负数。） 对上面$$z$$的补数的表达式需要理解两点：为什么求补数的操作可以表达为上式？假定$$z$$为正整数，故z的$$2^n$$项为0，因此计算这一项（位）的补数为加上$$-2^n$$。而在其他位上的补数操作相当于用这些位上可以有的最大正整数减去$$z$$，即$$111…111-z$$，也就是 $$2^{n-1}+...+2^1+2^0-z$$。两部加和，即为上式。在上式中，易知$$-2^n+2^{n-1}+...+2^1+2^0＝－1$$ 故第二步求补数操作后得$$-z-1$$。第3步再加1得$$-z$$。因此得到$$z$$的相反数。证毕。 P.S. 上式的一个扩展形式为： $$-b^n + (b-1)b^{n-1} + (b-1)b^{n-2}...+(b-1)b^1+(b-1)b^0=-1$$ 该式在直观上是显而易见的。如在16进制数下$$\mathtt{0x1000}-\mathtt{0xfff}=1$$，因为$$\mathtt{0xfff}$$进位1得到$$\mathtt{0x1000}$$。

## Publication Information

- [Aulee](https://paragraph.com/@aulee/): Publication homepage
- [All Posts](https://paragraph.com/@aulee/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@aulee): Subscribe to updates