Типы и знаковость

Целочисленных типов в C++ больше, чем нужно, и половину можно смело забыть. Но у оставшихся есть свойства, из-за которых код ломается молча.

Что реально нужно

тип	диапазон	когда
int	$\pm 2.1 \cdot 10^9$	по умолчанию
long long	$\pm 9.2 \cdot 10^{18}$	когда int мал
char	$-128 \dots 127$	символы
bool	true / false	флаги
double	15–16 значащих цифр	вещественные
__int128	$\pm 1.7 \cdot 10^{38}$	промежуточные произведения

Про short и long можно забыть. Первый нужен в исчезающе редких случаях экономии памяти, второй вообще опасен: на Linux это 64 бита, на Windows — 32, и код, работавший локально, ломается на сервере.

Отдельно про char: он бывает signed char и unsigned char, и это три разных типа, причём знаковость обычного char зависит от платформы. Практическое следствие одно: если пишете a[c] для символа c, приводите явно — a[(unsigned char)c], иначе на символах кириллицы получите отрицательный индекс.

Беззнаковые типы

У unsigned тот же размер, но диапазон сдвинут: не $[-2^{31}, 2^{31})$, а $[0, 2^{32})$.

Ключевое свойство: при выходе за границу беззнаковое значение заворачивается по кругу, и это определённое поведение, а не ошибка. Ноль минус единица даёт $2^{32} - 1$.

unsigned x = 0;
cout << x + 1;   // 1
cout << x - 1;   // 4294967295

Само по себе это безобидно. Проблема в том, что беззнаковые типы попадают в код там, где их не ждут.

Главная ловушка: size()

vector::size() возвращает size_t — беззнаковый 64-битный тип. Отсюда:

vector<int> a;                        // пустой
for (int i = 0; i < a.size() - 1; i++)
    cout << a[i];

Ожидается, что цикл не выполнится ни разу. На самом деле a.size() - 1 равно 18446744073709551615, цикл идёт по всему адресному пространству, и программа падает.

Причём на непустом векторе всё работает — ошибка проявляется ровно на вырожденном тесте, которого нет в сэмплах.

Три способа не попасться:

for (int i = 0; i + 1 < a.size(); i++)        // перенесли единицу влево
for (int i = 0; i < (int)a.size() - 1; i++)   // привели к знаковому
for (size_t i = 0; i + 1 < a.size(); i++)     // работаем в size_t целиком

Первый вариант лучший: он не требует ни приведений, ни размышлений.

Тот же капкан в сравнении. if (i < a.size()) при отрицательном i даст истину: знаковое i приведётся к беззнаковому и станет огромным. Компилятор об этом предупреждает (-Wsign-compare), но предупреждения обычно тонут в выводе.

Приведение типов

Канонический C++ требует static_cast<int>(x). В олимпиадном коде повсеместно пишут (int)x — короче в два раза и делает то же самое для арифметических типов.

Разница проявляется на указателях и классах, где static_cast проверяет больше. В задачах этого не бывает, так что пишите как удобнее — но знайте, что в рабочем коде вам скажут писать длинную форму.

__int128

Расширение GCC: 128-битное целое, диапазон около $1.7 \cdot 10^{38}$.

Главное применение — промежуточное произведение. Умножить два числа около $10^{18}$ по модулю нельзя ни в long long, ни в unsigned long long:

long long mulmod(long long a, long long b, long long m) {
    return (__int128)a * b % m;
}

Два ограничения:

• ввод и вывод не работают. cin >> x и cout << x для __int128 не определены; печатать приходится вручную, по цифре;
• медленнее. Одна операция стоит примерно как две над long long. Писать весь код на __int128 — верный способ получить превышение времени.

void print(__int128 value) {
    if (value < 0) { cout << '-'; value = -value; }
    string digits;
    if (value == 0) digits = "0";
    while (value > 0) { digits += char('0' + int(value % 10)); value /= 10; }
    reverse(digits.begin(), digits.end());
    cout << digits;
}

Почему не сделать всё long long

Соблазн написать #define int long long и не думать понятен. Три причины не делать этого:

Память. Массив на $10^7$ элементов — 80 МБ вместо 40. При лимите 256 МБ это половина бюджета.

Скорость. В кэш помещается вдвое меньше данных. На задачах с большими массивами разница бывает двукратной.

Ломается остальное. #define int long long превращает main в long long main, из-за чего приходится писать signed main. Дальше начинают ломаться шаблоны, abs берёт не ту перегрузку, а %d в printf читает половину числа.

Разумно: int по умолчанию, long long там, где нужен диапазон. Подробнее о том, где именно арифметика ломается, — в статье про переполнение.