Как определить остаток деления двоичных чисел

Деление чисел

Рассмотрим алгоритмы операции деления целых положительных двоичных чисел на , где А – 2п-разрядное делимое; В – и-разрядный делитель; . Полагаем, что частное является целым от-разрядным числом , при этом

Алгоритм деления с восстановлением остатка. Значения разрядов частногоопределяются в результате анализа остатков, полученных после вычитания делителя В на первом шаге алгоритма из старших разрядов делимого Дст, а на последующих шагах – из старших разрядов текущего остатка.

При положительном и пулевом значениях остатка разряд частного ck = 1. В этом случае для получения следующего остатка текущий остаток сдвигается на один разряд влево и из него вычитается делитель В.

При отрицательном значении остатка текущий разряд частного ck = 0. Возникает тупиковая ситуация. Для выхода из нее восстанавливается предыдущий остаток путем прибавления делителя В к отрицательному остатку. Восстановленный остаток сдвигается на один разряд влево и из него вычитается делитель В. Операции восстановления и сдвига позволяют увеличить предыдущий остаток в два раза и продолжить операцию деления.

Пример 2.30. Проиллюстрируем алгоритм с восстановлением остатка для случая п = 3, когда делимое А = 100011 (35|0), делитель В = 111 (710). Для вычитания делителя В воспользуемся операцией алгебраического сложения в дополнительном коде. Отрицательное значение делителя в дополнительном коде (

В) = 1001. Для выполнения операции деления введем дополнительные знаковые разряды, которые выделим жирным шрифтом. Последовательность действий при делении представлена ниже, на рис. 2.17.

Рис. 2.17. Алгоритм деления двоичных чисел с восстановлением остатка

Пример 2.31. При делении используются операции сложения и сдвига.

В результате деления получено частное С=0101, которое, по сути дела, представляет собой совокупность переносов, возникающих в результате операций сложения.

Алгоритм деления без восстановления остатка. При аппаратной реализации деления двоичных чисел операция сложения реализуется в сумматоре, а сдвига – в регистре. Регистр обладает способностью хранить предыдущий остаток во время выполнения операции суммирования. Поэтому восстановление остатка является необязательной операцией. При отрицательном значении текущего остатка необходимо воспользоваться хранящимся в регистре предыдущим остатком и произвести его сдвиг влево на один разряд.

Пример 2.32. Алгоритм без восстановления остатка для тех же значений делителя и делимого аналогичен приведенному примеру 2.29 (рис. 2.18).

Рис. 2.18. Алгоритм деления двоичных чисел без восстановления остатка

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

4.3. Деление двоичных чисел

4.3.1. Деление двоичных чисел, представленных в форме с фиксированной запятой.

Деление двоичных чисел во многом аналогично делению десятичных чисел.

В универсальных вычислительных машинах, как правило, реализуется «школьный» алгоритм деления чисел. «Школьный» алгоритм деления заключается в том, что делитель на каждом шаге вычитается из делимого столько раз (начиная со старших разрядов), сколько это возможно для получения наименьшего положительного остатка. Тогда в очередной разряд частного записывается цифра, равная числу делителей, содержащихся в делимом на данном шаге. Иначе говоря, при делении операцию вычитания повторяют до тех пор, пока уменьшаемое не станет меньше вычитаемого. Число этих повторений показывает, сколько раз вычитаемое укладывается в уменьшаемом.

разделим число 35 на 7 :

1) 35 — 7 = 28, 2) 28 — 7 = 21, 3) 21 — 7 = 14, 4) 14 — 7 = 7, 5) 7 — 7 = 0.

Ответ равен 5, т.к. процедура вычитания была повторена 5 раз.

Рассмотрим еще один пример:

разделим 204(10) на 12(10), т.е. 11001100(2):1100(2):

делимое 11001100 | 1100 — делитель

делитель 1100 | 10001

Двоичное, как и десятичное деление, начинается с анализа делимого (11001100) и делителя (1100). Сразу же обнаруживается, что делитель укладывается в 1100, а поэтому записывается 1 в старший разряд поля частного. Умножается делитель на 1 и вычитается из 1100, разность равна 0. Объединяется 0 остатка со значением следующего разряда делимого, равным 1. Поскольку делитель (1100) 0 раз укладывается в 1, записываем 0 в следующий по старшинству разряд поля частного, а число 1 объединяется со следующим разрядом делимого и т.д. до тех пор, пока делимое не оказывается исчерпанным.

Конечно компьютер не может строить догадок относительно того, сколько раз делитель укладывается в том или ином числе, поэтому весь процесс деления сводится к операциям вычитания и сдвига. Продемонстрируем на том же примере, но сначала делитель (1100) представим в дополнительном коде, что позволит ограничиться сложением во всех случаях, когда нужно выполнять сложение или вычитание: 1100пр = 1. 0100д. Частное формируется в некотором регистре С, незаполненные разряды которого будем обозначать через Х.

