0x3f3f3f3f为何成图论INF首选：溢出与memset避坑

1. 三个十六进制常量到底是什么来路

1.1 从一串奇怪的数字说起

0x7fffffff、0x3fffffff、0x3f3f3f3f，这三个数我在写图论、写状态压缩、写嵌入式寄存器操作的时候几乎每次都要敲一遍。很多刚入行的朋友看到这一串 f 会有点懵：这不就是一堆十六进制的字母吗，凭什么它们跟"无穷大"有关系？说白了，它们都是 32 位有符号整数能表示的某个特定大数值，被人为挑出来当作"大于一切合法答案"的标记值用。你在做最短路、做 DP、做贪心求最小值的时候，总得有个初始值去填充那些还没算出来的位置，而这个初始值必须足够大，大到任何一条真实路径、任何一个真实方案都比它小；同时又得足够稳，稳到你在它上面做加法、做取最小的时候不会突然掉进负数区间。

这三个常量分别对应三个精确的十进制数：0x7fffffff 是 2147483647，也就是 32 位有符号整数的最大值，标准头文件里的 INT_MAX 就是它；0x3fffffff 是 1073741823，等于 2 的 30 次方减一，大约是 INT_MAX 的一半略少一点点；0x3f3f3f3f 是 1061109567，它有个特别好记的结构——四个字节全是 0x3f，写成乘法就是 0x3f 乘以 0x01010101。前两个数是"整数意义上的大"，第三个数是"字节意义上的齐整"，这个区别是后面所有选型讨论的根子。

适合谁看这篇？如果你在刷算法题、在写图论模板、在做嵌入式里那些需要初始化一片缓冲区的活，或者你被"为什么我的距离数组突然变成负数了"这类问题折磨过，那这篇基本就是给你写的。我下面会把每个数的边界、为什么老手不直接用 INT_MAX、memset 那个坑怎么绕、以及实际代码里怎么落地，一条条拆开讲。

1.2 三个数值的设计意图差异

先说 0x7fffffff。它的二进制是 0111 1111 1111 1111 1111 1111 1111 1111，最高位是 0，后面 31 个 1。这是有符号 32 位整数的天花板，再加一就会翻到 0x80000000，也就是 -2147483648。它出现在这里的理由很直白：没有比它更大的正数了，所以我用它表示"不可达""无解""无限远"在语义上是最准确的。很多标准库、很多接口定义里的"最大值哨兵"用的都是它。

再说 0x3fffffff。二进制是 0011 1111 ...，最高两位是 0，后面 30 个 1。它比 INT_MAX 小，但小得不多，仍然是十亿量级。选它的核心动机是留出安全余量：两个 0x3fffffff 加起来是 0x7ffffffe，也就是 2147483646，刚好比 INT_MAX 小 1，不溢出。这一点非常关键，因为在图算法里你经常要算dist[u] + w，如果两个 dist 都是"无穷大"，这个加法就必须保证还是正数，否则取 min 就会选出一个负数，整个算法直接崩掉。

第三个 0x3f3f3f3f 更讲究。它本身约 1.06 乘以 10 的 9 次方，比 0x3fffffff 略小，但两个相加是 0x7e7e7e7e，约 2.12 乘以 10 的 9 次方，距离 INT_MAX 还留着十亿多的余量。也就是说，你不仅能让两个 INF 相加不溢出，甚至还能再往上叠加一个中等规模的边权而不出事。这个"余量思维"是三个常量里最值得学的一点，后面我会专门算给你看。

这张表建议你直接记住最后一行那个"余量约 2.5 亿"，它决定了你在什么规模的边权下可以放心用 0x3f3f3f3f 当 INF。边权如果都是 10 的 4 次方到 10 的 6 次方这个量级，那随便加，一点问题没有；边权要是能到 10 的 9 次方，那就得留个心眼，稍微算一算。

2. 为什么老手偏爱 0x3f3f3f3f 而不是 INT_MAX

2.1 两个"无穷大"相加还能不能保住正数

我见过太多初学者的模板是这么写的：const int INF = INT_MAX;，然后 Dijkstra 里写if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;。这段代码在一部分数据上跑得好好的，换一组数据就莫名其妙输出一个巨大的负数。原因就在这个加法上：当dist[u]是 INT_MAX、w是个正数的时候，INT_MAX + w在补码实现下回绕成负数，于是dist[u] + w < dist[v]这个判断居然成立了，dist[v] 被更新成一个负数，后面所有依赖它的松弛全部污染。这种 bug 最难查，因为它不报错、不越界，只是答案悄悄错了。

