32 位計算機時間戳溢位的思考 —— 整數的二進位制表示

Year 2038 problem

在 CS50 第 01 講：C語言 中，提到了一個很有趣的問題：Year 2038 problem，這個問題指的是：一些使用 32 位來儲存時間戳的計算機，在 2038 年，可能會出現整數溢位的問題，導致計算機的時間倒退回 1901 年

時間戳 指得是：UTC 1970 年 1 月 1 日 0 時 0 分 0 秒到現在經歷的秒數，用時間戳就可以表示當前的時間

為什麼會出現這個問題呢？因為時間總是在流逝，所以每時每刻時間戳都在增加，但是 32 位的儲存空間是有限的，總有一天會超出所能存放的最大值，而反直覺的是在超過了最大值後並不是歸零（時間戳回到 1970），而是倒退到了更前的 1901 年，對應下面的表格我們就可以更直觀地看到幾個時間戳對應的具體時間

可以看到當儲存超過位數能容納的最大值時，該值會從一個非常大的正數突然變為一個非常小的負數，所以導致了日期回到了 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，下面的數軸分別表示整數的值（真值）和其對應的二補數

從二進位制的角度來看 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

連成圈後也可以很直觀地看出來，四位二進位制，除去一位符號位，還有三位，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?