Why Programmers Like to Set Infinity to 0x3f3f3f3f
It's common to set an constant variable representing infinity. For example, to find the minimum number among a list, it's necessary to set an a
having the maximum value and change its value later.
Obviously, computers have no fixed way representing the concept "Infinity". So we can only set a constant to express "the maximum".
For int
, naturally we bring 0x7f ff ff ff
to mind, since it's the maximum value of a 32-bit int
(0x7f ff ff ff = 2^31 - 1 = 2147483647
).
Mostly it's proved to be practical. In many cases, such as picking the minimum number as described above, it is a good choice of infinity. But, when some problems related to arithmetic calculation, say relaxation operation in finding shortest paths:
def relax(u, v, w):
if (d[u] + w[u][v] < d[v]):
d[v] = d[u] + w[u][v]
data overflow may happen when using 0x7f ff ff ff
as infinity. Because the first bit of an int
is used to express its sign.
So, to avoid that hidden danger, 0x3f 3f 3f 3f
can be chosen to represent infinity. There're two advantages: firstly, 0x3f 3f 3f 3f = 1061109567
which is the same order of magnitude as 0x7f ff ff ff
. Even though, twice of 0x3f 3f 3f 3f
is within the range of int
.
Secondly, it's widely accepted that memset
is the quickest way initializing an array in C language. The second parameter value
of memset
is of 8-bit:
value
: Value to be set. Thevalue
is passed as anint
, but the function fills the block of memory using theunsigned char
conversion of this value.
That's to say, memset
fills an array using an 8-bit value. Surprisingly, all the four eight bits of 0x3f 3f 3f 3f
are same. So, it's safe to use memset
and 0x3f 3f 3f 3f
to maximize an array, which improves effiency.