884 字

4 分钟

整数表示

2024-04-21

[toc]

整数#

数据类型#

数据类型	大小
char	1Byte
short	2Bytes
int	4Bytes，最小和shor相同
long	4Bytes/8Bytes(64bit机器)，最小和int相同
long long	8Bytes(64bit)
int_64t	8Bytes
uint_64t	8Bytes

无符号数编码#

在数字编码中，我们可以把数字看做由w个0,1组成的向量，每一位的权重为 $2^w$ 次方。从而得到

B2U_w(\vec{X}) = \Sigma_{i = 0}^{w - 1}x_i2^i

无符号数字的总和就是每个向量在数轴上的叠加。

有符号数补码#

为了表示负数，需要第一位来表示符号。虽然第一位是符号位，我们可以第一位的权重视为 $-2^{w - 1}$

同样套用无符号编码类似的公式，第一位符号位的权重单独表示：

B2T_w(\vec{X}) = x_{w - 1}(-2^{w-1}) \times \Sigma_{i = 0}^{w - 2}x_i2^i

当符号位为1，后面为0时数字最小为 $-2^{w - 1}$ ，随着后面数字的增大而增大，全为 $1$ 时表示 $-1$

因为使用了一个符号位，最大整数只能为 $2^{w - 1} - 1$ ，其中符号位不能为1，所以不能为 $2^{w - 1}$

有符号数的原码和反码#

原码：最高位视为 $(-1)^n$ ，只表示符号和数值绝对值大小无关。剩下的bit表示数值。
反码：最高位的权重为 $-2^{w - 1} - 1$ $- 2^{w - 1} - 1$ ，
- 原码编码取反，然后+1，即可变为反码对应的编码。

这两种编码对于0都同时存在两种编码方案。如在源码中，[1000]和[0000]都表示0，反码中[0000]和[1111]都表示0

有符号数和无符号数的转换#

通过公式可以看出，对于正整数，无符号数的补码和有符号数的编码方案相同。

但是对于负数，无符号数的第一位权重为 $-2^{w - 1}$ ，而有符号数第一位的权重为 $2^{w - 1}$

显然看出，二者的权重相差 $2^w$ ，因此对于负数的补码转化为有符号数，只需要在负数的基础加上 $2^{w}$ 即可。

而大于或等于 $2^{w - 1}$ 的无符号数，只需要减去 $2^{w}$ 即可得到无符号数。

数字的操作#

数字的扩展#

对于无符号数，只需要在前面补0即可
对于负数，只要补上符号位的数字
- 假设对于1111，补上1后变为[11111]，新的前两位的权重总和为 $-16 + 8$ ,仍然是 $-8$ ，因此负数的数值保持不变。

数字的截断#

对于无符号数，截断前n位表示，对前n位不变，而剩下位数为0的数字取模。
- 如： $111001 = 57$ ，截断前3位表示 $57 mod [111000] = 1$
对于负数，需要先把补码转化为有符号数，然后截断后转化回补码。

加法#

有符号加法：溢出时，减去 $2^w$ 即可#

检测溢出：如果 $x + y \lt x$ ，则发生了溢出。

补码加法：#

正溢出，减去 $2^w$ $2^{w}$
- 检测正溢出： $x > 0, y > 0, x + y < 0$ ，发生了正溢出
负溢出，加上 $2^w$ $2^{w}$
- 检测负溢出： $x < 0, y < 0, x + y > 0$ ，发生了负溢出。

补码取反#

正数和0：取负数，然后减 $1$ $1$
- 如：01100(12) -> 10011(-13)
负数：取绝对值，然后加1
- 和上面的相反

乘法#

补码：都转化为有符号数，乘法运算后 $mod \space 2^{w}$ ，在转化为补码。

乘以2的幂，等价于左移 $log_2n$ 位

对于大于w位的左移位，实际只会移动 mod w 位

除以2的幂#

等价于右移位

整数表示

https://chrisnake11.github.io/blog/posts/coding/csapp/informationencoding/integer/

作者

Zheyv

发布于