Перейти к содержимому
Topos Uranos
Русский

Биты и математическая библиотека

Краткое содержание

Целое число для процессора есть ряд битов, и C++ предлагает операторы, которые действуют на этот ряд столбец за столбцом: &, |, ^ и ~, а также сдвиги << и >>. Этот урок учит вычислять их вручную, использовать их, чтобы хранить несколько флагов в одном целом числе с помощью масок, и распознавать сдвиги, которые стандарт не определяет. Затем он объясняет, почему 2 ^ 3 равно 1, а не 8, и почему побитовые операторы требуют скобок. Вторая половина представляет математическую библиотеку: функции <cmath>, константы <numbers>, наибольший общий делитель и наименьшее общее кратное из <numeric> и битовые функции <bit>, вместе с принципом, верным для любого языка: то, что библиотека предлагает правильным и проверенным, не переписывают.

Цели обучения

  1. Вычислять вручную результат &, |, ^, ~ и сдвигов для небольших целых чисел.
  2. Отличать определённые сдвиги (в том числе сдвиги отрицательных чисел, начиная с C++20) от тех, что являются неопределённым поведением, и предсказывать результат первых.
  3. Использовать маски, чтобы проверить, установить, сбросить и переключить бит.
  4. Объяснять, почему 2 ^ 3 равно 1, а не 8, и выбирать между std::pow и сдвигом в зависимости от случая.
  5. Использовать в формулах функции <cmath> (std::sqrt, std::pow, std::abs, std::hypot, тригонометрические) и константы <numbers>, такие как std::numbers::pi.

Побитовые операторы

Урок Целые числа и их представление показал, что int есть ряд битов, 32 в системах курса, и что его значение равно сумме весов позиций, где стоит 1. До сих пор, однако, программа обращалась с целым числом только как с числом: складывала, умножала и делила его. Между тем тот же ряд допускает и другое прочтение, как набор из 32 ответов «да» или «нет», и для такого прочтения в C++ есть четыре оператора, которые работают с битами по одному, без переноса между позициями.

Биты нумеруются справа, начиная с 0: бит kk есть бит с весом 2k2^k. Так, в числе 1212, которое в двоичной записи есть 1100, установлены биты 2 и 3 и сброшены биты 0 и 1.

Операторы таковы. Побитовое И, a & b, даёт 1 в каждой позиции, где и у a, и у b стоит 1. Побитовое ИЛИ, a | b, даёт 1 там, где 1 есть хотя бы у одного из двух. Исключающее ИЛИ, a ^ b, даёт 1 там, где 1 есть ровно у одного из двух, то есть там, где биты различаются. Побитовое НЕ, ~a, имеет один операнд и инвертирует каждый бит. Таблицы первых трёх для пары битов pp и qq совпадают с таблицами конъюнкции, дизъюнкции и исключающей дизъюнкции:

pqp&qp∣qp^q11110100110101100000\begin{array}{cc|ccc} p & q & p \mathbin{\&} q & p \mid q & p \mathbin{\hat{}} q \\ \hline 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}

Тот, кто изучал курс «Математическая логика I», узнает здесь логические связки, где 1 означает истину, а 0 ложь: побитовый оператор есть не что иное, как связка, применённая ко всем столбцам сразу. Отсюда следует способ вычисления вручную: оба числа записывают в двоичной системе одно под другим, выравнивая по правому краю, и применяют таблицу к каждому столбцу, не заботясь о соседних.

ПримерДвенадцать и десять, столбец за столбцом

Числа 12=12 = 1100 и 10=10 = 1010 обладают тем свойством, что их четыре столбца перебирают все четыре сочетания двух битов; поэтому на них можно увидеть все три таблицы сразу.

Доказательство

  1. Данные: 1100 есть 12, а 1010 есть 10. Столбцы слева направо содержат пары (1,1)(1, 1), (1,0)(1, 0), (0,1)(0, 1) и (0,0)(0, 0).

  2. Первый столбец 12 & 10: оба бита равны 1, и И даёт 1.

  3. Второй столбец: 1 и 0. Достаточно одного 0, чтобы И дало 0.

  4. Третий столбец: 0 и 1; И снова даёт 0.

  5. Четвёртый столбец: 0 и 0 дают 0. Строка результата, 1000, есть 8: 12 & 10 равно 8.

  6. ИЛИ устанавливает каждый столбец, где есть хотя бы одна 1: 1110, то есть 12 | 10 равно 14.

  7. Исключающее ИЛИ устанавливает только столбцы, биты которых различаются: 0110, и 12 ^ 10 равно 6.

Программа ниже подтверждает рисунок. Поле форматирования {:04b}, представленное в уроке о целых числах, выводит значение в двоичной системе четырьмя цифрами, дополненными нулями.

Программа на C++
#include <print>​int main(){    const int a{0b1100};    const int b{0b1010};    std::println("a     = {:04b} = {}", a, a);    std::println("b     = {:04b} = {}", b, b);    std::println("a & b = {:04b} = {}", a & b, a & b);    std::println("a | b = {:04b} = {}", a | b, a | b);    std::println("a ^ b = {:04b} = {}", a ^ b, a ^ b);    std::println("~a    = {}", ~a);}
Вывод
a     = 1100 = 12b     = 1010 = 10a & b = 1000 = 8a | b = 1110 = 14a ^ b = 0110 = 6~a    = -13

Последняя строка требует объяснения. НЕ инвертирует все 32 бита a, а не только четыре выводимых: 28 нулей слева становятся единицами, а int, который начинается с 1, в дополнительном коде отрицателен. Между тем в дополнительном коде противоположное число получают, инвертируя биты и прибавляя 1, то есть −x=∼x+1-x = {\sim}x + 1; следовательно, ∼x=−x−1{\sim}x = -x - 1, и ~12 равно −13-13. Итак, побитовое НЕ над целым числом со знаком даёт число, которое редко интересно как число: оно интересно как битовая комбинация, и поэтому с битами предпочтительно работают в беззнаковых типах, как будет видно в параграфе о масках.

Предупреждение о малых типах. Перед операцией C++ преобразует в int всякий операнд более узкого целого типа, например std::uint8_t; это продвижение, которое урок Арифметические операции описал для арифметических операций, и оно действует и здесь. Отсюда следует, что ~flags при flags типа std::uint8_t со значением 5 есть не байт 11111010, а int −6-6, среди 32 битов которого 24 единицы добавлены слева; лишь при обратном сохранении в std::uint8_t значение усекается до восьми битов и получается ожидаемый байт 250.

Не следует путать побитовые операторы с логическими операторами урока Отношения и логика. 6 && 3 есть true: оба операнда отличны от нуля, а результат имеет тип bool. 6 & 3, напротив, есть целое число, составленное из столбцов, где у обоих стоит 1. Кроме того, && вычисляется по короткой схеме, а & всегда вычисляет оба операнда.