换成 0x3f3f3f3f 之后，同样的场景：dist[u] + w是 1061109567 加上一个边权。只要你边权不超过十亿出头，结果仍然是个正数，而且仍然比任何真实的最短路径大得多，取 min 的时候自然会输给真实的 dist[v]，逻辑就对了。这就是为什么大家说 0x3f3f3f3f 是"带保护的无穷大"——它用一点点数值余量，换掉了整整一类溢出隐患。

0x3fffffff 其实也能满足这个要求，两个相加是 0x7ffffffe，也不溢出。但它有个致命短板：余量只有 1。也就是说0x3fffffff + 1还能活，0x3fffffff + 2就翻车了。你在做 Floyd 的时候要算dist[i][k] + dist[k][j]，两个都是 0x3fffffff 的时候结果是 0x7ffffffe，勉强安全；但如果代码里还有别的地方顺手再叠一个值上去，就立刻越界。相比之下 0x3f3f3f3f 给出的余量宽裕得多，容错空间完全不是一个级别。

2.2 memset 整片初始化这个隐藏福利

这才是我真正偏爱 0x3f3f3f3f 的理由。C 里的memset是按字节填充的，它把目标内存的每一个字节都写成你给的那个值。而 0x3f3f3f3f 的四个字节恰好全是 0x3f，所以memset(arr, 0x3f, sizeof(arr))执行完之后，一个 int 数组里每个元素都精确地变成了 0x3f3f3f3f。这一行代码搞定整个数组的初始化，比写 for 循环快得多，而且在大数组上差距很明显。

换另外两个常量试试就明白了。0x7fffffff 的字节是 0xff、0xff、0xff、0x7f，四个字节不一样，memset 填不出来；memset(arr, 0xff, ...)得到的是 0xffffffff，也就是 -1，不是你要的。0x3fffffff 的字节是 0xff、0xff、0xff、0x3f，同样不齐整，memset 也无能为力，只能老老实实写循环或者用 fill。

注意：这里的结论只在"四字节 int、小端或大端不影响字节内容"的前提下成立，因为 memset 是按字节写，字节内容一样，拼起来的整数值就一样。32 位 int 是这个结论的标准场景，如果你在 64 位 long 上想用同样的技巧，对应的是 0x3f3f3f3f3f3f3f3f。

我给一个直观的对比，你在自己的机器上跑一遍就明白了：

#include <stdio.h> #include <string.h> int a[5], b[5], c[5]; int main() { memset(a, 0x3f, sizeof(a)); // 每个元素 0x3f3f3f3f memset(b, 0x7f, sizeof(b)); // 每个元素 0x7f7f7f7f memset(c, 0xff, sizeof(c)); // 每个元素 0xffffffff 即 -1 for (int i = 0; i < 5; i++) printf("%d %d %d\n", a[i], b[i], c[i]); return 0; }

跑出来你会看到第一列全是 1061109567，第二列是 2139062143（这个数比 INT_MAX 小，也能当 INF 用，是另一个流派），第三列全是 -1。这个实验我建议每个刚接触图论的人都亲手做一次，比看十篇文章都管用。

2.3 与 0x3fffffff 的分工：一个防溢出，一个当掩码

那 0x3fffffff 是不是就没用了？不是。它在另一个场景里非常常见：位掩码。因为它二进制是 30 个 1，x & 0x3fffffff的效果就是保留 x 的低 30 位、把高 2 位清零。在状态压缩、哈希、位图这类操作里，需要一个"取低 N 位"的掩码时，0x3fffffff 拿起来就能用。

还有一类场景是做数组下标的中位切分、大整数拆分、或者某些需要"比一半少一点"的边界值判断。因为 0x3fffffff 恰好小于 INT_MAX 的一半左右，两个这样的值相加刚好卡在正数区间边缘，所以有些人在做"两个中等值相加不能溢出"的约束时会选它。

我自己的习惯是：当作 INF 用、且需要 memset 的时候，用 0x3f3f3f3f；当作位掩码用，用 0x3fffffff；只有当语义上确实需要"整数上限"这个精确概念（比如做二分上界、某些接口约定）时，才用 0x7fffffff。三个数各司其职，不要混着用，混用是 bug 的温床。

