编程中极值的选取

编程中极值的选取

很多时候,在编程中我们都需要把一些变量初始化为极大、极小值。下面是对于一些常见极值的比较。

TL; DR:

比较时用 0x7fffffff, 需要参与运算(如 a = max(a+b, c) )时, 用 0x3fffffff0x3f3f3f3f

不用数了, 7 个 f。

如果是 long long, 用 0x7fffffffffffffffLL0x3f3f3f3f3f3f3f3fLL0x3fffffffffffffffLL

15 个 f。

10000000

此类极值无疑是最简单的一种, 随手写即可。初学阶段可以使用,但是后期就会产生风险。

首先,如果手欠多写了几个 0, 会发生什么呢?

可以运行一下代码测试一下:

1
2
printf("%d", 10000000000);
// Outputs 1410065408

这是为什么呢? 注意, 在 C 语言中, 字面量也是有类型的。 $10000000000$的类型是 int,但是他超过了 int 所能表示的最大值 $2147483647$,所以溢出为了 $1410065408$。

其次,如果少写了几个 0,会发生什么呢?

”极大值“选取的不够大,程序就会算出错误的结果。

所以, 不建议这样选取极大值。

0x7fffffff

当需要进行比较类型的运算时,(如保存最小值的变量要用一个极大值初始化),可以初始化为0x7fffffff

原因:

  1. 他是 int 类型变量的最大值,绝大部分情境下足够大。
  2. 比 10 进制下 int 变量最大值$\left(2147483647\right)$更好记忆。 (7 后 7 个 f)

缺点:

因为它是 int 最大值,加上 1 都会溢出为负数。所以仅能在不需要进行算数运算,仅需要进行比较时使用。

0x3fffffff / 0x3f3f3f3f

需要极值参与的运算大部分情况下都是这样的:

1
2
a = max(a+b, c);
// a 和 b 可能是极大值

这种情况下,仅需要保证 $a+b$ 的过程不溢出,既保证$a \leq INT_MAX / 2$ 即可。所以,a 可以初始化为0x3fffffff。(一样还是 7 个 f)

同样,在图论题中,我们经常需要把一整个二维数组赋值为极值。这种情况下,0x3fffffff不能使用memset进行一次性赋值。因此,采用略小一些的 0x3f3f3f3f 就可以一次性用memset赋值:

1
2
int data[MAXN][MAXM];
memset(data, 0x3f, sizeof data);

还记得吗? memset 函数是对于给定大小数组的每个字节赋值为指定的值。