1. 為什么需要 __int128從 long long 的邊界說(shuō)起寫(xiě) C 的人遲早會(huì)撞上溢出的墻。long long看起來(lái)已經(jīng)很大了9.22e18的上限日常寫(xiě)個(gè)階乘到 20 就頂天了。但一旦你開(kāi)始碰組合數(shù)、大數(shù)乘法、模意義下的快速冪、或者某些競(jìng)賽題里明晃晃寫(xiě)著“答案可能超過(guò) 64 位整數(shù)范圍”long long就徹底不夠用了。我最早遇到這個(gè)問(wèn)題是在做一道組合計(jì)數(shù)題需要算C(100, 50)結(jié)果用long long跑出來(lái)是個(gè)負(fù)數(shù)。當(dāng)時(shí)還以為是公式寫(xiě)錯(cuò)了排查了半天才發(fā)現(xiàn)是中間乘法溢出。后來(lái)?yè)Q成__int128一行代碼解決問(wèn)題。__int128是 GCC 和 Clang 提供的一個(gè)擴(kuò)展類(lèi)型不是 C 標(biāo)準(zhǔn)的一部分。它在 64 位平臺(tái)上通常是 128 位有符號(hào)整數(shù)范圍大約是-1.7e38到1.7e38。這個(gè)范圍有多大你可以粗略理解為long long的平方級(jí)別。對(duì)于絕大多數(shù)需要“比 long long 再大一點(diǎn)”的場(chǎng)景它完全夠用。但問(wèn)題在于它沒(méi)有配套的輸入輸出。cin和cout不認(rèn)識(shí)它printf和scanf也不支持。你直接寫(xiě)cout x會(huì)編譯報(bào)錯(cuò)。這就是為什么很多人明明知道這個(gè)類(lèi)型卻不知道怎么用——卡在了輸入輸出上。這篇文章就是來(lái)解決這個(gè)問(wèn)題的。我會(huì)從類(lèi)型定義、輸入輸出實(shí)現(xiàn)、常見(jiàn)運(yùn)算場(chǎng)景、性能對(duì)比、踩坑記錄幾個(gè)角度把__int128的完整使用方案講清楚。不管你是剛學(xué) C 的新手還是打了幾年競(jìng)賽的老手只要你的程序需要處理超大整數(shù)這篇內(nèi)容都能直接拿來(lái)用。注意__int128是編譯器擴(kuò)展不是標(biāo)準(zhǔn) C。在 MSVCVisual Studio 的編譯器上不可用。如果你用的是 Windows Visual Studio需要換到 MinGW 或者 WSL 下的 GCC 才能編譯。2. __int128 的類(lèi)型定義與編譯器支持情況2.1 類(lèi)型名稱(chēng)與平臺(tái)差異在 GCC 和 Clang 中128 位整數(shù)有兩種寫(xiě)法__int128有符號(hào)范圍約-1.7e38到1.7e38unsigned __int128無(wú)符號(hào)范圍約0到3.4e38這兩個(gè)類(lèi)型在 64 位 Linux、macOS、以及 Windows 下的 MinGW-w64 中都可以使用。但在 32 位平臺(tái)上GCC 可能不支持或者支持但性能很差。所以用之前先確認(rèn)你的編譯目標(biāo)是 64 位。一個(gè)簡(jiǎn)單的驗(yàn)證方法#include bits/stdc.h using namespace std; int main() { __int128 x 1; cout sizeof(x) endl; // 輸出 16 return 0; }如果編譯通過(guò)并且輸出 16說(shuō)明你的環(huán)境支持。如果報(bào)錯(cuò)unknown type name __int128說(shuō)明編譯器不支持需要換環(huán)境。2.2 與 long long 的范圍對(duì)比類(lèi)型位數(shù)大致范圍能表示的最大階乘int32-2.1e9~2.1e912!long long64-9.2e18~9.2e1820!__int128128-1.7e38~1.7e3834!unsigned __int1281280~3.4e3834!從表里可以看到__int128能表示的階乘上限是 34而long long只能到 20。這個(gè)差距在組合數(shù)學(xué)、概率計(jì)算、密碼學(xué)相關(guān)題目中非常關(guān)鍵。2.3 什么時(shí)候該用 __int128不是所有“大數(shù)”場(chǎng)景都適合用__int128。我總結(jié)了幾種典型情況中間結(jié)果溢出但最終結(jié)果在 long long 范圍內(nèi)比如計(jì)算a * b % mod其中a和b都是long long級(jí)別乘積會(huì)溢出但取模后結(jié)果不大。這時(shí)候用__int128做中間計(jì)算最方便。需要精確計(jì)算超過(guò) 64 位的整數(shù)比如某些數(shù)論題、組合計(jì)數(shù)題。不想引入大數(shù)庫(kù)手寫(xiě)大數(shù)類(lèi)或者引入第三方庫(kù)如 GMP成本較高_(dá)_int128是零依賴(lài)的方案。但如果你的數(shù)字超過(guò) 38 位比如計(jì)算 100! 的精確值那__int128也不夠用必須上大數(shù)庫(kù)或者手寫(xiě)高精度。這一點(diǎn)要提前判斷清楚。3. 輸入輸出的完整解決方案3.1 為什么標(biāo)準(zhǔn)庫(kù)不支持__int128是編譯器層面的擴(kuò)展類(lèi)型C 標(biāo)準(zhǔn)庫(kù)的iostream和 C 標(biāo)準(zhǔn)庫(kù)的stdio都沒(méi)有為它定義重載或格式化說(shuō)明符。cout的operator只對(duì)標(biāo)準(zhǔn)類(lèi)型有重載printf的%d、%lld等也只認(rèn)標(biāo)準(zhǔn)類(lèi)型。所以你必須自己寫(xiě)輸入輸出函數(shù)。這不是什么難事核心思路就是把 __int128 當(dāng)成一個(gè)十進(jìn)制字符串來(lái)處理。輸出的時(shí)候不斷取模 10 得到每一位輸入的時(shí)候逐字符讀取然后累乘 10。3.2 輸出函數(shù)實(shí)現(xiàn)先看輸出。思路很簡(jiǎn)單如果是負(fù)數(shù)先輸出負(fù)號(hào)然后轉(zhuǎn)成正數(shù)處理。正數(shù)部分不斷對(duì) 10 取余把余數(shù)存到字符數(shù)組里最后倒序輸出。void print_int128(__int128 x) { if (x 0) { putchar(-); x -x; } if (x 0) { putchar(0); return; } char buf[50]; int len 0; while (x 0) { buf[len] 0 (int)(x % 10); x / 10; } for (int i len - 1; i 0; i--) { putchar(buf[i]); } }這段代碼有幾個(gè)細(xì)節(jié)值得說(shuō)buf的大小設(shè)為 50 足夠了因?yàn)?128 位整數(shù)的最大十進(jìn)制位數(shù)是 39 位2^127約等于1.7e3839 位數(shù)。x % 10的結(jié)果是__int128類(lèi)型需要強(qiáng)制轉(zhuǎn)成int才能加到字符上。用putchar而不是cout是因?yàn)閜utchar更快而且不涉及類(lèi)型重載問(wèn)題。如果你更喜歡用cout也可以把結(jié)果存到string里再輸出string to_string_int128(__int128 x) { if (x 0) return 0; bool neg false; if (x 0) { neg true; x -x; } string s; while (x 0) { s char(0 (int)(x % 10)); x / 10; } if (neg) s -; reverse(s.begin(), s.end()); return s; }3.3 輸入函數(shù)實(shí)現(xiàn)輸入稍微麻煩一點(diǎn)因?yàn)橐幚碡?fù)號(hào)、空白字符、以及非數(shù)字字符的終止判斷。__int128 read_int128() { __int128 x 0; int f 1; char ch getchar(); while (ch 0 || ch 9) { if (ch -) f -1; ch getchar(); } while (ch 0 ch 9) { x x * 10 (ch - 0); ch getchar(); } return x * f; }這個(gè)函數(shù)的邏輯是跳過(guò)所有非數(shù)字字符同時(shí)記錄是否遇到負(fù)號(hào)。讀到數(shù)字后不斷累乘 10 并加上當(dāng)前位。遇到非數(shù)字字符停止。注意這個(gè)函數(shù)假設(shè)輸入是合法的。如果輸入中有其他字符比如字母它會(huì)把字母當(dāng)成終止符。在競(jìng)賽環(huán)境中這通常沒(méi)問(wèn)題但如果你要處理更復(fù)雜的輸入格式需要自己加判斷。3.4 重載運(yùn)算符的寫(xiě)法如果你想讓代碼更“C 風(fēng)格”可以重載和運(yùn)算符ostream operator(ostream os, __int128 x) { if (x 0) { os -; x -x; } if (x 0) { os 0; return os; } string s; while (x 0) { s char(0 (int)(x % 10)); x / 10; } reverse(s.begin(), s.end()); os s; return os; } istream operator(istream is, __int128 x) { x 0; int f 1; char ch; while (is.get(ch) (ch 0 || ch 9)) { if (ch -) f -1; } while (ch 0 ch 9) { x x * 10 (ch - 0); is.get(ch); } x * f; return is; }重載之后就可以直接寫(xiě)cin x和cout x了。但要注意重載的時(shí)候最后一個(gè)字符會(huì)被“吃掉”如果后續(xù)還要讀其他內(nèi)容可能需要is.unget(ch)把字符放回去。這個(gè)細(xì)節(jié)在實(shí)際使用中很容易踩坑。4. 常見(jiàn)運(yùn)算場(chǎng)景與實(shí)操代碼4.1 大數(shù)乘法取模這是__int128最常用的場(chǎng)景。當(dāng)你需要計(jì)算(a * b) % mod而a和b都是long long級(jí)別時(shí)直接乘會(huì)溢出。用__int128做中間類(lèi)型long long mul_mod(long long a, long long b, long long mod) { return (long long)((__int128)a * b % mod); }這行代碼在競(jìng)賽中出現(xiàn)的頻率極高。它的原理是__int128能容納a * b的完整結(jié)果取模后再轉(zhuǎn)回long long就不會(huì)丟失精度。4.2 快速冪中的溢出處理快速冪的標(biāo)準(zhǔn)寫(xiě)法是long long qpow(long long a, long long b, long long mod) { long long res 1; while (b) { if (b 1) res (__int128)res * a % mod; a (__int128)a * a % mod; b 1; } return res; }注意res * a和a * a都用了__int128強(qiáng)轉(zhuǎn)。如果不轉(zhuǎn)當(dāng)mod接近1e18時(shí)兩個(gè)接近1e18的數(shù)相乘會(huì)溢出long long導(dǎo)致結(jié)果錯(cuò)誤。這個(gè)坑我在早期寫(xiě)題時(shí)踩過(guò)好幾次后來(lái)養(yǎng)成了習(xí)慣只要涉及模運(yùn)算下的乘法一律先轉(zhuǎn) __int128。4.3 組合數(shù)計(jì)算計(jì)算C(n, m)時(shí)中間結(jié)果可能非常大。如果最終結(jié)果在long long范圍內(nèi)可以用__int128做中間計(jì)算__int128 C(int n, int m) { if (m n - m) m n - m; __int128 res 1; for (int i 1; i m; i) { res res * (n - m i) / i; } return res; }這個(gè)寫(xiě)法利用了組合數(shù)的遞推性質(zhì)每一步都保證整除。用__int128可以計(jì)算到C(67, 33)左右再大就溢出了。4.4 與字符串的相互轉(zhuǎn)換有時(shí)候輸入是以字符串形式給出的超大整數(shù)需要轉(zhuǎn)成__int128再計(jì)算__int128 string_to_int128(const string s) { __int128 x 0; int start 0; bool neg false; if (s[0] -) { neg true; start 1; } for (int i start; i (int)s.size(); i) { x x * 10 (s[i] - 0); } return neg ? -x : x; }反過(guò)來(lái)把__int128轉(zhuǎn)成字符串用前面寫(xiě)的to_string_int128就行。5. 性能對(duì)比與選型建議5.1 __int128 vs long long 的性能差距__int128的運(yùn)算速度比long long慢這是必然的。在 x86-64 平臺(tái)上64 位整數(shù)的加減乘除都有硬件指令支持而 128 位整數(shù)需要編譯器生成多條指令來(lái)模擬。根據(jù)我的實(shí)測(cè)大致差距如下運(yùn)算long long__int128倍數(shù)加法1x2-3x慢 2-3 倍乘法1x3-5x慢 3-5 倍除法1x10-20x慢 10-20 倍取模1x10-20x慢 10-20 倍除法和取模特別慢因?yàn)?128 位除法沒(méi)有硬件指令編譯器需要調(diào)用軟件模擬函數(shù)。所以在性能敏感的代碼中要盡量減少__int128的除法和取模操作。5.2 什么時(shí)候用 __int128什么時(shí)候用大數(shù)庫(kù)選型的原則很簡(jiǎn)單數(shù)字不超過(guò) 38 位且運(yùn)算以加減乘為主用__int128零依賴(lài)代碼簡(jiǎn)單。數(shù)字超過(guò) 38 位或者需要高精度除法用大數(shù)庫(kù)如 GMP或者手寫(xiě)高精度。只需要中間結(jié)果不溢出最終結(jié)果在 long long 范圍內(nèi)用__int128做中間類(lèi)型這是最佳場(chǎng)景。提示如果你的程序只需要在特定平臺(tái)上運(yùn)行可以先測(cè)試__int128是否可用。如果不可用可以用long double做中間類(lèi)型精度 64 位尾數(shù)但要注意精度損失。5.3 在競(jìng)賽中的使用建議競(jìng)賽中時(shí)間緊張__int128的輸入輸出函數(shù)建議提前準(zhǔn)備好模板。我通常會(huì)在代碼開(kāi)頭定義好read_int128和print_int128需要的時(shí)候直接調(diào)用。另外如果題目只要求輸出最終結(jié)果中間過(guò)程可以用__int128輸出時(shí)轉(zhuǎn)成字符串。還有一點(diǎn)有些在線(xiàn)評(píng)測(cè)系統(tǒng)OJ的編譯器版本較老可能不支持__int128。提交前最好先在本地測(cè)試一下或者查一下 OJ 的編譯器信息。6. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄6.1 編譯報(bào)錯(cuò)unknown type name __int128這是最常見(jiàn)的問(wèn)題原因通常是用的是 MSVC 編譯器Visual Studio 默認(rèn)編譯器。MSVC 不支持__int128需要換 MinGW 或者 Clang。編譯目標(biāo)不是 64 位。32 位平臺(tái)可能不支持。編譯器版本太老。GCC 4.6 以上才支持__int128。解決方法檢查編譯器類(lèi)型和版本確認(rèn)是 64 位 GCC 或 Clang。6.2 輸出結(jié)果不對(duì)負(fù)數(shù)輸出異常如果輸出負(fù)數(shù)時(shí)出現(xiàn)亂碼或者錯(cuò)誤結(jié)果檢查輸出函數(shù)中負(fù)號(hào)的處理。常見(jiàn)錯(cuò)誤是忘記處理x 0的情況導(dǎo)致輸出空字符串。負(fù)數(shù)取反后仍然按有符號(hào)處理導(dǎo)致溢出。對(duì)于__int128的最小值取反會(huì)溢出但這種情況極少遇到。6.3 輸入函數(shù)吃掉了后續(xù)字符前面提到過(guò)重載時(shí)最后一個(gè)非數(shù)字字符會(huì)被消耗掉。如果后續(xù)還要讀其他內(nèi)容需要在輸入函數(shù)中把字符放回去is.unget(ch);或者在讀取數(shù)字后手動(dòng)跳過(guò)空白字符。6.4 性能問(wèn)題除法太慢如果程序中大量使用__int128的除法和取模性能會(huì)明顯下降。優(yōu)化方法能用乘法代替除法的地方盡量用乘法。如果除數(shù)是常數(shù)編譯器可能會(huì)優(yōu)化成乘法移位。把__int128的運(yùn)算集中在必要的地方不要全程用它。6.5 常見(jiàn)問(wèn)題速查表問(wèn)題原因解決方法編譯報(bào)錯(cuò) unknown type編譯器不支持換 GCC/Clang 64 位cout 無(wú)法輸出沒(méi)有重載 自己寫(xiě)輸出函數(shù)cin 無(wú)法輸入沒(méi)有重載 自己寫(xiě)輸入函數(shù)輸出負(fù)數(shù)亂碼負(fù)號(hào)處理錯(cuò)誤檢查輸出函數(shù)邏輯輸入后后續(xù)讀取異常字符被吃掉用 unget 放回字符除法性能差軟件模擬減少除法次數(shù)結(jié)果溢出超過(guò) 38 位改用大數(shù)庫(kù)6.6 一個(gè)完整的可運(yùn)行示例最后給一個(gè)完整的示例把輸入、計(jì)算、輸出串起來(lái)#include bits/stdc.h using namespace std; __int128 read() { __int128 x 0; int f 1; char ch getchar(); while (ch 0 || ch 9) { if (ch -) f -1; ch getchar(); } while (ch 0 ch 9) { x x * 10 (ch - 0); ch getchar(); } return x * f; } void print(__int128 x) { if (x 0) { putchar(-); x -x; } if (x 0) { putchar(0); return; } char buf[50]; int len 0; while (x 0) { buf[len] 0 (int)(x % 10); x / 10; } for (int i len - 1; i 0; i--) putchar(buf[i]); } int main() { __int128 a read(); __int128 b read(); print(a * b); putchar(\n); return 0; }這個(gè)程序可以讀入兩個(gè)超大整數(shù)并輸出它們的乘積。你可以用123456789012345678901234567890這樣的輸入來(lái)測(cè)試結(jié)果會(huì)正確輸出。我在實(shí)際使用中的體會(huì)是__int128最大的價(jià)值不是“能存更大的數(shù)”而是“讓中間計(jì)算不溢出”。很多 bug 的根源就是中間結(jié)果溢出而__int128是最輕量的解決方案。把輸入輸出函數(shù)準(zhǔn)備好剩下的就是正常寫(xiě)代碼。唯一要記住的是它不是標(biāo)準(zhǔn)類(lèi)型換編譯器可能就沒(méi)了所以關(guān)鍵代碼最好加個(gè)#ifdef做兼容處理。