32 位電腦時間戳溢出的思考 —— 整數的二進位表示

• 2022 年 11 月 9 日
• 筆記
• 編程雜記

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?