32 位计算机时间戳溢出的思考 —— 整数的二进制表示

Year 2038 problem

CS50 第 01 讲:C语言 中,提到了一个很有趣的问题:Year 2038 problem,这个问题指的是:一些使用 32 位来存储时间戳的计算机,在 2038 年,可能会出现整数溢出的问题,导致计算机的时间倒退回 1901 年

时间戳 指得是:UTC 1970 年 1 月 1 日 0 时 0 分 0 秒到现在经历的秒数,用时间戳就可以表示当前的时间

为什么会出现这个问题呢?因为时间总是在流逝,所以每时每刻时间戳都在增加,但是 32 位的存储空间是有限的,总有一天会超出所能存放的最大值,而反直觉的是在超过了最大值后并不是归零(时间戳回到 1970),而是倒退到了更前的 1901 年,对应下面的表格我们就可以更直观地看到几个时间戳对应的具体时间

时间戳 对应的 UTC 时间
0 1970-01-01 00:00:00
2147483647 (32 位 int 最大整数值:2^31 - 1) 2038-01-19 03:14:07
-2147483648 (32 位 int 最小整数值:-2^31) 1901-12-13 20:45:52

可以看到当存储超过位数能容纳的最大值时,该值会从一个非常大的正数突然变为一个非常小的负数,所以导致了日期回到了 1901 年

原码、反码、补码

计算机底层是通过二进制的方式存储整数,两者转换可以参考文章:二进制和十进制之间的互相转换,除了整数的大小,还需要存储的是整数的正负,一般首位(最高位)用于存储正负,0 代表该整数为正数,1 代表该数为负数,将一个整数对应的二进制数转化为计算机存储的二进制数,这个变换就是《数字逻辑电路》里面经常提到的原码、反码、补码转化。注意:正数和 0 的原码、反码、补码相同,负数则需要转换

我们回顾一下,以 4 位二进制表示的整数举例:0 的原反补码都是 0000,1 的原反补码都是 0001,而 -1 该如何表示呢?

  1. 将 -1 的绝对值(1)的二进制 001 加上符号位(负数用 1)构造出原码 1001
  2. 符号位为不变,其余的按位取反转化为反码 001 就变成了 110,加上符号位,得到反码 1110
  3. 反码 +1 就成了补码 1111

补码就是机器存储的形式。具体的规则可以参考:原码, 反码, 补码 详解

整数的二进制编码

为什么要有这么复杂的原反补码的转换呢?直接最高位表示正负,其余位数表示数值这样不是很清晰吗?我们以 4 位为例,用二进制数表示数值,最高位表示符号,0 为 正数,1 为负数,其余三位表示数值,这种做法会有两个问题:

  1. 0 会重复,即出现正零(0000)和负零(1000),造成浪费
  2. 不利于计算机减法运算的设计,计算机计算减法的时候不能像人一样考虑借位

那么如何解决这个问题呢?解决方法就是把减法变成加法,加法对于计算机来说很容易。减去一个数就等于加上这个数的相反数,即 1 - 2 = 1 + (-2) = -1,如果把这个过程映射到数轴上就会容易理解一点,把负数接在 0 的前面,1 - 2 就可以理解为在 -2 的位置上,再加上 1,那结果是 -1,下面的数轴分别表示整数的值(真值)和其对应的补码

32 位计算机时间戳溢出的思考 —— 整数的二进制表示插图

从二进制的角度来看 0000 的前面是什么?我们可以理解为是 1111,因为当 1111 加上 1 的时候本来应该是 10000,但由于位数的限制,最高位溢出,我们可以当成是 0000,有了这种编码方式,上面的两个问题都解决了

现在再来看原码、反码、补码,就会通透一些,0 和 正整数的原反补相同,而负数,以 -1 为例,其绝对值 1 的原码 0001,对其修改,把符号位改为 1,其余位按位取反,得到 -1 的反码1110,对照数轴会发现 1110 其实是 -2 对应的补码,如果再把 1110 加 1,就变成了 1111 这就是 -1 的补码。我们可以理解为:正数转负数的这个过程本来是对称的过程,只要把正整数的补码映射到数轴的另一侧对应的位置即可,但是由于我们没有负零,所以需要往右边挪一个位置

将数轴连成圈,我们就可以很直观地看到,当整数到了其位数能表达的最大正数(7)后再加 1,此时进位,数值位变为了 000 而符号为了 1,而 1000 则是 4 位二进制表示的最小的负整数(-8),这就是为什么 32 位时间戳经过了 2038-01-19 03:14:07 却直接跳到了 1901-12-13 20:45:52

32 位计算机时间戳溢出的思考 —— 整数的二进制表示插图1

连成圈后也可以很直观地看出来,四位二进制,除去一位符号位,还有三位,2^3 = 8,可以表示 8 个整数,可以分别表示 8 个正整数和负整数,实际上 0 占用了正整数一个位置(0000),这也是为什么 Java Integer 的最大值的绝对值比最小值的绝对值小 1 了。最小值是 -2147483648(2^31),而最大值是 2147483647(2^31 - 1)

参考资料

Why has the Int32 type a maximum value of 2³¹ − 1?

文章来源于互联网:32 位计算机时间戳溢出的思考 —— 整数的二进制表示

THE END
分享
二维码