3. 数值边界的手算过程与验证方法

3.1 二进制拆解与溢出临界点计算

我想把溢出的临界点算清楚，因为这是很多人口口相传却从没自己推过的东西。32 位有符号整数的表示范围是 -2147483648 到 2147483647，边界值是 0x7fffffff 和 0x80000000。当你做0x7fffffff + 1的时候，二进制上就是从 0111...1111 加 1 变成 1000...0000，最高位从 0 变 1，符号位被置上，解释成有符号数就是 -2147483648。这不是"错误"，这是补码运算的自然结果，但对算法逻辑来说就是灾难。

再看 0x3fffffff。它等于 2 的 30 次方减一。两倍就是 2 的 31 次方减二，即 2147483646，二进制 0111...1110，最高位仍是 0。所以它离溢出只差一步：只要再加 1，就变成 0x7fffffff，还是正的；再加 1 就变成 0x80000000，翻了。所以它的安全边界是"最多只能叠加 1"。这个数字太紧了，紧到我不敢在实际代码里依赖它。

0x3f3f3f3f 的推导稍微绕一点，但很有意思。它的四个字节都是 0x3f，也就是十进制 63。所以它等于 63 乘以 (1 + 256 + 65536 + 16777216)，括号里是 16843009，乘出来 1061109567。两倍是 2122219134，二进制 0111 1110 0111 1110 0111 1110 0111 1110，最高位还是 0。距离 INT_MAX 的差值 = 2147483647 减 2122219134 等于 25264513，也就是大约 2500 万。这个数字看起来不大，但注意这是"两个 INF 相加后"剩下的余量，实际单个 INF 到溢出线之间有一亿多（2147483647 减 1061109567 等于 1086374080，约 10.8 亿）的空间，所以你在 INF 上叠一个常见的边权是完全安全的。

我把它整理成一个可以直接对照的表：

最后一行值得特别注意：如果你的边权能到 10 的 9 次方，那么一次加法就吃掉了将近一半的余量。这时候如果你还在别的地方做了第二次加法，就要警惕了。我在一个模拟项目里就遇到过边权是1 <= w <= 1e9的最短路，当时有人图省事还是用 0x3f3f3f3f，结果在 Floyd 的三重循环里dist[i][k] + dist[k][j]两个都是 INF 的时候还好（0x7e7e7e7e 没溢出），但如果代码里额外写了个+ 额外代价，就真的越界了。后来改成 0x1fffffff 才稳。所以边权上限决定了你要不要换更保守的 INF，这个没有标准答案，得看你自己的数据范围。

3.2 用几行代码把边界跑一遍

纸上算完，我习惯再用代码验证一次，因为不同编译器对溢出行为的处理不完全一样，亲眼看到结果心里才踏实。这段代码你可以直接复制到任意在线编译器里跑：

#include <stdio.h> #include <limits.h> int main() { int a = 0x7fffffff; int b = 0x3fffffff; int c = 0x3f3f3f3f; printf("a=%d b=%d c=%d\n", a, b, c); printf("a+1=%d\n", a + 1); // 负数，演示回绕 printf("b*2=%d\n", b * 2); // 正数，余量极小 printf("c*2=%d\n", c * 2); // 正数，余量充足 printf("c+1000000000=%d\n", c + 1000000000); printf("INT_MAX-c=%d\n", INT_MAX - c); return 0; }

如果你用 gcc 加-fwrapv编译，有符号溢出会被定义为回绕，结果就是上面表格里那套；如果不开这个选项，理论上是有符号溢出属于未定义行为（UB），编译器可以做任何事，虽然实际环境中大多是回绕。这就是为什么我强烈建议不要写依赖溢出的代码——你以为的"回绕"在别的优化等级下可能被优化成完全不同的东西。用 0x3f3f3f3f 从源头上避开这个问题，比事后打补丁靠谱得多。

4. 真刀真枪的实操：最短路与 DP 里的初始化模板

4.1 图的存储与 INF 的填充

