整数在计算机中的表达

本质上是一个编码问题。

有符号数:在计算机中的表达非常有意思,体现了计算机科学的底层编码基本功。

如果一个N位的有符号数x,它的数学表达公式为:

公式一:有符号数的运算公式

$f(x)= -x_{N-1} \cdot 2^{N-1} + \sum_{n=0}^{N-2}x_{n}\cdot 2^n$

$x_{n}$ 分别代表每一个位,分别取值 1 或 0 。

注意到最高位上面默认带了一个负值,这意味有符号的数最高位$$x_{N-1}$$是正数时 $$x_{N-1}==0$$,这样有符号和无符号的正数在计算机里看到的编码统一起来。

在负数情况下,CPU的运算器可以很快的利用通用运算法则计算出二进制所表达的数值。如: (1,111, 1111)在CPU寄存器设置符号位的情况下,利用公式一可以计算出他的实际计算值: -1。 (很多教材上只告诉大家最高位是符号位,但是从来没告诉大家符号位实际上参与了计算。)

另外一点值得一提的是,因为负数用反码表示。多出了一个编码。

自然的负数编码思维: $$1000,0000 ~ 1111,111$$,表达 -0 ~ -127 共128个数。

自然的正数编码思维: $$0000,0000 ~ 0111,1111$$,表达 0 ~ 127 共128个数。

来看看这种人类思维的问题,一步一步的提问解决:

  • 1000,0000 和 0000,0000 在自然世界里没有意义,是属于冗余编码。他们两个编码中必然有一个可以拿出来另做他用。
  • 看起来0单独用0000,0000表达很符合逻辑,但这个 1000,0000怎么才能重复利用呢。
  • 用来表达 -127 的 1111,1111 在计算机里 +1 的话变成了 1000,0000,这就溢出变成我们的 -0了。正常情况下应该是 -126 才对。再 +1 变成 $$(1000,0001)_{b} = (-1)_{d} \ne (-125)_{d}$$
  • 这种编码看来满足不了需求。

解决方案

1,让 -1 + 1 = 0 在计算机中计算二进制非常的自然。如果 0000,0000表示0 。那么 -1 应该表示为 1111,1111。依次减1,最后一个负数应该是1000,0000。那么应该是表示了-128 到 -1 这些负数。

2,这就是补码,使用two's complement 补码来给负数编码。让计算机的算术计算看起来就这么自然。

3,补码有一个运算规则,计算机的前辈们发现的。相应的转换关系可以通过原码和补码来转换。 原码= 反码 + 1。

4, 一直以来,我只是记住了这个计算公式。但没有深入理解其背后的思考过程。

有一本编码的书,详细的解释了各种编码的规则。

安全

  • 符号整数和非符号整数的互相转换
  • 加一溢出
  • 整数翻转
  • 负数移出
  • 乘积溢出

当处理乘积问题时,有一个很好的实践。为乘积分配一个两个因子中最大的那个数的两倍。

对无符号数来说:$$(2^n-1) \cdot (2^n-1) = 2^{2n} - 2^{n+1} +1 < 2^{2n} $$

对有符号数来说:$$(2^{n-1}) \cdot (2^{n-1}) = 2^{2n-2} - 2^{n+1} +1 < 2^{2n} $$

有一组很好的胶片来说明这个问题。

标签: none

添加新评论