/ Programming

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. The value is passed as an int, but the function fills the block of memory using the unsigned 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.

Reference

http://www.kawabangga.com/posts/1153