我拿一个标准的邻接矩阵 Dijkstra 举例，这套写法在小规模图上足够用，也是最能体现 INF 选型的地方。核心就两步：先把整张距离矩阵铺成 0x3f3f3f3f，再把起点的距离设成 0，然后正常松弛。矩阵的对角线要看你怎么定义，如果是求"点 i 到点 i 的距离"，那应该是 0；如果你是用它来表示"有没有边"，那对角可以先留着 INF。

#include <stdio.h> #include <string.h> #define MAXN 1005 #define INF 0x3f3f3f3f int dist[MAXN]; int g[MAXN][MAXN]; int vis[MAXN]; void dijkstra(int n, int s) { memset(dist, 0x3f, sizeof(dist)); // 每个 dist 都是 0x3f3f3f3f memset(vis, 0, sizeof(vis)); dist[s] = 0; for (int it = 0; it < n; it++) { int u = -1; for (int i = 1; i <= n; i++) if (!vis[i] && (u == -1 || dist[i] < dist[u])) u = i; if (u == -1 || dist[u] == INF) break; vis[u] = 1; for (int v = 1; v <= n; v++) { if (dist[u] + g[u][v] < dist[v]) dist[v] = dist[u] + g[u][v]; } } }

这里有几个细节值得说。第一，memset(dist, 0x3f, sizeof(dist))之后你可以打印一下dist[0]确认它确实是 1061109567，这一步别省，我见过有人 sizeof 写错（比如写成sizeof(dist[0])），结果只填了头 4 个字节，后面全是垃圾值，调了半天才发现。第二，if (u == -1 || dist[u] == INF) break;这个提前退出用等号是可以的，因为初始值就是精确的 INF，没被污染过；但如果你在某些版本里会往 INF 上加东西，就必须改成dist[u] >= INF或者dist[u] > INF / 2，后面会细说。

如果换用邻接表，初始化的套路一样，只是 g 换成了 vector 或者数组模拟的链表。我在一个跨平台的小工具里就吃过亏：邻接表里每条边都用memset初始化成 0x3f3f3f3f 表示"暂不可达"，结果有一次图里真的存在一条权重恰好等于 0x3f3f3f3f 的边（那是人为构造的极端测试），算法把它误判成"无边"。这种 bug 只会在压力测试里冒出来，日常小数据永远看不见。教训是：INF 要和合法数据的值域拉开至少一个数量级，如果你的边权能开到 10 的 9 次方，INF 就不要用 0x3f3f3f3f 了。

4.2 松弛与判定条件怎么写才不翻车

松弛语句看着简单，其实是事故高发区。我总结下来有三条铁律，照着写基本不会错。

第一条，先判可达再相加。如果 dist[u] 还是 INF，那dist[u] + w算出来即使不溢出，也还是个大数，没有意义，不如直接跳过。这样写的好处是逻辑清晰，顺便还能躲避一部分溢出风险：

if (dist[u] != INF && dist[u] + w < dist[v]) dist[v] = dist[u] + w;

第二条，判定不可达用大于 INF 的一半，而不是等于 INF。原因是你可能在某些版本里给 INF 加过小量，或者做过多源初始化，dist 里可能残留 INF 加某个小值。用dist[v] > INF / 2判断更宽容，这也是网上流传最广的写法：

if (dist[v] > INF / 2) printf("不可达\n"); else printf("%d\n", dist[v]);

第三条，Floyd 的三重循环一定要把 INF 的加法放在脑里过一遍。dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])，最坏情况是 i 到 k 和 k 到 j 都不通，两项都是 0x3f3f3f3f，加起来 0x7e7e7e7e，是正的，不会把 min 带偏。这正是 0x3f3f3f3f 最经典的用武之地。如果你用 INT_MAX，这一步就直接是负数，Floyd 会给出完全错误的答案，而且错得很隐蔽。

for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];

这段代码我几乎能默写出来，但我还是建议你每次写之前想一句："这里两个 INF 相加会不会溢出？"想完再敲，能省掉大量调试时间。

5. 踩坑实录与常见问题速查

5.1 几个高频翻车现场

第一个坑：memset 之后值不是你以为的那个数。有一次我在一个图像处理的小 demo 里，想用memset把 int 数组初始化成 0x3fffffff，跑出来发现每个元素变成了 0x3f3f3f3f。原因很蠢——我写的是memset(arr, 0x3f, ...)，还以为是 0x3fffffff。字节填充和整数赋值是两个概念，memset 只认字节。要精确填 0x3fffffff，只能用循环或者for (i = 0; i < n; i++) arr[i] = 0x3fffffff;，没有捷径。