Начинаем вычитать делитель из делимого. Если остаток получается положительным, то в разряд частного записывается 1, в противном случае — 0.

0. 11001100 делимое 204

+ 1. 01000000 делитель 12

0. 00001100 первый остаток

Первый (старший) бит частного равен 1, т.к. остаток получился положительным: С = 1ХХХХ. Далее сдвигается первый остаток на один разряд влево и из него вычитывается делитель:

1. 01011000 второй остаток

Остаток отрицательный, поэтому в следующий разряд частного записывается 0, С = 10ХХХ. Кроме того необходимо биты делителя вернуть обратно первому остатку, т.е. сложить делитель (в прямом коде) и второй остаток:

0. 00011000 сдвинутый первый остаток.

Далее еще раз сдвигается сдвинутый первый остаток на один разряд влево и вычитается из него делитель:

1. 01110000 третий остаток

Третий остаток отрицательный, значит следующий (третий) разряд частного равен 0, С = 100ХХ. Поэтому возвращаем делитель третьему остатку,

0. 00110000 дважды сдвинутый первый остаток

Сдвигаем дважды сдвинутый первый остаток на один разряд влево и вычитаем делитель:

1. 10100000 четвертый остаток

Четвертый остаток опять отрицательный, поэтому С = 1000Х. Прибавляем делитель к четвертому остатку, результат сдвигаем на один разряд влево, а затем вновь вычитаем делитель:

0. 1100000 первый остаток после четвертого сдвига

0. 0000000 пятый остаток

Остаток положительный, значит С = 10001 = 17(10) — это и есть ответ.

Такой метод деления называется делением с восстановлением остатка.

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

Перед выполнением самой процедуры деления чисел в формате с фиксированной запятой определяется и запоминается знак частного. Далее оба операнда представляются в прямом коде, а делитель еще и в дополнительном для того, чтобы вычитание делителя заменить сложением, и выполняется сама процедура деления по описанному выше методу с обязательным контролем переполнения разрядной сетки. Если знак частного отрицательный, то ответ, при необходимости, представляется в дополнительном коде.

Например: разделим 35 на 5. 3510 = 0.1000112, 510 = 1012, 5д = 1.011д

(в регистре С, как и в предыдущем примере, формируется частное):

1.111011 С = 0 восстанавливаем остаток до делимого.

0.100011 сдвигаем влево остаток.

0.01111 С = 01, сдвигаем влево остаток.

0.0101 С = 011, сдвигаем остаток.

0.000 С = 0111 = 710

Вычитание делимого продолжают столько раз, сколько разрядов отведено для частного.

Метод деления без восстановления остатка. Как уже отмечалось, основой выполнения деления является операция вычитания с целью получения остатка, знак которого определяет цифру частного. Алгоритм выполнения деления имеет следующий вид:

где a0 — это остаток. Если а0 0, то С = 1, если а0 < 0, то С = 0. Для определения следующей цифры частного необходимо выполнить следующие действия: при а0 0 надо 2а0 — Y = a1, а при а0 < 0 надо 2а0 + Y = a1. Как видно в данном случае знак остатка определяет не только очередную цифру частного, но и характер следующей процедуры: прибавления делителя к сдвинутому остатку, если этот остаток меньше 0, и вычитание делителя из сдвинутого остатка, если остаток больше или равен 0. Этот метод деления получил название деления без восстановления остатка.

Как определить остаток деления двоичных чисел

Рассмотрим алгоритмы операции деления целых положительных двоичных чисел на , где А – 2п-разрядное делимое; В – и-разрядный делитель; . Полагаем, что частное является целым от-разрядным числом , при этом

Алгоритм деления с восстановлением остатка. Значения разрядов частногоопределяются в результате анализа остатков, полученных после вычитания делителя В на первом шаге алгоритма из старших разрядов делимого Дст, а на последующих шагах – из старших разрядов текущего остатка.

Системы счисления

Система счисления — способ записи чисел с помощью символов (называемых цифрами).

Привычная для людей система счисления — позиционная десятичная. Слово десятичная означает, что используются десять различных цифр. Слово позиционная означает, что положение цифры в записи числа имеет важное значение. Позиции цифр называются разрядами и нумеруются в обычной записи справа налево.

Например, число 9512 состоит из четырех разрядов.

Число 9512 в позиционной десятичной системе

цифра	разряд	название разряда
9	3	тысячи
5	2	сотни
1	1	десятки
2	0	единицы

Разряды удобно нумеровать, начиная не с единицы, а с нуля, что видно по следующей общей формуле, связывающей собственно число с его записью в позиционной системе счисления (ц — некоторая цифра, val(ц) — числовое значение цифры):

Разряд с номером 0 (самый левый) называют младшим least significant . Напротив, самый правый разряд называют старшим most significant .

