算法竞赛 0x3F3F3F3F 特殊数字和技巧

原文链接:https://blog.csdn.net/jiange_zh/article/details/50198097

在算法竞赛中, 我们常常需要用到一个无穷大的值, 对于我来说, 大多数时间我会根据具体问题取一个 $\text{99999999}$ 之类的数 (显得很不专业啊!)

在网上看别人代码的时候, 经常会看到他们把 $INF$ 设为 $\text{0x7FFFFFFF}$, 奇怪为什么设一个这么奇怪的十六进制数, 一查才知道, 因为这是 $\text{32}$ 位 $int$ 的最大值. 如果这个无穷大只用于一般的比较 (比如求最小值时 $min$ 变量的初值), 那么 $\text{0x7FFFFFFF}$ 确实是一个完美的选择.

但是更多情况下, $\text{0x7FFFFFFF}$ 并不是一个好的选择, 比如在最短路径算法中, 我们使用松弛操作:

if (d[u] + w[u][v] < d[v])
    d[v] = d[u]+w[u][v];

如果 $u$, $v$ 之间没有边, 那么 $w[u][v]=INF$, 如果我们的 $INF$ 取 $\text{0x7FFFFFFF}$, 那么 $d[u] + w[u][v]$ 会溢出而变成负数, 我们的松弛操作便出错了!

准确来说, $\text{0x7FFFFFFF}$ 不能满足无穷大加一个有穷的数依然是无穷大这个条件, 它会变成了一个很小的负数.

更进一步的, 如果有一个数能够满足无穷大加无穷大依然是无穷大, 那么就更好了!

前阵子无意中看到了一个不一样的取值, $INF=\text{0x3F3F3F3F}$, 这时我又郁闷了, 这个值又代表的是什么? 于是我去寻找答案, 发现这个值的设置真的很精妙!

$\text{0x3F3F3F3F}$ 的十进制是 $1061109567$, 是 $10^9$ 级别的 (和 $\text{0x7FFFFFFF}$ 一个数量级), 而一般场合下的数据都是小于 $10^9$ 的, 所以它可以作为无穷大使用而不致出现数据大于无穷大的情形.

另一方面, 由于一般的数据都不会大于 $10^9$, 所以当我们把无穷大加上一个数据时, 它并不会溢出 (这就满足了无穷大加一个有穷的数依然是无穷大), 事实上 $\text{0x3F3F3F3F} + \text{0x3F3F3F3F} = 2122219134$, 这非常大但却没有超过 $32$ 位 $int$ 的表示范围, 所以 $\text{0x3F3F3F3F}$ 还满足了我们无穷大加无穷大还是无穷大的需求.

最后, $\text{0x3F3F3F3F}$ 还能给我们带来一个意想不到的额外好处:

如果我们想要将某个数组清零, 我们通常会使用 memset(a, 0, sizeof(a)), 方便又高效, 但是当我们想将某个数组全部赋值为无穷大时, 就不能使用 memset 函数而得自己写循环了, 因为 memset 是按字节操作的, 它能够对数组清零是因为 $0$ 的每个字节都是 $0$(一般我们只有赋值为 $-1$ 和 $0$ 的时候才使用它). 现在好了, 如果我们将无穷大设为 $\text{0x3F3F3F3F}$, 那么奇迹就发生了, $\text{0x3F3F3F3F}$ 的每个字节都是 $\text{0x3F}$, 所以要把一段内存全部置为无穷大, 我们只需要memset(a, 0x3f, sizeof(a)).

所以在通常的场合下, $\text{0x3F3F3F3F}$ 真的是一个非常棒的选择!