CODEWITHSUNDEEP
cinfinity
Gabriel
Gabriel

Reputation: 1833

Why is infinity = 0x3f3f3f3f?

In some situations, one generally uses a large enough integer value to represent infinity. I usually use the largest representable positive/negative integer. That usually yields more code, since you need to check if one of the operands is infinity before virtually all arithmetic operations in order to avoid overflows. Sometimes it would be desirable to have saturated integer arithmetic. For that reason, some people use smaller values for infinity, that can be added or multiplied several times without overflow. What intrigues me is the fact that it's extremely common to see (specially in programming competitions):

const int INF = 0x3f3f3f3f;

Why is that number special? It's binary representation is:

00111111001111110011111100111111

I don't see any specially interesting property here. I see it's easy to type, but if that was the reason, almost anything would do (0x3e3e3e3e, 0x2f2f2f2f, etc). It can be added once without overflow, which allows for:

a = min(INF, b + c);

But all the other constants would do, then. Googling only shows me a lot of code snippets that use that constant, but no explanations or comments.

Can anyone spot it?

Upvotes: 34

Views: 26268

Answers (3)

Alexandru
Alexandru

Reputation: 25810

I may or may not be one of the earliest discoverers of 0x3f3f3f3f. I published a Romanian article about it in 2004 (http://www.infoarena.ro/12-ponturi-pentru-programatorii-cc #9), but I've been using this value since 2002 at least for programming competitions.

There are two reasons for it:

  • 0x3f3f3f3f + 0x3f3f3f3f doesn't overflow int32. For this some use 100000000 (one billion).
  • one can set an array of ints to infinity by doing memset(array, 0x3f, sizeof(array))

Upvotes: 20

Matteo Italia
Matteo Italia

Reputation: 126787

I found some evidence about this here (original content in Chinese); the basic idea is that 0x7fffffff is problematic since it's already "the top" of the range of 4-byte signed ints; so, adding anything to it results in negative numbers; 0x3f3f3f3f, instead:

  • is still quite big (same order of magnitude of 0x7fffffff);

  • has a lot of headroom; if you say that the valid range of integers is limited to numbers below it, you can add any "valid positive number" to it and still get an infinite (i.e. something >=INF). Even INF+INF doesn't overflow. This allows to keep it always "under control":

    a+=b;
if(a>INF)
    a=INF;

  • is a repetition of equal bytes, which means you can easily memset stuff to INF;

  • also, as @Jörg W Mittag noticed above, it has a nice ASCII representation, that allows both to spot it on the fly looking at memory dumps, and to write it directly in memory.

Upvotes: 35

Jörg W Mittag
Jörg W Mittag

Reputation: 369458

0x3f3f3f3f is the ASCII representation of the string ????.

Krugle finds 48 instances of that constant in its entire database. 46 of those instances are in a Java project, where it is used as a bitmask for some graphics manipulation.

1 project is an operating system, where it is used to represent an unknown ACPI device.

1 project is again a bitmask for Java graphics.

So, in all of the projects indexed by Krugle, it is used 47 times because of its bitpattern, once because of its ASCII interpretation, and not a single time as a representation of infinity.

Upvotes: 12

Related Questions