Число r — основание системы счисления radix . В традиционной десятичной системе r = 10.

При помощи n разрядов можно записать r n разных целых чисел (от 0 до (r n – 1) включительно). Запись в позиционной системе легко обобщается на дроби: достаточно поставить разделитель целой и дробной частей (запятую или точку), указывающий нулевой разряд, и можно дописывать справа от него разряды, соответствующие отрицательным степеням основания.

Результат деления с остатком на степень основания r i можно выписать, просто “разрезав” запись числа по разряду i:

Таким образом, частное записывается цифрами в разрядах (n–1) … i, а остаток — цифрами в разрядах (i–1) … 0.

Это свойство позволяет формализовать алгоритм выписывания произвольного числа x в заданной системе счисления. Имеем рекуррентное соотношение:

Взяв остаток от деления x на r, получим цифру в младшем разряде. Далее, положим x равным частному деления x на r. Будем повторять эти операции, пока не получим 0 в качестве частного, выписывая остатки в соответствующие разряды записываемого числа.

В качестве примера, переведем 125 из десятичной в двоичную систему: 125 = 62·2 + 1, 62 = 31·2 + 0, 31 = 15·2 + 1, 15 = 7·2 + 1, 7 = 3·2 + 1, 3 = 1·2 + 1, 1 = 0·2 + 1 (получаемые остатки выписываем справа налево).

Откуда заключаем, что 125₁₀ = 1111101₂.

Для записи натурального числа x в системе счисления с основанием r достаточно (⌊log_r x⌋ + 1) разрядов. Соответственно при переводе n-разрядного числа из системы с основанием r в систему с основанием p получаем около n log_p r разрядов. Например, при переводе из десятичной в двоичную систему количество разрядов возрастает в log₂ 10 ≈ 3 раз. Действительно, 2 10 = 1024 ≈ 10 3 .

Арифметические операции, непосредственно поддерживаемые C++

Операция	C++
сложение	+
вычитание	—
умножение	*
деление	/
взятие остатка	%

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

Деление на нуль или взятие остатка от деления на нуль приводит к неопределённому поведению. Более экзотическая ситуация, в которой также возникает неопределённое поведение — невозможность представить результат деления. В частности, это возможно при делении (или взятие остатка от деления) на –1 наименьшего представимого целого при использовании дополнительного кода (см. далее).

В C++11 и выше для целых a и b частное a / b округляется в сторону нуля (т. е. дробная часть отбрасывается). Остаток от деление определяется исходя из тождества

(a / b) * b + a % b == a

Таким образом, знак остатка совпадает со знаком делимого.

Двоичная система счисления

Простейшая позиционная система счисления соответствует r = 2 — “двоичная система счисления”. В двоичной системе счисления всего две цифры: 0 и 1.

Двоичный разряд называется бит (от англ. binary digit, кроме того, по-английски bit букв. “кусочек”).

Благодаря своей минимальности двоичная система проще остальных реализуется “в железе”. Так, если заряд ячейки памяти больше порогового уровня Q₁, считаем, что она хранит 1, если же заряд меньше порогового уровня Q₀, считаем, что она хранит 0. Таким образом, ячейка памяти, способная находиться в двух различимых состояниях, может хранить один бит. Две таких ячейки могут хранить два бита и суммарно находиться в 2 2 = 4 разных состояниях (комбинации 00, 01, 10 и 11).

Или наоборот, если ячейка может находиться в четырёх различимых состояниях, например, хранить четыре различимых уровня заряда, то можно считать, что она хранит два бита, нужно лишь назначить разным уровням заряда условные значения 00, 01, 10 и 11.

Подобная ячейка памяти используется в MLC Flash-памяти. А в TLC flash-памяти ячейка может хранить уже восемь различимых уровней заряда или три бита (000, 001, 010, 011, 100, 101, 110 и 111). Чем больше уровней — тем больше данных можно уместить в единице объёма, но и вероятность ошибок возрастает, так как различные уровни заряда находятся тем ближе друг ко другу, чем их больше.

Двоичные числа легко складывать “столбиком”, учитывая перенос. Нетрудно выполнить и умножение “столбиком”: сдвинутые влево копии левого сомножителя умножаются на соответствующий разряд правого сомножителя и складываются.

Пример двоичного умножения

10011·1101	×
10011	1
100110	0
1001100	1
10011000	1
11110111	=

Под сдвигом влево на n разрядов понимается дописывание справа от числа n нулей. Если разрядная сетка ограничена, то старшие разряды могут отбрасываться.

Что касается деления с остатком, то оно выполняется “наоборот”: надо вычитать из делимого максимально сдвинутый влево делитель, пока это возможно. Например, ниже получено, что 1110110 = 1101·1001 + 1.

Пример двоичного деления с остатком

1110110	1001
1001000	1000
100100	100
10010	0
1001	1
= 1	1101

