Почему бесконечность = 0x3f3f3f3f?

В некоторых ситуациях обычно используется достаточно большое целочисленное значение для представления бесконечности. Обычно я использую наибольшее представимое положительное/отрицательное целое число. Это обычно дает больше кода, так как вам нужно проверить, является ли один из операндов бесконечным до практически всех арифметических операций, чтобы избежать переполнения. Иногда желательно иметь насыщенную целочисленную арифметику. По этой причине некоторые люди используют меньшие значения для бесконечности, которые можно добавлять или умножать несколько раз без переполнения. Меня интересует тот факт, что это чрезвычайно распространено (особенно в соревнованиях по программированию):

const int INF = 0x3f3f3f3f;

Почему этот номер особенный? Это двоичное представление:

00111111001111110011111100111111

Я не вижу здесь особого интересного свойства. Я вижу, что это легко ввести, но если это было причиной, почти все могло бы сделать (0x3e3e3e3e, 0x2f2f2f2f и т.д.). Он может быть добавлен один раз без переполнения, что позволяет:

a = min(INF, b + c);

Но тогда все остальные константы. Googling только показывает мне много фрагментов кода, которые используют эту константу, но никаких объяснений и комментариев.

Кто-нибудь может это заметить?

Ответ 1

Я нашел некоторые доказательства об этом здесь (исходный контент на китайском языке); основная идея заключается в том, что 0x7fffffff проблематичен, поскольку он уже "вершина" диапазона 4-байтных подписанных int; поэтому добавление чего-либо к нему приводит к отрицательным числам; 0x3f3f3f3f, вместо этого:

все еще довольно большой (тот же порядок величины 0x7fffffff);
имеет большой запас; если вы говорите, что допустимый диапазон целых чисел ограничен числами ниже него, вы можете добавить к нему любое "действительное положительное число" и все равно получить бесконечное (то есть что-то >=INF). Даже INF+INF не переполняется. Это позволяет всегда держать его под контролем:
```
a+=b;
if(a>INF)
    a=INF;
```
- это повторение равных байтов, что означает, что вы можете легко memset stuff на INF;
также, как заметил выше замечание Jörg W Mittag, он имеет приятное представление ASCII, которое позволяет как "летать" на лету, глядя на дампы памяти, так и записывать их непосредственно в память.

Ответ 2

0x3f3f3f3f - это представление ASCII строки ????.

Krugle находит 48 экземпляров этой константы во всей своей базе данных. 46 из этих экземпляров находятся в проекте Java, где он используется как битмаска для некоторых графических манипуляций.

1 project - это операционная система, где используется для представления неизвестного устройства ACPI.

1 проект снова является битовой маской для графики Java.

Таким образом, во всех проектах, индексированных Кругле, он используется 47 раз из-за его битпаттера, один раз из-за его интерпретации ASCII и не один раз как представление бесконечности.

Ответ 3

Я могу быть или не быть одним из первых первооткрывателей 0x3f3f3f3f. Я опубликовал румынскую статью об этом в 2004 году (http://www.infoarena.ro/12-ponturi-pentru-programatorii-cc # 9), но я использую это значение с 2002 года, по крайней мере, для соревнований по программированию.

Для этого есть две причины:

0x3f3f3f3f + 0x3f3f3f3f не переполняет int32. Для этого некоторые используют 100000000 (один миллиард).
можно установить массив из ints в бесконечность, выполнив memset(array, 0x3f, sizeof(array))