第二个坑：dist 数组声明成无符号类型。如果写成unsigned int dist[N]，那么一开始dist[u] != INF这种判断会失效，因为无符号没有负数，某些比较的语义和你预期不一致。我见过有人在无符号数组上判断"是否大于 INF"，逻辑上没问题，但一旦有负权边（虽然 Dijkstra 不支持，但有人混用）就会静默出错。最稳的做法是距离数组一律用有符号 int，INF 也用有符号常量。

第三个坑：INF 太小，被真实路径"打败"。这个反直觉但真实存在。如果图里存在一条总权重超过 0x3f3f3f3f 的合法路径，那么用 0x3f3f3f3f 当 INF 就会导致这条路径被当成"不可达"。我在一个模拟项目里碰到过顶点数很少但边权极大的图，边长都是 10 的 8 次方级别，路径长度轻松破十亿，那时候只能换更保守的值或者直接改用long long。经验是：先用数据的理论上界乘一下最大路径长度，看看会不会超过 10.6 亿，超了就换。

第四个坑：把 INF 当普通数参与排序或计数。有一次统计"有多少个不可达点"，代码写的是if (dist[i] == INF) cnt++;，结果机器上算出来比实际少。查下来是因为某些 dist 被更新成了 INF 加一个很小的值（代码里有个+0的冗余操作导致精度损失？其实是别的路径污染）。改成> INF / 2就好了。这个条件看着粗糙，实际最稳。

5.2 常见问题速查表

这张表我建议存下来，出问题的时候按行对一遍，八成能定位。特别提醒"多组数据串味"这一条，它跟 INF 关系不大但经常和 INF 一起出现：很多人只 memset 了 dist 忘了清 vis，或者只清了前 n 个位置，结果上一组数据的残留把这一组污染了。养成"每组数据开始前把该清的都清一遍"的习惯，比任何技巧都管用。

6. 我个人的一些使用习惯

写到这里我想聊聊自己这些年攒下来的一些习惯，不算什么高级技巧，但确实让我少踩了很多坑。

参数不要散落在代码里。我现在的做法是统一在文件头写#define INF 0x3f3f3f3f，然后全篇只用 INF 这个符号，绝对不直接在松弛语句里写十六进制数。这样以后要换值（比如换 long long 版本）只改一处，不用满代码搜索替换。而且读代码的人一眼就知道这个数是"无穷大"的意思，不用去猜 0x3fffffff 到底想表达什么。

64 位场景记得同步换。如果我把距离数组改成long long，那 INF 也要换成0x3f3f3f3f3f3f3f3f，同时 memset 用的是同一个 0x3f，非常整齐。这个配套关系是 0x3f3f3f3f 这套体系最舒服的地方：从 32 位升到 64 位，填充字节不用变，只是字节数变多，改动量极小。而如果原来用的是 0x3fffffff 再升 64 位，就得重新设计一个"四个字节同样内容"的常量，白折腾。

写完先做一次边界自测。我的固定动作是：造一张只有两个点、一条边的图，边权设成数据范围的最大值，跑一遍看看结果对不对；再造一张完全不连通的图，看看不可达判定是不是准确。这两个小测试花不了一分钟，但能覆盖 INF 相关的大半问题。我在一个算法练习项目里就是靠这个习惯提前发现了一次 INF 太小的问题，省下了后面几个小时的黑盒调试。

不确定的时候往保守走。如果实在拿不准边权会不会把 INF 撑爆，那就直接上long long加 0x3f3f3f3f3f3f3f3f。多占一点内存、慢一点，但换来的是彻底不用担心溢出，我觉得这笔买卖很划算。性能优化是在正确性之后才谈的事，顺序反了就是给自己挖坑。

最后分享一个小技巧：调试的时候把 INF 临时改成一个小的、好认的数，比如 999999，这样你打印矩阵的时候一眼就能看出哪些位置还是初始值、哪些已经被更新过了。确认逻辑没问题再改回 0x3f3f3f3f 正式跑。这个土办法在查 Floyd 矩阵的时候特别好用，因为矩阵一大，1061109567 这种数字在满屏输出里几乎不可辨认，换成 999999 立刻就清晰了。