Шестнадцатеричная система счисления

Исторически сложилось так, что минимальная отдельно адресуемая ячейка компьютерной памяти (называемая байтом), как правило, состоит из 8 бит. Две четырёхбитные половинки байта называют тетрадами nibble, nybble . Тетрада может хранить 2 4 = 16 разных значений, поэтому её значение удобно записывать одной шестнадцатеричной цифрой hexadecimal digit . Традиционно в качестве шестнадцатеричных цифр используются десять арабских цифр и латинские буквы A, B, C, D, E и F для недостающих цифр со значениями 10, 11, 12, 13, 14 и 15 соответственно. В свою очередь, байт может принимать 2 8 = 256 = 16 2 разных значений. Значение байта можно записать двумя шестнадцатеричными цифрами.

Для перевода из двоичной в шестнадцатеричную систему и обратно удобно пользоваться следующей таблицей (одной шестнадцатеричной цифре соответствует четыре двоичных цифры).

Перевод между системами

Биты	Цифра	Значение
0000	0	0
0001	1	1
0010	2	2
0011	3	3
0100	4	4
0101	5	5
0110	6	6
0111	7	7
1000	8	8
1001	9	9
1010	A	10
1011	B	11
1100	C	12
1101	D	13
1110	E	14
1111	F	15

Числовые литералы C++

Литерал — непосредственно выписанное в программе значение. Например, 3.1415926 — литерал, а имя константы PI — не литерал, а идентификатор.

В C++ по умолчанию числовые литералы трактуются как записанные в десятичной системе счисления. Однако доступны ещё три системы, принадлежность к которым указывается префиксом.

Префиксы литералов

Префикс	Основание	Пример	В десятичной
нет	10	1921	1921
0b , 0B	2	0b1011	11
0	8	0377	255
0x , 0X	16	0xDEAD	57005

Поддержка префикса 0b введена в C++14, поэтому некоторые компиляторы могут его не поддерживать. Также в C++14 введена поддержка разделителя ’ (например 1’000 ), предназначенного для удобства чтения.

Суффиксы литералов позволяют задать тип константы

Тип	Бит*	Суффикс	Пример
int	32	нет	0x100
unsigned int	32	u , U	2’000u
long int	32	l , L	1l
unsigned long int	32	ul , UL	0UL
long long	64	ll , LL	64ll
unsigned long long	64	ull , ULL	10’000’000’000ull

*Ширина в битах указана для 32-битной версии платформы x86.

Кодирование отрицательных чисел

Для представления чисел компьютер применяет фиксированные наборы двоичных разрядов (бит). Способ представления некоторого множества чисел таким набором называют кодированием или кодом. Для неотрицательных целых чисел придумать такой код не составляет труда — надо просто выписать представление в двоичной системе счисления. Например, один байт (8 двоичных разрядов) способен хранить двоичные коды от 00000000 до 11111111.

Кодирование положительных чисел

Код	Число
00000000	0
00000001	1
00000010	2
00000011	3
00000100	4
…	…
01111111	127
10000000	128
10000001	129
10000010	130
…	…
11111110	254
11111111	255

Однако не так очевидно, как следует поступить с отрицательными целыми числами (дроби здесь рассматривать не будем — это отдельная большая тема). Для кодирования целых чисел с диапазоном, включающим отрицательные числа, были придуманы различные способы. Стандарты C и C++ не регламентируют, какой способ должна использовать реализация (как правило, используется тот способ, который целевой процессор поддерживает аппаратно), поэтому беззнаковые типы unsigned могут использоваться как фиксированные группы бит, а использование знаковых типов signed (включая наиболее популярный int , к которому относятся “обычным образом записанные” числовые значения вроде 101 или 16383) в таком качестве во многих случаях приводит к “неопределённому поведению”.

Ниже даны описания четырёх широко известных способов.

Прямой код

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

8-битный прямой код

Код	Число
00000000	0
00000001	1
00000010	2
…	…
01111110	126
01111111	127
10000000	–0
10000001	–1
10000010	–2
…	…
11111110	–126
11111111	–127

Недостатки: наличие двух нулей, увеличение числа на единицу как беззнакового может как добавить единицу, так и вычесть единицу.

Преимущество: симметричные диапазоны отрицательных и положительных чисел.

Обратный код

Обратный код представляет отрицательные числа в виде инверсии (каждый ноль заменяется единицей, а каждая единица — нулём) положительных аналогов.

8-битный обратный код

Код	Число
00000000	0
00000001	1
00000010	2
…	…
01111110	126
01111111	127
10000000	–127
10000001	–126
10000010	–125
…	…
11111110	–1
11111111	–0

Недостатки: наличие двух нулей, проверка на чётность требует проверки знака.

