Свод правил по работе с целыми числами в C-C++

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

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

Типы данных

Базовые целочисленные типы

Целочисленные типы устанавливаются с помощью допустимой последовательности ключевых слов, взятых из набора {char, short, int, long, signed, unsigned}.

Несмотря на то, что битовая ширина каждого базового целочисленного типа определяется реализацией (т.е. зависит от компилятора и платформы), стандартом закреплены следующие их свойства:

• char: минимум 8 бит в ширину;
• short: минимум 16 бит и при этом не меньше char;
• int: минимум 16 бит и при этом не меньше short;
• long: минимум 32 бит и при этом не меньше int;
• long long: минимум 64 бит и при этом не меньше long.

Наличие знака

• Стандартный сhar может иметь знак или быть беззнаковым, что зависит от реализации.
• Стандартные short, int, long и long long идут со знаком. Беззнаковыми их можно сделать, добавив ключевое слово unsigned.
• Числа со знаком можно кодировать в двоичном формате в виде дополнительного кода, обратного или как величину со знаком. Это определяется реализацией. Заметьте, что обратный код и величина со знаком имеют различные шаблоны битов для отрицательного нуля и положительного, в то время как дополнительный код имеет уникальный нуль.
• Символьные литералы (в одинарных кавычках) имеют тип (signed) intв C, но (signed или unsigned) char в C++.

Дополнительные правила

• sizeof(char) всегда равен 1, независимо от битовой ширины char.
• Битовая ширина не обязательно должна отличаться. Например, допустимо использовать char, short и int, каждый шириной в 32 бита.
• Битовая ширина должна быть кратна 2. Например, int может иметь ширину 36 бит.
• Есть разные способы написания целочисленного типа. К примеру, в каждой следующей строке перечислен набор синонимов:
  • int, signed, signed int, int signed;
  • short, short int, short signed, short signed int;
  • unsigned long long, long unsigned int long, int long long unsigned.

Типы из стандартных библиотек

• size_t [1] (определен в stddef.h) является беззнаковым и содержит не менее 16 бит. При этом не гарантируется, что его ширина будет как минимум равна int.
• ptrdiff_t [2] (определен в stddef.h) является целочисленным типом со знаком. Вычитание двух указателей будет давать этот тип. При этом не стоит ожидать, что вычитание двух указателей даст int.
• В stdint.h ^[3] определена конкретная ширина типов: uint8_t, int8_t, 16, 32 и 64. Будьте внимательны к операциям, подразумевающим продвижение типов. Например, uint8_t + uint8_t даст int (со знаком и шириной не менее 16 бит), а не uint8_t, как можно было предположить.

Преобразования

Представим, что значение исходного целочисленного типа нужно преобразовать в значение целевого целочисленного типа. Такая ситуация может возникнуть при явном приведении, неявном приведении в процессе присваивания или при продвижении типов.

Как происходит преобразование?

Главный принцип в том, что, если целевой тип может содержать значение исходного типа, то это значение семантически сохраняется.

Говоря конкретнее:

• Когда исходный тип расширяется до целевого типа с аналогичной знаковой характеристикой (например, signed char -> int или unsigned short -> unsigned long), каждое исходное значение после преобразования сохраняется.
• Даже если исходный и целевой типы имеют разные диапазоны, все значения в их пересекающейся части будут сохранены. Например, int, содержащий значение в диапазоне [0, 255], будет без потерь преобразован в unsigned char.

В более точной форме эти правила звучат так:

• При преобразовании в беззнаковый тип новое значение равняется старому значению по модулю 2^{целевая ширина в битах}. Объяснение:
  • Если исходный тип беззнаковый и шире целевого, тогда старшие биты отбрасываются.
  • Если исходный тип имеет знак, тогда в процессе преобразования берется исходное значение, и из него/к нему вычитается/прибавляется 2^{целевая ширина в битах} до тех пор, пока новое значение не впишется в диапазон целевого типа. Более того, если число со знаком представлено в дополнительном коде, то в процессе преобразования старшие биты отбрасываются, как и в случае с беззнаковыми числами.

• В случае преобразования в тип со знаком случаи могут быть такими:
  • Если исходное значение вписывается в диапазон целевого типа, тогда процесс преобразования (например, расширение знака) производит целевое значение, семантически равное исходному.
  • Если же оно не вписывается, тогда поведение будет определяться реализацией и может вызвать исключение (к примеру, прерывание из-за переполнения).

