0x3f3f3f3f

在算法竞赛中，我们常常需要用到设置一个常量用来代表“无穷大”。

对于int类型的数，有人会采用INT_MAX，即 0x7fffffff （2^31-1）作为无穷大。

  • int占用4字节，1字节（byte） = 8位（bit），共占用32位（比特），数据范围为-2147483648~2147483647（-2^31~2^31-1）
    但是以INT_MAX为无穷大常常面临一个问题，即加一个其他的数会溢出。

而这种情况在动态规划，或者其他一些递推的算法中常常出现，很有可能导致算法出问题。

所以在算法竞赛中，我们常采用 0x3f3f3f3f 来作为无穷大。

0x3f3f3f3f 主要有如下好处：

  1. 0x3f3f3f3f 的十进制为1061109567，0x7fffffff的十进制为2147483647（2^31-1），和INT_MAX一个数量级，即10^9数量级，一般场合下的数据都是小于10^9的。

  2. 0x3f3f3f3f * 2 = 2122219134（比2147483647小一点），无穷大相加依然不会溢出。

Memset

  1. 原理
    memset作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。memset以一个字节（8位）为单位赋值，一个int型占32位，即有4个字节循环，所以使用memset一般只用来初始化特定数字，如0、-1、0x3f，其他的（如1）建议使用循环初始化。

  2. 0x3f
    memset(a, 0x3f, sizeof(a)); 用于初始化数组a为正无穷，0x3f转化为二进制是 1 1 1 1 1 1 （6位），补零到8位（一个字节）后是 0 0 1 1 1 1 1 1 ，经过四次赋值变为一个int型，
    即 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 ，即 0x3f3f3f3f ，以此将int数组的每个数赋值为无穷大。

由上例可发现，memset只能用来置特殊的数：

  • 0 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  • -1 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    （负数以补码形式储存，即其正数加符号位0，取反，+1）
  • 0x3f3f3f3f = 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1

这些数即每四个字节都相同的数，其他的要使用循环来置数。