Преимущества: симметричные диапазоны отрицательных и положительных чисел; немного проще выполнить сложение по сравнению с прямым кодом — можно просто складывать коды, добавляя “знак” (значение старшего бита — ноль или один). Например: 100 + (–44) = 01100100₂ + (–00101100₂) = 01100100₂ + 11010011₂ + 1 = (1)00111000₂ = 56.

Сдвинутый код

Сдвинутый (или смещённый) код предполагает выбор некоторой константы b (сдвиг bias ), на которую сдвигается (путём вычитания) представление числа, взятое как беззнаковое целое. Обычно b выбирается равным половине диапазона (127 для 8-битного кода).

8-битный сдвинутый код

Код	Число
00000000	–127
00000001	–126
00000010	–125
00000011	–124
…	…
01111111	0
10000000	1
10000001	2
10000010	3
…	…
11111110	127
11111111	128

Сдвинутый код используется в особых случаях, например, для кодирования показателя в формате чисел с плавающей точкой по стандарту IEEE-754.

Дополнительный код

Дополнительный код получается из обратного кода добавлением единицы к инверсии (т.е. “знак” добавляется не в сумматоре, а заранее — к самому представлению), что позволяет складывать и вычитать числа как их беззнаковые представления.

8-битный дополнительный код

Код	Число
00000000	0
00000001	1
00000010	2
…	…
01111110	126
01111111	127
10000000	–128
10000001	–127
10000010	–126
…	…
11111110	–2
11111111	–1

Недостатки: несимметричность диапазонов отрицательных и положительных чисел; если сменить знак у наименьшего числа, получится оно же. В 8-битном случае: –(–128) = –10000000₂ = 01111111₂ + 1 = 10000000₂ = –128.

Преимущества: нет двух нулей, диапазон используется “полностью”; наиболее удобный для аппаратной реализации.

В настоящее время дополнительный код используется почти повсеместно.

Целочисленные типы C++

Встроенные

Некоторые правила, обязательные для всех реализаций:

• Ключевые слова int и signed подразумеваются по умолчанию (кроме случая с char), поэтому часто опускаются ( signed short int — то же, что short ).
• Минимум беззнаковых типов всегда равен нулю.
• Размер типа char равен 1 (отождествляется с “байтом”), размеры остальных типов кратны размеру char (получить в программе размер типа можно с помощью оператора sizeof ).
• Представление char имеет размер не менее 8 бит (в заголовочном файле climits определён макрос CHAR_BIT , равный количеству бит в char).
• Размеры signed и unsigned аналогов равны.
• Размер int не может быть меньше размера short и больше размера long.
• Размер long строго больше размера short.
• Типы signed char и unsigned char имеют размер 1, но считаются отдельными от char типами, при этом диапазон значений char совпадает либо с диапазоном signed char, либо с диапазоном unsigned char (задаётся конкретной реализацией языка).
• При смешивании значений знаковых и беззнаковых типов одного размера значения знаковых типов автоматически приводятся к беззнаковым, что иногда приводит не к тому результату, которого ожидал программист. Желательно избегать смешивания разных типов в одном выражении и использовать явное приведение типов, если есть сомнения по поводу результирующего типа подвыражения.

Правила приведения целочисленных типов:

• Значение одного целочисленного типа может быть конвертировано в значение другого целочисленного типа (произвольного). При этом не гарантируется его “сохранность”.
• При приведении целочисленного значения разрядности m к беззнаковому типу разрядности n: а) в случае n ≤ m вычисляется значение mod 2 m , для беззнаковых и знаковых в дополнительном коде это означает, что старшие (m–n) бит отбрасываются, младшие n бит интерпретируются как беззнаковое целое; б) в случае n > m старшие (n–m) бит заполняются нулями, если исходное число было беззнакового типа; если же исходное число было знакового типа, то сначала производится приведение к знаковому типу разрядности n, затем результат интерпретируется как беззнаковое целое (сохраняя двоичное представление).
• При приведении целочисленного значения к знаковому типу, исходное значение сохраняется (с возможным перекодированием), если попадает в диапазон целевого знакового типа, в противном случае результат приведения определяется реализацией.

Минимумы и максимумы, задающие минимальные гарантированные диапазоны целочисленных типов, выписаны по приложению E из стандарта ISO C99 (стандарт ISO C++ не задаёт конкретных величин).

Встроенные целочисленные типы C

Тип	Минимум	Максимум	Пример: x86-32
signed char	–127	127	1 байт, 8 бит, [–128, 127]
unsigned char	0	255	1 байт, [0, 255]
signed short int	–32767	32767	2 байта, [–32768, 32767]
unsigned short int	0	65535	2 байта, [0, 65535]
signed int	–32767	32767	4 байта, [–2147483648, 2147483647]
unsigned int	0	65535	4 байта, [0, 4294967295]
signed long int	–2147483647	2147483647	4 байта, [–2147483648, 2147483647]
unsigned long int	0	4294967295	4 байта, [0, 4294967295]
signed long long int	–9223372036854775807	9223372036854775807	8 байт, [–9223372036854775808, 9223372036854775807]
unsigned long long int	0	18446744073709551615	8 байт, [0, 18446744073709551615]

