unsplash.com/@polina_art
为什么是 0x3f
?
写 dijkstra
等等经典算法时;我们希望 dist
数组初始值是 无穷大
的数,常常会用到 memset(dist, 0x3f, sizeof dist)
。为什么要给 dist
赋值为 0x3f3f3f3f
呢?
首先我们看一下 0x3f
有多大。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int a[1];
memset(a, 0x3f, 4);
cout << a[0];
}
输出 1061109567
,是10^9
级别的。
memset
按照字节赋值,因此我们把 4 个 0011 1111
填充到 32 位的 int
上。但问题是,为什么不是 0x4f
或者 0x5f
?
首先 10^9
级别足够大,其次,也是最重要的,0x3f3f3f3f + 0x3f3f3f3f
等于 0x7e7e7e7e
, 不会爆int 。
在很多算法中,我们需要进行诸如 dist[j] > dist[t] + w[t][j]
之类的判断,如果两个大于 0x3f3f3f3f
的数相加,那么后果不堪设想。因为溢出并不会报错,算法逻辑复杂,我们往往很难定位真正的错误。
附:近期收集了很多 C++ STL 的妙用... 如下图片的 C++ 确实有点感触。
笔记主要放在 github/PiperLiu/ACMOI_Journey[1] 的“经验”中。有空一并整理。
此外,memset
对于不同的数据类型初始值当然是不同的,有一篇极好的文章:【自用】 memset对于int、long long、float、double 的极值怎么清[2],阅读原文也可查看。比如 int
对应 0x3f
, float
对应 0x4f
。
值得注意的是,我最近在看歪总代码时,用到初始化 -INF
,直接 memset(a, -0x3f, sizeof a)
也是可以的,无非就是 0x3f
取反加一嘛,从 0011 1111
变为 1100 0001
。但是相加会爆。
[1]
github/PiperLiu/ACMOI_Journey: https://github.com/PiperLiu/ACMOI_Journey
[2]
【自用】 memset对于int、long long、float、double 的极值怎么清: https://blog.csdn.net/vmurder/article/details/46537613