Арифметика

Продвижение/преобразование

• Унарный арифметический оператор применяется только к одному операнду. Примеры: -, ~.
• Бинарный оператор применяется к двум операндам. Примеры: +, *, &. <<.
• Если операнд имеет тип bool, char или short (как signed, так и unsigned), тогда он продвигается до int (signed), если int может содержать все значения исходного типа. В противном случае он продвигается до unsigned int. Процесс продвижения происходит без потерь. Примеры:
  • В реализации присутствуют 16-битный short и 24-битный int. Если переменные x и y имеют тип unsigned short, то операцияx & y продвигает оба операнда до signed int.
  • В реализации присутствуют 32-битный char и 32-битный int. Если переменные x и y имеют тип unsigned char, то операцияx – y продвигает оба операнда до unsigned int.

• В случае двоичных операторов оба операнда перед арифметической операцией неявно преобразуются в одинаковый общий тип. Ранги преобразования возрастают в следующем порядке: int, long, long long. Рангом общего типа считается старший ранг среди типов двух операндов. Если оба операнда являются signed/unsigned, то их общий тип будет иметь ту же характеристику. Если же операнд с беззнаковым типом имеет старший или равный ранг по отношению ко второму операнду, то их общий тип будет беззнаковым. В случае, когда тип операнда со знаком может представлять все значения другого типа операнда, общий тип будет иметь знак. В противном случае общий тип получается беззнаковым. Примеры:
  • (long) + (long) → (long);
  • (unsigned int) * (int) → (unsigned int);
  • (unsigned long) / (int) → (unsigned long);
  • если int является 32-битным, а long 64-битным: (unsigned int) % (long) → (long);
  • если int и long оба являются 32-битными: (unsigned int) % (long) → (unsigned long).

Неопределенное поведение

Знаковое переполнение:

• При выполнении арифметических операций над целочисленным типом переполнение считается неопределенным поведением (UB). Такое поведение может вызывать верные, несогласованные и/или неверные действия как сразу, так и в дальнейшем.
• При выполнении арифметики над беззнаковым целым (после продвижений и преобразований) любое переполнение гарантированно вызовет оборот значения. Например, UINT_MAX + 1 == 0.
• Выполнение арифметики над беззнаковыми целыми фиксированного размера может привести к едва уловимым ошибкам. Например:
  • Пусть uint16_t = unsigned short, и int равен 32-битам. Тогда uint16_t x=0xFFFF, y=0xFFFF, z=x*y; x и y будут продвинуты до int, и x * y приведет к переполнению int, вызвав неопределенное поведение.
  • Пусть uint32_t = unsigned char, и int равен 33-битам. Тогда uint32_t x=0xFFFFFFFF, y=0xFFFFFFFF, z=x+y; x и y будут продвинуты до int, и x + y приведет к переполнению int, то есть неопределенному поведению.
  • Чтобы обеспечить безопасную арифметику с беззнаковыми целыми, нужно либо прибавить 0U, либо умножить на 1U в качестве пустой операции. Например: 0U + x + y или 1U * x * y. Это гарантирует, что операнды будут продвинуты как минимум до ранга int и при этом останутся без знаков.

Деление/остаток:

• Деление на нуль и остаток с делителем нуля также относятся к неопределенному поведению.
• Беззнаковое деление/остаток не имею других особых случаев.
• Деление со знаком может вызывать переполнение, например INT_MIN / -1.
• Остаток со знаком при отрицательных операндах может вызывать сложности, так как некоторые части являются однообразными, в то время как другие определяются реализацией.

Битовые сдвиги:

• Неопределенным поведением считается битовый сдвиг (< < и >>)на размер, который либо отрицателен, либо равен или больше битовой ширины.
• Левый сдвиг беззнакового операнда (после продвижения/преобразования) считается определенным правильно и отклонений в поведении не вызывает.
• Левый сдвиг операнда со знаком, содержащего неотрицательное значение, в следствии которого 1 бит переходит в знаковый бит, является неопределенным поведением.
• Левый сдвиг отрицательного значения относится к неопределенному поведению.
• Правый сдвиг неотрицательного значения (в типе операнда без знака или со знаком) считается определенным правильно и отклонений в поведении не вызывает.
• Правый сдвиг отрицательного значения определяется реализацией.