На практике минимум для знаковых типов обычно меньше на единицу, чем приведённые выше значения (например, –128 вместо –127) благодаря использованию дополнительного кода.

Заголовочный файл climits

Данный заголовочный файл позволяет узнать некоторые характеристики базовых типов данной реализации.

Макросы из climits/limits.h

Макрос	Значение
CHAR_BIT	количество бит в байте
X_MIN	минимум целочисленного типа X (см. варианты ниже — только знаковые и char)
X_MAX	максимум целочисленного типа X (см. варианты ниже)
X = CHAR	тип char
X = SCHAR	тип signed char
X = UCHAR	тип unsigned char
X = SHRT	тип signed short
X = USHRT	тип unsigned short
X = INT	тип signed int
X = UINT	тип unsigned int
X = LONG	тип signed long
X = ULONG	тип unsigned long
X = LLONG	тип signed long long
X = ULLONG	тип unsigned long long

Заголовочный файл cstddef

Данный заголовочный файл вводит два синонима некоторых целочисленных типов:

• size_t — беззнаковый, диапазон которого достаточен для представления размера произвольного массива, который может быть размещён в памяти непрерывно;
• ptrdiff_t — знаковый аналог size_t, разность указателей имеет этот тип.

Заголовочный файл cstdint

Данный заголовочный файл предоставляет синонимы целочисленных типов заданного размера (X может быть равно 8, 16, 32 или 64):

Типы cstdint

Тип	Смысл
intX_t	знаковое целое размера X бит (опциональные)
uintX_t	беззнаковое целое размер X бит (опциональные)
int_fastX_t	знаковое целое размера не меньше X бит
uint_fastX_t	беззнаковое целое размера не меньше X бит
int_leastX_t	наименьшее знаковое целое размера не меньше X бит
uint_leastX_t	наименьшее беззнаковое целое размера не меньше X бит
intmax_t	знаковое целое самого большого размера
uintmax_t	беззнаковое целое самого большого размера
intptr_t	знаковое целое, способное вместить адрес (опциональный)
uintptr_t	беззнаковое целое, способное вместить адрес (опциональный)

Типы, помеченные как “опциональные”, могут не предоставляться конкретной реализацией. Если uintX_t и intX_t предоставляются, то они имеют размер точно X бит. Если intX_t предоставляются, то они используют дополнительный код.

Заголовочный файл cstdlib

В данном заголовочном файле объявлены две функции, которые могут применяться в целочисленных вычислениях: деление с остатком (div) и модуль числа (abs). Варианты функции div возвращают значения структуры div_t и её аналогов, поля которой rem и quot установлены в значение остатка и частного соответственно. Перегруженные варианты div и abs, принимающие long и long long, доступны только в C++. Варианты функций для long long введены в стандартах C++11 и C99.

Варианты функций div и abs

Функция	Тип параметров	Тип результата
div	int, long, long long	div_t, ldiv_t, lldiv_t
ldiv	long	ldiv_t
lldiv	long long	lldiv_t
abs	int, long, long long	int, long, long long
labs	long	long
llabs	long long	long long

Поразрядные двоичные операции

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

Например, поразрядное и, обозначаемое в C++ через & , вычисляет булевское и бит, стоящих в числах слева и справа на одной позиции. Аналогично вводятся поразрядное или | и поразрядное исключающее или (“xor”) ^ . Доступно и поразрядное отрицание (обычно называемое дополнением complement или инверсией), которое обозначается

Операция поразрядное исключающее или обладает следующими свойствами.

• Коммутативность: a ^ b ≡ b ^ a.
• Ассоциативность: (a ^ b) ^ c ≡ a ^ (b ^ c).
• Нильпотентность: a ^ a ≡ 0.
• Управляемое отрицание: 0 ^ a ≡ a,

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

Из приведённых выше свойств легко выводится утверждение (a ^ b) ^ b ≡ a. Данное утверждение обосновывает применимость известного “трюка”, позволяющего обменять значения двух целочисленных переменных без использования явной временной переменной.

На практике не следует применять данный трюк без действительной необходимости — на современных процессорах такой код работает медленнее, чем использование промежуточной переменной (которую компилятор часто может удалить на этапе оптимизации).

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

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

Обозначение в C операций сдвига

Операция	Обозначение	Замечание
линейный сдвиг влево	a << b
линейный сдвиг вправо	a >> b	a — беззнакового типа
арифметический сдвиг вправо	a >> b	a — знакового типа*

*Поддержка арифметического сдвига зависит от конкретной платформы и не гарантируется стандартом.

Ниже показаны результаты сдвига 8-битного слова на 0–4 бит вправо для циклического, линейного и арифметического сдвигов.

