在算法竞赛中,我们常常需要用到设置一个常量用来代表“无穷大”。
一般会有两个选择:0x7fffffff和0x3f3f3f3f
比如对于int类型的数,有的人会采用INT_MAX,即0x7fffffff作为无穷大。但是以INT_MAX为无穷大常常面临一个问题,即加一个其他的数会溢出。
而这种情况在动态规划,或者其他一些递推的算法中常常出现,很有可能导致算法出问题。
下面来看看到底如何进行选择
0x7fffffff
首先了解数字的含义,"0x"是一个前缀,表示十六进制。
而"7"在二进制中是7的二进制码为 0111,f是指1111。
这样, 0x7FFFFFFF 的二进制表示就是除了符号位是 0表示正数,其余都是1。
对于int而言,0x7fffffff是最大的数值。
所以可以把需要比较的无穷大设为0x7fffffff再进行比较。
0x3f3f3f3f
0x3f3f3f3f的十进制为1061109567,和INT_MAX一个数量级,即10^9数量级,
而一般场合下的数据都是小于10^9的。
0x3f3f3f3f的数值为1061109567,它的两倍也只有2122219134,不会溢出。
这样就有一个好处,当两个无穷大相加的时候可以使int型整数不溢出,并使数值仍为无穷大。
而使用0x3f3f3f3f在对于数组初始化的时候也比较方便,一般数组批量赋值时会使用memset函数,如果想将一个数组全部定义为"无穷大"的0x3f3f3f3f,因为memset函数是对字节进行操作,而0x3f3f3f3f的每个字节都是0x3f,所以可以直接定义为memset(array, 0x3f, sizeof(array))
在java中使用Arrays.fill(arr,0x3f3f3f3f);