Счетчик цикла

Выбор типа

Предположим, что у нас есть массив, в котором нужно обработать каждый элемент последовательно. Длина массива хранится в переменной len типа T0. Как нужно объявить переменную счетчика цикла i типа T1?

• Самым простым решением будет использовать тот же тип, что и у переменной длины. Например:

uint8_t len = (...);
for (uint8_t i = 0; i < len; i++) { ... }

• Говоря обобщенно, переменная счетчика типа T1 будет работать верно, если диапазон T1 будет являться (не строго) надмножетсвом диапазона T0. Например, если len имеет тип uint16_t, тогда отсчет с использованием signed long (не менее 32 бит) сработает.
• Говоря же более конкретно, счетчик цикла должен просто покрывать всю фактическую длину. Например, если len типа int гарантированно будет иметь значение в диапазоне [3,50] (обусловленное логикой приложения), тогда допустимо отсчитывать цикл, используя char без знака или со знаком (в котором однозначно можно представить диапазон [0,127]).
• Нежелательно использовать переменную длины и переменную счетчика с разной знаковостью. В этом случае сравнение вызовет неявное сложное преобразование, сопровождаемое характерными для платформы проблемами. К примеру, не стоит писать такой код:

size_t len = (...);  // Unsigned
for (int i = 0; i < len; i++) { ... }

Отсчет вниз

Для циклов, ведущих отсчет вниз, более естественным будет использовать счетчик со знаком, потому что тогда можно написать:

for (int i = len - 1; i >= 0; i--) {
    process(array[i]);
}

При этом для беззнакового счетчика код будет таким:

for (unsigned int i = len; i > 0; i--) {
    process(array[i - 1]);
}

Примечание: сравнение i >= 0 имеет смысл только, когда i является числом со знаком, но всегда будет давать true, если оно будет беззнаковым. Поэтому, когда это выражение встречается в беззнаковом контексте, значит, автор кода скорее всего допустил ошибку в логике.

Заблуждения

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

• char всегда равен 8 битам. int всегда равен 32 битам.
• sizeof(T) представляет число из 8-битных байтов (октетов), необходимых для хранения переменной типа T. (Это утверждение ложно, потому что если, скажем, char равняется 32 битам, тогда sizeof(T) измеряется в 32-битных словах).
• Можно использовать int в любой части программы и игнорировать более точные типы вроде size_t, uint32_t и т.д.
• Знаковое переполнение гарантированно вызовет оборот значения. (например, INT_MAX + 1 == INT_MIN).
• Символьные литералы равны их значениям в коде ASCII, например ‘A’ == 65. (Согласно EBCDIC это утверждение ложно).
• Преобразование указателя в int и обратно в указатель происходит без потерь.
• Преобразование {указателя на один целочисленный тип} в {указатель на другой целочисленный тип} безопасно. Например, int *p (…); long *q = (long*)p;. (см. каламбур типизации и строгий алиасинг).
• Когда все операнд(ы) арифметического оператора (унарного или бинарного) имеют беззнаковые типы, арифметическая операция выполняется в беззнаковом режиме, никогда не вызывая неопределенного поведения, и в результате получается беззнаковый тип. Например: предположим, что uint8_t x; uint8_t y; uint32_t z;, тогда операция x + y должна дать тип вроде uint8_t, беззнаковый int, или другой разумный вариант, а +z по-прежнему будет uint32_t. (Это не так, потому что при продвижении типов предпочтение отдается типам со знаком).

Моя критика