Сдвиги вправо

бит	циклич.	линейн.	арифм.
0	11001101	11001101	11001101
1	11100110	01100110	11100110
2	01110011	00110011	11110011
3	10111001	00011001	11111001
4	11011100	00001100	11111100

Упражнение. Продолжите эту таблицу для сдвигов на 5–9 бит.

Операции циклического сдвига аппаратно реализованы во многих процессорах, однако, как правило, не поддерживаются языками высокого уровня напрямую (включая C и C++).

Несложно реализовать циклический сдвиг через комбинацию линейных сдвигов.

Некоторые компиляторы (например, g++) способны оптимизировать данный код, заменив его командой циклического сдвига.

Маской называют последовательность бит, задающую, значения каких бит требуется извлечь путем применения поразрядного и к другой последовательности бит (соответствующие биты в маске установлены в 1, прочие — в 0).

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

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

• Степень 2 n можно получить как 1u << n (линейный сдвиг влево), соответственно произведение a·2 n можно получить как a << n .
• Целая часть частного a/2 n при условии a ≥ 0 может быть вычислена как a >> n (линейный сдвиг вправо).
• Остаток от деления a ≥ 0 на 2 n можно получить, выделив младшие биты (которые пропали бы при сдвиге вправо) с помощью соответствующей маски: a & ((1u << n) — 1) . В частности, можно проверить число a (справедливо и для отрицательных в дополнительном коде) на четность с помощью условия (a & 1) == 0 .
• Проверить, является ли целое число a степенью двойки (или нулём): (a & (a — 1)) == 0 .

Упражнение. Проанализируйте функции возведения числа в целочисленную степень, представленные ниже. Правильно ли они работают и почему? Сколько умножений им требуются для получения результата?

Использование чисел как представлений множеств

Отдельные биты могут использоваться как признаки наличия элементов из некоторого конечного множества в подмножестве (представленном последовательностью бит). Так, если есть множество B = < 0, 1, …, 7 >, то 8-битный байт может служить представлением произвольного подмножества M ⊆ B. Если i ∈ M, то i-й бит байта установлен в единицу (в противном случае — в ноль). Указанный способ представления подмножеств позволяет выполнять теоретико-множественные операции с помощью поразрядных операций.

Упражнение. В таблице ниже замените вопросительные знаки на соответствующий им C++-код.

Дополнительные примеры

Данные примеры являются дополнительными и предназначены для углублённого изучения приёмов программирования и оперирования целыми числами или группами бит.

Проверить значение заданного бита

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

Изменить значение заданного бита

Следующие четыре функции возвращают новое значение слова (с изменённым битом в заданной позиции).

Извлечь битовое поле

Под “битовым полем” в данном примере понимается непрерывный фрагмент машинного слова (например, все биты с 5-го по 10-й включительно: start = 5, length = 6). Пусть задан номер начального бита, принадлежащего битовому полю, и количество бит, входящих в битовое поле. Тогда извлечь значение битового поля в виде беззнакового целого можно следующей функцией.

Установить значение битового поля

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

Наложение маски на value можно убрать, если гарантируется, что value не выходит за пределы диапазона значений битового поля (т.е. value ∈ [0, 2 length –1]).

Некоторые современные процессоры предоставляют команды, выполняющие операции get_bitfield и set_bitfield.

Вычислить ближайшее сверху кратное заданной степени двойки

Пусть заданы натуральные числа P = 2 p и число X. Необходимо вычислить наименьшее число N такое, что N ≥ X и N = nP для некоторого натурального n.

Метод вычисления. В случае, если X mod P не равен нулю, то добавление к X максимального остатка (P – 1) даёт перенос бита в разряд p, а если X mod P равен нулю, то не даёт. Таким образом, если обнулить младшие p бит суммы (X + (P – 1)), то получим искомое: N = (X + (P – 1)) &

Вычислить ближайшую сверху степень двойки

Требуется вычислить число, равное степени двойки, не меньшей, чем заданное натуральное число. Ниже приведён результат для 32-битного числа.

Если имеется эффективная реализация функции leading_zero_bits, то можно использовать её

Проверить чётность количества установленных бит

Рассмотрим 8-битное число, составленное из бит с b₀ по b₇. Число установленных бит можно получить, сложив все разряды числа: b₀ + b₁ + … + b₇. Чётность равна остатку от деления этой суммы на 2. Иными словами, вместо сложения отдельных бит можно использовать операцию исключающее или, выполняющую сложение по модулю 2.

Обратим внимание, что благодаря ассоциативности и коммутативности сложения можно складывать биты в произвольном порядке, например, так: ((b₇ + b₆) + (b₅ + b₄)) + ((b₃ + b₂) + (b₁ + b₀)), то есть сложить пары соседних бит, потом соседние пары бит результата (из которых важен только младший бит), потом соседние четверки бит и т.д. Данный метод применим к произвольному числу бит и позволяет ускорить вычисление с помощью применения поразрядных операций, одновременно задействующих группы бит, уложенные в одном машинном слове.

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

