关闭

【算法设计与数据结构】为何程序员喜欢将INF设置为0x3f3f3f3f?

标签: 算法INF0x3f3f3f3f
4616人阅读 评论(3) 收藏 举报
分类:

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

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

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

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

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

准确来说,0x7fffffff不能满足“无穷大加一个有穷的数依然是无穷大”这个条件,它会变成了一个很小的负数。

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

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

0x3f3f3f3f的十进制是1061109567,是10^9级别的(和0x7fffffff一个数量级),而一般场合下的数据都是小于10^9的,所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。
另一方面,由于一般的数据都不会大于10^9,所以当我们把无穷大加上一个数据时,它并不会溢出(这就满足了“无穷大加一个有穷的数依然是无穷大”),事实上0x3f3f3f3f+0x3f3f3f3f=2122219134,这非常大但却没有超过32-bit int的表示范围,所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。

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

所以在通常的场合下,0x3f3f3f3f真的是一个非常棒的选择!

20
0
查看评论
发表评论
* 以上用户言论只代表其个人钱柜娱乐开户,不代表CSDN网站的钱柜娱乐开户或立场

关于0x3f3f3f3f(0x四个3f)

在之前一道最小生成树问题中遇到过,一般我啊以前的习惯
  • tcherry
  • tcherry
  • 2014-07-09 20:19
  • 886

编程中无穷大的设定

编程中无穷大的设定 很多人可能设为0x7fffffff,这个数的确是32-bit int的最大值,符号位为0,其他的都是1 但在很多情况下,0x7fffffff会出现错误,比如溢出,这样两个无穷大...
  • mylovestart
  • mylovestart
  • 2012-11-29 12:38
  • 2983

为何将INF设置为0x3f3f3f3f

转自/jiange_zh 在算法竞赛中,我们常常需要用到一个“无穷大”的值,对于我来说,大多数时间我会根据具体问题取一个99999999之类的数(显得很不...
  • sduthao
  • sduthao
  • 2017-07-27 20:47
  • 106

【转载】为何程序员喜欢将INF设置为0x3f3f3f3f?

在算法竞赛中,我们常常需要用到一个“无穷大”的值,对于我来说,大多数时间我会根据具体问题取一个99999999之类的数(显得很不专业啊!) 在网上看别人代码的时候,经常会看到他们把INF设为0x...
  • feiyu_diary
  • feiyu_diary
  • 2017-12-14 14:05
  • 6

【算法设计与数据结构】为何程序员喜欢将INF设置为0x3f3f3f3f?

出处/jiange_zh 在算法竞赛中,我们常常需要用到一个“无穷大”的值,对于我来说,大多数时间我会根据具体问题取一个99999999之类的数(显得很不专业啊...
  • feng_zhiyu
  • feng_zhiyu
  • 2017-07-20 15:15
  • 164

【算法设计与数据结构】为何程序员喜欢将INF设置为0x3f3f3f3f?

在算法竞赛中,我们常常需要用到一个“无穷大”的值,对于我来说,大多数时间我会根据具体问题取一个99999999之类的数(显得很不专业啊!) 在网上看别人代码的时候,经常会看到他们把INF设为0x...
  • huanghanqian
  • huanghanqian
  • 6天前 14:24
  • 19

为什么把无穷大INF设置成0x3f3f3f3f?

INF为什么设置成为0x3f3f3f3f
  • qq_34131212
  • qq_34131212
  • 2017-02-16 23:14
  • 515

使用0x3f3f3f表示无穷大

如果问题中各数据的范围明确,那么无穷大的设定不是问题,在不明确的情况下,很多程序员都取0x7fffffff作为无穷大,因为这是32-bit int的最大值。如果这个无穷大只用于一般的比较(比如求最小值...
  • L_apple8
  • L_apple8
  • 2016-09-13 14:40
  • 1097

【算法设计与数据结构】为何程序员喜欢将INF设置为0x3f3f3f3f?

在算法竞赛中,我们常常需要用到一个“无穷大”的值,对于我来说,大多数时间我会根据具体问题取一个99999999之类的数(显得很不专业啊!) 在网上看别人代码的时候,经常会看到他们把INF设为0x...
  • syz201558503103
  • syz201558503103
  • 2017-07-28 16:55
  • 68

【算法设计与数据结构】为何程序员喜欢将INF设置为0x3f3f3f3f?

出处:/jiange_zh/article/details/50198097 在算法竞赛中,我们常常需要用到一个“无穷大”的值,对于我来说,大多数时间我会...
  • major_zhang
  • major_zhang
  • 2017-04-14 18:04
  • 366
    个人资料
    • 访问:384239次
    • 积分:6583
    • 等级:
    • 排名:第4240名
    • 原创:272篇
    • 转载:16篇
    • 译文:0篇
    • 评论:153条
    Personal Information

    中山大学 计算机科学与技术

    腾讯科技 后台开发工程师

    e-mail:jiangezh@qq.com

    GitHub:https://github.com/jiangeZh

    钱柜娱乐开户
    最新评论