1. 為什么需要 __int128從 long long 的邊界說(shuō)起做算法題或者寫(xiě)數(shù)值計(jì)算程序的時(shí)候幾乎每個(gè)人都遇到過(guò)這樣的場(chǎng)景題目要求對(duì)兩個(gè)大整數(shù)做乘法結(jié)果要對(duì)某個(gè)數(shù)取模你信心滿滿地寫(xiě)了long long本地樣例全過(guò)一提交就 WA盯著代碼看了半小時(shí)才發(fā)現(xiàn)——溢出了。long long是有符號(hào) 64 位整數(shù)能表示的范圍是 -9223372036854775808 到 9223372036854775807也就是大約 9.2×10^18。這個(gè)范圍聽(tīng)起來(lái)很大但在算法競(jìng)賽和某些工程場(chǎng)景里它經(jīng)常不夠用。最典型的例子就是兩個(gè) 10^9 級(jí)別的數(shù)相乘結(jié)果直接沖到 10^18 量級(jí)如果還要再乘一個(gè)數(shù)或者累加多次溢出幾乎是必然的。這時(shí)候很多人的第一反應(yīng)是用大數(shù)庫(kù)比如 Java 的BigInteger或者 Python 的原生大整數(shù)。但在 C 里標(biāo)準(zhǔn)庫(kù)并沒(méi)有提供任意精度整數(shù)。手寫(xiě)高精度用數(shù)組模擬當(dāng)然可以但代碼量大、容易出錯(cuò)、性能也不一定好。而__int128就是 GCC/Clang 提供的一個(gè)中間檔解決方案——它比long long大一圈能表示到約 1.7×10^38足以覆蓋絕大多數(shù)算法題和工程計(jì)算的需求而且它是編譯器原生支持的運(yùn)算速度接近硬件級(jí)別用起來(lái)和普通整數(shù)幾乎一樣。這篇文章就是圍繞__int128展開(kāi)的。我會(huì)從它的本質(zhì)、適用場(chǎng)景、輸入輸出的坑、實(shí)際代碼模板一直講到常見(jiàn)問(wèn)題的排查。適合正在刷算法題、參加競(jìng)賽、或者寫(xiě)數(shù)值計(jì)算程序時(shí)被溢出折磨過(guò)的 C 程序員。如果你還在用long long硬扛大數(shù)乘法這篇內(nèi)容應(yīng)該能幫你省下不少調(diào)試時(shí)間。2. __int128 的本質(zhì)與適用邊界2.1 它到底是什么編譯器擴(kuò)展而非標(biāo)準(zhǔn)類型先說(shuō)一個(gè)很多人容易誤解的點(diǎn)__int128不是 C 標(biāo)準(zhǔn)的一部分。你在 C 標(biāo)準(zhǔn)文檔里翻不到它c(diǎn)stdint里也沒(méi)有它的定義。它是 GCC 和 Clang 這兩個(gè)編譯器提供的擴(kuò)展類型屬于編譯器送你用的東西。這意味著兩件事。第一如果你用的是 MSVCVisual Studio 自帶的編譯器__int128是不存在的編譯直接報(bào)錯(cuò)。第二即使你用 GCC/Clang代碼的可移植性也會(huì)打折扣——換到不支持它的平臺(tái)上就跑不了。所以用之前先確認(rèn)你的編譯環(huán)境這一點(diǎn)后面會(huì)專門講。它的完整寫(xiě)法是__int128有符號(hào)和unsigned __int128無(wú)符號(hào)。在 64 位平臺(tái)上它占 16 個(gè)字節(jié)也就是 128 位。有符號(hào)版本的范圍大約是 -1.7×10^38 到 1.7×10^38無(wú)符號(hào)版本是 0 到約 3.4×10^38。2.2 和 long long、大數(shù)庫(kù)的對(duì)比為了讓你直觀感受__int128的定位我整理了一張對(duì)比表類型位數(shù)大致范圍是否標(biāo)準(zhǔn)運(yùn)算速度輸入輸出支持int32±2.1×10^9是最快原生long long64±9.2×10^18是快原生__int128128±1.7×10^38否擴(kuò)展快需手寫(xiě)手寫(xiě)高精度任意任意是慢需手寫(xiě)boost::multiprecision任意任意是庫(kù)中等需適配從表里能看出來(lái)__int128的甜點(diǎn)區(qū)非常明確當(dāng)你的數(shù)值超過(guò) 64 位但不超過(guò) 128 位時(shí)它是最優(yōu)解。運(yùn)算速度接近原生整數(shù)代碼改動(dòng)量極小唯一麻煩的就是輸入輸出需要自己處理。2.3 什么時(shí)候該用它什么時(shí)候不該用我個(gè)人的判斷標(biāo)準(zhǔn)是這樣的該用算法題里兩個(gè) 10^9 級(jí)別的數(shù)相乘、快速冪取模、組合數(shù)計(jì)算、哈希時(shí)的乘法防溢出、某些幾何計(jì)算中的叉積。不該用需要超過(guò) 128 位的精度比如計(jì)算 100 的階乘這時(shí)候老老實(shí)實(shí)上高精度或者 boost需要跨平臺(tái)兼容 MSVC 的項(xiàng)目對(duì)性能極度敏感且能用 64 位搞定的場(chǎng)景。有一個(gè)很實(shí)用的技巧當(dāng)你寫(xiě)a * b擔(dān)心溢出時(shí)可以先把其中一個(gè)數(shù)轉(zhuǎn)成__int128再乘這樣整個(gè)表達(dá)式就按 128 位計(jì)算了。比如(__int128)a * b這是最常見(jiàn)的用法改動(dòng)量只有一個(gè)強(qiáng)制轉(zhuǎn)換。3. 輸入輸出的完整解決方案3.1 為什么 cin/cout 和 scanf/printf 都不行這是新手最容易踩的坑。你興沖沖地定義了一個(gè)__int128 x然后寫(xiě)cin x編譯器直接給你一長(zhǎng)串錯(cuò)誤信息。原因很簡(jiǎn)單標(biāo)準(zhǔn)庫(kù)的輸入輸出流只針對(duì)內(nèi)置的標(biāo)準(zhǔn)類型做了重載__int128是擴(kuò)展類型標(biāo)準(zhǔn)庫(kù)根本不認(rèn)識(shí)它。scanf和printf也一樣。你找不到%d之外的格式符能對(duì)應(yīng) 128 位整數(shù)%lld只能處理 64 位。所以輸入輸出必須自己寫(xiě)函數(shù)。3.2 手寫(xiě)輸入函數(shù)逐字符解析輸入的核心思路是把數(shù)字當(dāng)成字符串讀進(jìn)來(lái)逐位累加。因?yàn)開(kāi)_int128本身支持乘 10 和加個(gè)位數(shù)的運(yùn)算所以這個(gè)過(guò)程很自然。#include bits/stdc.h using namespace std; __int128 read() { __int128 x 0, 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; }這段代碼的邏輯很直白先跳過(guò)所有非數(shù)字字符如果遇到負(fù)號(hào)就把符號(hào)位設(shè)成 -1然后每讀到一個(gè)數(shù)字字符就把當(dāng)前結(jié)果乘 10 再加上這個(gè)數(shù)字。getchar()比cin快很多適合大量輸入的場(chǎng)景。注意這個(gè)函數(shù)用的是getchar()如果你的程序里混用了cin要注意緩沖區(qū)同步問(wèn)題。穩(wěn)妥的做法是全程用 C 風(fēng)格輸入輸出或者在用cin之前加ios::sync_with_stdio(false)并避免混用。3.3 手寫(xiě)輸出函數(shù)遞歸或棧輸出比輸入稍微繞一點(diǎn)因?yàn)槟阋褦?shù)字拆成一個(gè)個(gè)字符。最優(yōu)雅的寫(xiě)法是遞歸void print(__int128 x) { if (x 0) { putchar(-); x -x; } if (x 9) print(x / 10); putchar(x % 10 0); }遞歸的思路是先把高位全部輸出再輸出最低位。x 9的時(shí)候遞歸處理x / 10這樣會(huì)一直深入到最高位然后逐層返回時(shí)輸出每一位。對(duì)于__int128來(lái)說(shuō)最多 39 位數(shù)字遞歸深度完全不用擔(dān)心棧溢出。如果你不喜歡遞歸也可以用字符數(shù)組手動(dòng)模擬void print(__int128 x) { if (x 0) { putchar(0); return; } if (x 0) { putchar(-); x -x; } char buf[50]; int len 0; while (x 0) { buf[len] 0 (x % 10); x / 10; } while (len--) putchar(buf[len]); }兩種寫(xiě)法效果一樣遞歸版更簡(jiǎn)潔數(shù)組版更直觀。我個(gè)人在比賽里習(xí)慣用遞歸版因?yàn)榇a短不容易寫(xiě)錯(cuò)。3.4 一個(gè)完整的輸入輸出模板把上面的東西拼起來(lái)就是一個(gè)可以直接抄的模板#include bits/stdc.h using namespace std; __int128 read() { __int128 x 0, 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 9) print(x / 10); putchar(x % 10 0); } int main() { __int128 a read(); __int128 b read(); print(a b); putchar(\n); print(a * b); putchar(\n); return 0; }這個(gè)模板我用了很多次實(shí)測(cè)在各種在線評(píng)測(cè)系統(tǒng)上都能穩(wěn)定運(yùn)行。注意print函數(shù)在輸出后不會(huì)自動(dòng)換行需要自己加putchar(\n)。4. 實(shí)戰(zhàn)場(chǎng)景與核心代碼4.1 場(chǎng)景一大數(shù)乘法防溢出這是__int128最經(jīng)典的用法。假設(shè)你要計(jì)算a * b % mod其中a、b、mod都是long long范圍內(nèi)的數(shù)。直接寫(xiě)a * b % mod在a和b都接近 10^9 時(shí)會(huì)溢出因?yàn)槌朔e達(dá)到 10^18 雖然還在long long范圍內(nèi)但如果a和b接近 10^18乘積就是 10^36直接爆掉。long long mul_mod(long long a, long long b, long long mod) { return (__int128)a * b % mod; }一行搞定。(__int128)a * b先把a(bǔ)提升到 128 位乘法的結(jié)果也是 128 位取模后再轉(zhuǎn)回long long。這個(gè)寫(xiě)法比快速乘用加法模擬乘法簡(jiǎn)潔得多而且速度快。4.2 場(chǎng)景二快速冪中的中間結(jié)果快速冪算法里每一步都要做base base * base % mod。如果mod接近 10^18base * base就會(huì)達(dá)到 10^36必須用__int128兜底long long fast_pow(long long base, long long exp, long long mod) { long long result 1; base % mod; while (exp 0) { if (exp 1) result (__int128)result * base % mod; base (__int128)base * base % mod; exp 1; } return result; }這段代碼在模數(shù)很大的時(shí)候特別有用比如某些數(shù)論題目里mod是 10^18 級(jí)別的質(zhì)數(shù)。4.3 場(chǎng)景三組合數(shù)計(jì)算計(jì)算組合數(shù) C(n, m) 時(shí)中間結(jié)果往往很大。如果題目要求輸出精確值而不是取模且 n 不太大比如 n ≤ 30可以用__int128直接算__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; }這里每一步都先乘后除保證整除。__int128能覆蓋 C(60, 30) 這樣的量級(jí)約 1.18×10^17再大就不行了。4.4 場(chǎng)景四哈希中的乘法字符串哈希或者多項(xiàng)式哈希里經(jīng)常要做hash hash * base ch這樣的運(yùn)算。如果base和hash都很大乘法會(huì)溢出。用__int128可以安全地計(jì)算后再取模const long long MOD 1000000000000000003LL; const long long BASE 131; long long compute_hash(const string s) { long long h 0; for (char c : s) { h ((__int128)h * BASE c) % MOD; } return h; }4.5 場(chǎng)景五幾何計(jì)算中的叉積計(jì)算多邊形面積或者判斷點(diǎn)在線段的哪一側(cè)時(shí)會(huì)用到叉積(x2-x1)*(y3-y1) - (x3-x1)*(y2-y1)。如果坐標(biāo)范圍是 10^9叉積的中間結(jié)果會(huì)達(dá)到 10^18 甚至更大用__int128可以避免精度問(wèn)題__int128 cross(__int128 x1, __int128 y1, __int128 x2, __int128 y2) { return x1 * y2 - x2 * y1; }5. 常見(jiàn)問(wèn)題與排查技巧5.1 編譯報(bào)錯(cuò)__int128 未定義最常見(jiàn)的原因是你用了 MSVC。__int128只在 GCC 和 Clang 上可用。如果你在 Windows 上用 Visual Studio需要換成 MinGW 或者 WSL 里的 GCC。在 VS Code 里配置 C/C 環(huán)境時(shí)也要注意選擇正確的編譯器。另一個(gè)可能的原因是你用的 GCC 版本太老。__int128從 GCC 4.6 開(kāi)始支持現(xiàn)在主流版本都沒(méi)問(wèn)題但如果你在某個(gè)老舊的在線評(píng)測(cè)系統(tǒng)上可能會(huì)遇到不支持的情況。5.2 輸出結(jié)果不對(duì)符號(hào)處理遺漏手寫(xiě)輸出函數(shù)時(shí)最容易忘的就是負(fù)號(hào)處理。如果你的print函數(shù)沒(méi)有處理x 0的情況負(fù)數(shù)會(huì)輸出成一堆亂碼。記住先判斷符號(hào)再取絕對(duì)值然后遞歸輸出。還有一個(gè)隱蔽的坑x -x在x是最小負(fù)數(shù)時(shí)會(huì)溢出。不過(guò)對(duì)于__int128來(lái)說(shuō)這個(gè)邊界值極其罕見(jiàn)實(shí)際使用中可以忽略。5.3 性能問(wèn)題輸入輸出太慢如果你用cin/cout配合手寫(xiě)的read/print可能會(huì)因?yàn)榫彌_區(qū)不同步導(dǎo)致性能下降。解決方案是全程用getchar/putchar或者加上ios::sync_with_stdio(false); cin.tie(0);。在大量輸入的場(chǎng)景下getchar版本的read函數(shù)比cin快 3 到 5 倍這個(gè)差距在數(shù)據(jù)量大的時(shí)候非常明顯。5.4 類型轉(zhuǎn)換的陷阱__int128和long long之間的隱式轉(zhuǎn)換有時(shí)候會(huì)出問(wèn)題。比如long long a 1000000000; long long b 1000000000; __int128 c a * b; // 錯(cuò)誤a*b 先按 long long 計(jì)算已經(jīng)溢出了正確的寫(xiě)法是__int128 c (__int128)a * b;強(qiáng)制先把a(bǔ)提升到 128 位。這個(gè)坑我踩過(guò)不止一次尤其是在表達(dá)式復(fù)雜的時(shí)候很容易忘記加轉(zhuǎn)換。5.5 常見(jiàn)問(wèn)題速查表問(wèn)題現(xiàn)象可能原因解決方法編譯報(bào)錯(cuò) __int128 未定義用了 MSVC 或老版本 GCC換 GCC/Clang升級(jí)編譯器輸出亂碼沒(méi)處理負(fù)號(hào)在 print 函數(shù)里先判斷符號(hào)結(jié)果溢出忘記強(qiáng)制類型轉(zhuǎn)換在乘法前加 (__int128)輸入輸出慢混用了 cin 和 getchar統(tǒng)一用 C 風(fēng)格 IO取模結(jié)果為負(fù)負(fù)數(shù)取模的符號(hào)問(wèn)題加 mod 再取模6. 幾個(gè)容易被忽略的細(xì)節(jié)6.1 無(wú)符號(hào)版本的取舍unsigned __int128的范圍是 0 到約 3.4×10^38比有符號(hào)版本大一倍。如果你的計(jì)算確定不會(huì)出現(xiàn)負(fù)數(shù)用無(wú)符號(hào)版本能多出一倍的表示范圍。但要注意無(wú)符號(hào)版本的輸入輸出函數(shù)需要單獨(dú)寫(xiě)不能直接復(fù)用有符號(hào)版本的代碼。6.2 和位運(yùn)算的配合__int128支持所有的位運(yùn)算與、或、異或、左移、右移。這在處理位掩碼或者狀態(tài)壓縮時(shí)很有用。比如(__int128)1 100可以生成一個(gè)第 100 位為 1 的數(shù)這在long long里是做不到的。6.3 在結(jié)構(gòu)體和類中使用__int128可以作為結(jié)構(gòu)體成員也可以作為函數(shù)參數(shù)和返回值。但要注意它不能直接用于printf和cin所以在結(jié)構(gòu)體的輸入輸出方法里也要用自定義函數(shù)。6.4 調(diào)試時(shí)的打印技巧調(diào)試的時(shí)候如果不想寫(xiě)完整的print函數(shù)可以用一個(gè)簡(jiǎn)單的宏#define PRINT(x) do { __int128 _t (x); if (_t 0) { putchar(-); _t -_t; } \ if (_t 9) print(_t / 10); putchar(_t % 10 0); } while(0)這樣在代碼里隨時(shí)可以PRINT(ans)查看中間結(jié)果不用每次都寫(xiě)完整的輸出語(yǔ)句。7. 我個(gè)人的使用體會(huì)用了幾年__int128最大的感受就是它填補(bǔ)了long long和高精度之間的空白而且填補(bǔ)得恰到好處。絕大多數(shù)算法題里數(shù)值范圍不會(huì)超過(guò) 128 位這時(shí)候用__int128比手寫(xiě)高精度省事太多性能也好得多。但我也踩過(guò)不少坑。最開(kāi)始不知道cin不支持它調(diào)了半天后來(lái)又在類型轉(zhuǎn)換上栽跟頭a * b忘了加(__int128)導(dǎo)致溢出再后來(lái)是在 MSVC 上編譯失敗才發(fā)現(xiàn)它不支持。這些坑現(xiàn)在都成了肌肉記憶寫(xiě)代碼的時(shí)候會(huì)下意識(shí)地檢查。如果你經(jīng)常做算法題或者寫(xiě)數(shù)值計(jì)算程序我建議把第 3.4 節(jié)那個(gè)模板保存下來(lái)需要的時(shí)候直接復(fù)制。輸入輸出這兩個(gè)函數(shù)是繞不過(guò)去的與其每次重寫(xiě)不如整理成自己的代碼片段庫(kù)。最后分享一個(gè)小技巧如果你不確定某個(gè)中間結(jié)果會(huì)不會(huì)超過(guò)long long可以先用__int128算一遍然后打印出來(lái)看看。如果結(jié)果在long long范圍內(nèi)再改回去用long long提升性能如果超了就保留__int128。這個(gè)先保守后優(yōu)化的策略能幫你在正確性和性能之間找到平衡。