Получить сумму младших бит во всех четвёрках бит числа можно одной операцией умножения на число, составленное из четвёрок бит 0001₂, длиной в машинное слово (почему?), при этом результат будет находиться в четырёх старших битах. Таким образом, вышеприведённый код можно заменить на следующий код. Этот код эффективнее, если целевой процессор умеет быстро умножать (что, в частности, справедливо для современных процессоров семейства x86).

Другой способ оптимизации первого варианта parity не использует умножение и заключается в использовании 32-битного числа как таблицы бит чётности. (Данный способ позаимствован отсюда.)

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

Определить число установленных бит

Относительно медленный, но элегантный и не зависящий от количества разрядов способ (предложен Б.Керниганом), снимающий в цикле по одному установленному биту (справа налево):

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

“Параллельный” вариант, манипулирующий парами, четвёрками и т.д. бит (сразу немного оптимизированный):

Его можно ещё слегка оптимизировать, если заметить, что по крайней мере одно наложение маски избыточно, так как переносы не пересекают последовательности нулевых бит:

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

Два последних варианта позаимствованы отсюда.

Многие процессоры предоставляют команды для выполнения данной операции.

Расстояние по Хэммингу

Вес строки бит по Хэммингу (норма) — количество единичных бит (см. предыдущий пример).

Расстояние между строками бит по Хэммингу (метрика) — количество различающихся бит в одинаковых позициях.

Поменять местами половинки числа

Частный случай циклического сдвига: сдвинуть циклически (хоть влево, хоть вправо) на половину разрядности.

Обратить порядок байт

Необходимость обращения байт иногда возникает из-за требования передачи двоичных данных между компьютерами с разными архитектурами (см. порядок байт). Современные процессоры имеют встроенные команды для быстрого обращения порядка байт (x86) и/или способны работать в разных режимах и быстро переключаться между ними (PowerPC, ARM). Но если требуется реализовать процессорно-независимую функцию, то это можно сделать, например так (метод “в лоб”, эффективен на конвейерных процессорах с большим набором регистров):

Более сложный для понимания способ (см. также следующие примеры с обращением порядка бит) использует меньше операций:

Обратить порядок тетрад

Способ, применённый для обращения порядка байт, можно расширить для обращения порядка тетрад. Нужно поменять местами соседние тетрады и обратить порядок байт.

Обратить порядок бит

Итак, если мы уже умеем обращать порядок тетрад, то можно обратить порядок бит, если обратить его в каждой тетраде — и затем обратить порядок тетрад. Для этого поменяем местами соседние биты, затем пары соседних бит аналогично тому, как поменяли местами соседние тетрады в предыдущем примере.

Впрочем, если базовый swap_bytes реализован стандартными операциями, а не с помощью специальной команды процессора, то лучше не использовать его, а просто распространить применённый метод “наверх” вплоть до половинок 32-битного слова.

Или так (занести маски):

Для расширения указанного метода на 64-битные слова надо будет добавить ещё одну строчку (уже для обмена 32-битных половин) и так далее при каждом удвоении.

Некоторые процессоры (например, семейства ARMv8) предоставляют встроенную команду для обращения порядка бит.

Определить номер самого правого установленного бита

Здесь будем считать, что эта задача эквивалентна задаче вычисления количества идущих подряд младших нулевых бит trailing zeroes , т.е. для нулевого аргумента ответ равен числу разрядов.

Простой и достаточно эффективный (из реализуемых стандартными операциями) способ на основе двоичного поиска, применённый к 32-битным числам.

Если же доступна эффективная реализация (командой процессора) операции вычисления числа установленных бит bit_count или операции leading_zero_bits, описанной в следующем разделе, то можно воспользоваться ими. Заметим, что изолировать младший ненулевой бит в числе x можно, вычислив (0 — x) & x . Если вычесть из этого числа единицу, то количество установленных бит будет равно искомому значению. Впрочем, то же самое можно получить более простым выражением (x — 1) &

Вариант на основе leading_zero_bits потенциально менее эффективен, поскольку надо особым образом обрабатывать значение 0.

Определить номер самого левого установленного бита

Данная задача по сути эквивалентна задаче вычисления округлённого вниз двоичного логарифма числа и родственна задаче подсчёта количества идущих подряд нулевых старших бит leading zeroes . Обе эти задачи могут решаться с помощью команд процессора (см. например: Википедия).

Обратив порядок поиска в примере с реализацией trailing_zero_bits через двоичный поиск, получим следующий код.

Тот же метод для получения номера самого старшего установленного бита (ненулевой аргумент).

При наличии эффективной реализации функции leading_zero_bits, реализация find_first_set тривиальна.

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