编程中的正无穷大和 memset 的原理

本文最后更新于:3 个月前

问题

用什么数字标记?

今天写 #120. 三角形最小路径和 的时候,用记忆化搜索的方式。其中需要用一个 int 整型 memo[i],来标记某点是否被计算过值;如果没有计算过,将计算后的值储存在 memo[i] 中。

我将 memo[i] 初始化为 -1,遍历时,如果发现该点上的 memo[i] 为 -1,则说明没有计算过,并将计算后的值储存在该点上的 memo[i] 中。

问题来了:计算后的值可能会是 -1,也可能会是 0,那我应该用什么数字去标记是否计算过呢?

无穷大

答案是,可以用 无穷大 来标记,即 int 的最大值:INT_MAX = 0x7fffffff。

因为 0x7fffffff 在正常数据运算中基本不可能出现。

新问题

那如何将数组全部初始化为无穷大?

我们知道,将数组清零,我们可以用 memset

int memo[100];
memset(memo, 0, sizeof(memo));

如果要将数组初始化为无穷大,是不是可以 memset(memo, 0x7fffffff, sizeof(memo)); ?答案是不行!

memset(memo, 0x7fffffff, sizeof(memo)); 最后执行的结果是 数组每个数都等 -1。因为 memset 是按照字节赋值的。

memset 原理

memset 是按照字节赋值的。举几个例子

  1. memset(memo, 0, sizeof(memo)); 是对 每个字节 都赋值为 0;以64位 int 为例,四个字节分别赋值为 0(最后该数字还是等于0)。
  2. memset(memo, -1, sizeof(memo)); 是对 每个字节 都赋值为 -1,-1 的补码是 1111 1111 1111 1111 1111 1111 1111 1111,存入 1 字节就是 1111 1111(高位舍弃),每个字节都是 1111 1111 ,那四个字节就是 1111 1111 1111 1111 1111 1111 1111 1111,所以该 int 数字还是 -1
  3. memset(memo, 0x7fffffff, sizeof(memo)); 是对 每个字节 都赋值为 0x7fffffff,整数的补码是本身,存入 1 字节就是 ff (高位舍弃),每个字节都是 ff,那四个字节就是 ffffffff, ffffffff 是 -1 的补码。(计算机打印十六进制时,打印的补码;打印十进制时,打印的是原码)。

所以 int数组 不可以用 memset 来初始化为 0x7fffffff。

那该怎么办呢?用 0x3f3f3f3f 代替 0x7fffffff。

0x3f3f3f3f

0x3f3f3f3f 和 0x7fffffff 是一个数量级的,也可以作为无穷大。

好处在于:

  • 0x3f3f3f3f 可以满足 无穷大 + 无穷大 = 无穷大 的设定。

  • 0x3f3f3f3f 可以用 memset 来初始化。

为什么 0x3f3f3f3f 可以用 memset 来初始化呢?

memset(memo, 0x3f3f3f3f, sizeof(memo)); 对每个字节都赋值为 0x3f3f3f3f,所以一个字节为 3f (高位舍弃),四个字节连在一起就是 0x3f3f3f3f,和原值大小一样。

新发现

在leetcode写#279. 完全平方数时,经测验发现,用 0x7fffffff 整个程序运行时间 200+ms,用 0x3f3f3f3f 运行时间 300+ms。

所以如果不使用 memset 的时候,用 0x7fffffff。

vector<int> a(n, 0x7fffffff);    // 运行更快。
vector<int> b(n, 0x3f3f3f3f);

本博客所有文章均个人原创,除特别声明外均采用 CC BY-SA 4.0协议,转载请注明出处!

 目录

致敬李文亮及各路英雄好汉!