• Если вкратце, то знание и постоянное использование всех этих правил сильно нагружает мышление ^[4]. Допущение же ошибки в их применении приводит к риску написания неверного или непортируемого кода. При этом такие ошибки могут как всплыть сразу, так и таиться в течение дней или даже долгих лет.
• Сложности начинаются с битовой ширины базовых целочисленных типов, которая зависит от реализации. Например, int может иметь 16, 32, 64 бита или другое их количество. Всегда нужно выбирать тип с достаточным диапазоном. Но иногда использование слишком обширного типа (например, необычного 128-битного int) может вызвать сложности или даже внести уязвимости. Усугубляется это тем, что такие типы из стандартных библиотек, как size_t, не имеют связи с другими типами вроде беззнакового int или uint32_t; стандарт позволяет им быть шире или уже.
• Правила преобразования совершенно безумны. Что еще хуже, практически везде допускаются неявные преобразования, существенно затрудняющие аудит человеком. Беззнаковые типы достаточно просты, но знаковые имеют очень много допустимых реализаций (например, обратный код, создание исключений). Типы с меньшим рангом, чем int, продвигаются автоматически, вызывая труднопонимаемое поведение с диапазонами и переполнение. Когда операнды отличаются знаковостью и рангами, они преобразуются в общий тип способом, который зависит от определяемой реализацией битовой ширины. Например, выполнение арифметики над двумя операндами, как минимум один из которых имеет беззнаковый тип, приведет к преобразованию их обоих либо в знаковый, либо в беззнаковый тип в зависимости от реализации.
• Арифметические операции изобилуют неопределенным поведением: знаковое переполнение в add/sub/mul/div, деление на нуль, битовые сдвиги. Не сложно создать такие условия неопределенного поведения по случайности, но сложно вызвать их намеренно или обнаружить при выполнении, равно как выявить их причины. Необходима повышенная внимательность и усилия для проектирования и реализации арифметического кода, исключающего переполнение/UB. Стоит учитывать, что в последствии становится сложно отследить и исправить код, при написании которого не соблюдались принципы защиты от переполнения/UB.
• Присутствие signed и unsigned версии каждого целочисленного типа удваивает количество доступных вариантов. Это создает дополнительную умственную нагрузку, которая не особо оправдывается, так как типы со знаком способны выполнять практически все те же функции, что и беззнаковые.
• Ни в одном другом передовом языке программирования нет такого числа правил и подводных камней касательно целочисленных типов, как в С и C++. Например:
  • В Java целые числа ведут себя одинаково в любой среде. В этом языке определено конкретно 5 целочисленных типов (в отличие от C/C++, где их не менее 10). Они имеют фиксированную битовую ширину, практически все из них имеют знаки (кроме char), числа со знаком должны находится в дополнительном коде, неявные преобразования допускают только их варианты без потерь, а вся арифметика и преобразования определяются точно и не вызывают неоднозначного поведения. Целочисленные типы в Java поддерживают быстрое вычисление и эффективное упаковывание массивов в сравнении с языками вроде Python, где есть только bigint переменного размера.
  • Java в значительной степени опирается на 32-битный тип int, особенно для перебора массивов. Это означает, что этот язык не может эффективно работать на малопроизводительных 16-битных ЦПУ (часто используемых во встраиваемых микроконтроллерах), а также не может непосредственно работать с большими массивами в 64-битных системах. К сравнению, C/C++ позволяет писать код, эффективно работающий на 16, 32 и/или 64-битных ЦПУ, но при этом требует от программиста особой осторожности.
  • В Python есть всего один целочисленный тип, а именно signed bigint. В сравнении с C/C++ это сводит на нет все рассуждения на тему битовой ширины, знаковости и преобразований, так как во всем коде правит один тип. Тем не менее за это приходится платить низкой скоростью выполнения и несогласованным потреблением памяти.
  • В JavaScript вообще нет целочисленного типа. Вместо этого в нем все выражается через математику float64 (double в C/C++). Из-за этого битовая ширина и числовой диапазон оказываются фиксированными, числа всегда имеют знаки, преобразования отсутствуют, а переполнение считается нормальным.
  • Язык ассемблера для любой конкретной машинной архитектуры (x86, MIPS и т.д.) определяет набор целочисленных типов фиксированной ширины, арифметические операции и преобразования – с редкими случаями неопределенного поведения или вообще без них.

Дополнительная информация (англ.)

• Wikipedia: C data types ^[5]
• cppreference.com: C++ — Fundamental types ^[6]
• cppreference.com: C — Implicit conversions — Integer conversions ^[7]
• cppreference.com: C — Implicit conversions — Usual arithmetic conversions ^[8]
• C in a Nutshell: Chapter 4. Type Conversions ^[9]
• Stack Overflow: Implicit type promotion rules ^[10]
• Stack Overflow: 32 bit unsigned multiply on 64 bit causing undefined behavior? ^[11]
• Stack Overflow: What’s the best C++ way to multiply unsigned integers modularly safely? ^[12]
• Stack Overflow: Is masking before unsigned left shift in C/C++ too paranoid? ^[13]

^[14]

Автор: Дмитрий Брайт

Источник ^[15]