Общее оглавление

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

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

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

ц_n–1 ц_n–2 … ц₁ ц₀ = val(ц_n–1)·r^n–1 + val(ц_n–2)·r^n–2 + … + val(ц₁)·r¹ + val(ц₀)·r⁰.

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

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

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

ц_n–1 ц_n–2 … ц_i ц_i–1 … ц₁ ц₀ = ц_n–1 ц_n–2 … ц_i · rⁱ + ц_i–1 … ц₁ ц₀.

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

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

x₀ = x,

x_i · r + val(ц_i–1) = x_i–1.

Взяв остаток от деления 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¹⁰ = 1024 ≈ 10³.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Прямой код

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

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

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

Обратный код

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

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

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

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

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

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

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

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

Недостатки: несимметричность диапазонов отрицательных и положительных чисел; если сменить знак у наименьшего числа, получится оно же. В 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++ не задаёт конкретных величин).

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

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

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

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

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

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

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

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

Типы, помеченные как “опциональные”, могут не предоставляться конкретной реализацией. Если 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.

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

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

// Пара переменных.
int a = 23, b = 42;

// Обычный обмен через промежуточную переменную.
int t = a;
a = b; // теперь a == 42
b = t; // теперь b == 23

// Трюк через xor.
a ^= b; // промежуточное значение a == 61
b ^= a; // теперь b == 42
a ^= b; // теперь a == 23

// Трюк через xor в одну строчку.
a ^= b ^= a ^= b;

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

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

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

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

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

#include <cstdint> // чтобы использовать целые с заданным размером в битах
inline uint32_t rotate_right(uint32_t arg, unsigned bits)
{
  bits &= 31; // взять bits mod 32
  return (arg << (32 - bits)) | (arg >> bits);
}

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

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

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

double power(double x, unsigned n)
{
  double xi = 1.0;
  while (true)
  {
    if (n & 1)
      xi *= x;
    n >>= 1;
    if (n == 0)
      return xi;
    x *= x;
  }
}
 
double power(double x, int n)
{
  return n < 0?
    1.0 / power(x, unsigned(-n)) // отрицательный показатель
  : power(x, unsigned(n));       // неотрицательный показатель
}

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

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

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

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

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

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

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

inline bool test_bit(unsigned word, unsigned bit)
{
  return (word & (1u << bit)) != 0;
}

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

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

// Установить заданный бит
inline unsigned set_bit(unsigned word, unsigned bit)
{
  return word | (1u << bit);
}

// Сбросить заданный бит
inline unsigned reset_bit(unsigned word, unsigned bit)
{
  return word & ~(1u << bit);
}

// Поменять значение заданного бита на противоположное
inline unsigned toggle_bit(unsigned word, unsigned bit)
{
  return word ^ (1u << bit);
}

// Установить заданный бит в заданное значение
inline unsigned set_bit(unsigned word, unsigned bit, bool value)
{
  const auto mask = 1u << bit;
  return (word & ~mask) | (value? mask: 0);
}

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

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

inline unsigned get_bitfield(unsigned word, unsigned start, unsigned length)
{
  return (word >> start) & ((1u << length) - 1);
}

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

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

inline unsigned set_bitfield(unsigned word, unsigned start, unsigned length, unsigned value)
{
  const auto mask = (1u << length) - 1;
  return (word & ~(mask << start)) | ((value & mask) << start);
}

Наложение маски на 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)) & ~(P – 1).

inline unsigned round_up_to_pow2(unsigned x, unsigned pow2)
{
  const auto pow2m1 = pow2 - 1;
  assert((pow2 & pow2m1) == 0); // pow2 обязано быть степенью двойки
  return (x + pow2m1) & ~pow2m1;
}

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

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

inline uint32_t round_up_to_pow2(uint32_t x)
{
  --x;
  x |= x >> 1;   // Группа наложений-сдвигов эффективно
  x |= x >> 2;   // заменяет цикл линейную последовательность вида
  x |= x >> 4;   // x |= x >> 1; x |= x >> 2; x |= x >> 3; ...
  x |= x >> 8;   // x |= x >> 31;
  x |= x >> 16;  // На каждое удвоение разрядности достаточно
  return x + 1;  // добавлять одну такую строчку.
}

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

inline uint32_t round_up_to_pow2(uint32_t x)
{
  const unsigned not_pow2 = (x & (x - 1)) != 0;
  return uint32_t(1) << (32 - (leading_zero_bits(x) + not_pow2));
}

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

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

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

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

inline unsigned parity(uint32_t bits)
{
  bits ^= bits >> 1;  // соседние биты
  bits ^= bits >> 2;  // соседние пары бит
  bits ^= bits >> 4;  // соседние четверки бит
  bits ^= bits >> 8;  // соседние байты
  bits ^= bits >> 16; // соседние пары байт
  return bits & 1; // четность в младшем бите  
}

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

inline unsigned parity(uint32_t bits)
{
  bits ^= bits >> 1; // соседние биты
  bits ^= bits >> 2; // соседние пары бит
  bits = (bits & 0x1111'1111) * 0x1111'1111;
  return (bits >> 28) & 1;
}

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

inline unsigned parity(uint32_t bits)
{
  bits ^= bits >> 16;
  bits ^= bits >> 8;
  bits ^= bits >> 4;
  return (0x6996u >> (bits & 0xF)) & 1;
}

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

inline unsigned parity(uint32_t bits)
{
  return bit_count(bits) & 1;
}

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

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

unsigned bit_count(unsigned bits)
{
  unsigned counter = 0;
  for (; bits != 0; ++counter)
    bits &= bits - 1;
  return counter;
}

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

unsigned bit_count(unsigned bits)
{
  static const unsigned nibble_count[] =
  {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
  };

  unsigned counter = 0;
  while (bits != 0)
  {
    counter += nibble_count[bits & 0xF]; // взять младшую тетраду
    bits >>= 4; // отбросить младшую тетраду
  }

  return counter;
}

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

inline unsigned bit_count(uint32_t bits)
{
  unsigned counter = 0;
  counter = bits - ((bits >> 1) & 0x5555'5555);
  counter = ((counter >> 2) & 0x3333'3333) + (counter & 0x3333'3333);
  counter = ((counter >> 4)  + counter) & 0x0F0F'0F0F;
  counter = ((counter >> 8)  + counter) & 0x00FF'00FF;
  counter = ((counter >> 16) + counter) & 0x0000'FFFF;
  return counter;
}

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

inline unsigned bit_count(uint32_t bits)
{
  unsigned counter = 0;
  counter = bits - ((bits >> 1) & 0x5555'5555);
  counter = ((counter >> 2) & 0x3333'3333) + (counter & 0x3333'3333);
  counter = ((counter >> 4)  + counter) & 0x0F0F'0F0F;
  counter += counter >> 8;
  return (counter + (counter >> 16)) & 0x3F;
}

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

inline unsigned bit_count(uint32_t bits)
{
  bits = bits - ((bits >> 1) & 0x5555'5555);
  bits = (bits & 0x3333'3333) + ((bits >> 2) & 0x3333'3333);
  return ((bits + (bits >> 4) & 0x0F0F'0F0F) * 0x0101'0101) >> 24;
}

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

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

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

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

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

inline unsigned hamming_distance(uint32_t a, uint32_t b)
{
  return bit_count(a ^ b);
}

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

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

inline uint32_t swap_halves(uint32_t word)
{
  return (word << 16) | (word >> 16);
}

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

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

inline uint32_t swap_bytes(uint32_t word)
{
  return ((word & 0x0000'00FF) << 24)
       | ((word & 0x0000'FF00) << 8)
       | ((word & 0x00FF'0000) >> 8)
       | ((word & 0xFF00'0000) >> 24);
}

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

inline uint32_t swap_bytes(uint32_t word)
{
  word = ((word & 0x00FF'00FF) << 8) | ((word >> 8) & 0x00FF'00FF);
  return (word << 16) | (word >> 16);
}

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

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

inline uint32_t swap_nibbles(uint32_t word)
{
  return swap_bytes(
    ((word & 0x0F0F'0F0F) << 4)
  | ((word & 0xF0F0'F0F0) >> 4));
}

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

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

inline uint32_t swap_bits(uint32_t word)
{
  word = ((word << 1)  & 0xAAAA'AAAA) | ((word >> 1)  & 0x5555'5555);
  word = ((word << 2)  & 0xCCCC'CCCC) | ((word >> 2)  & 0x3333'3333);
  return swap_nibbles(word);
}

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

inline uint32_t swap_bits(uint32_t word)
{
  word = ((word << 1) & 0xAAAA'AAAA) | ((word >> 1) & 0x5555'5555);
  word = ((word << 2) & 0xCCCC'CCCC) | ((word >> 2) & 0x3333'3333);
  word = ((word << 4) & 0xF0F0'F0F0) | ((word >> 4) & 0x0F0F'0F0F);
  word = ((word << 8) & 0xFF00'FF00) | ((word >> 8) & 0x00FF'00FF);
  return (word << 16) | (word >> 16);
}

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

inline uint32_t swap_bits(uint32_t word)
{
  word = ((word & 0x5555'5555) << 1) | ((word >> 1) & 0x5555'5555);
  word = ((word & 0x3333'3333) << 2) | ((word >> 2) & 0x3333'3333);
  word = ((word & 0x0F0F'0F0F) << 4) | ((word >> 4) & 0x0F0F'0F0F);
  word = ((word & 0x00FF'00FF) << 8) | ((word >> 8) & 0x00FF'00FF);
  return (word << 16) | (word >> 16);
}

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

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

См. также: 0, 1, 2 и 3.

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

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

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

inline unsigned trailing_zero_bits(uint32_t word)
{
  if (word & 0x1) // половина чисел -- нечётные
    return 0;

  const auto old_word = word;
  unsigned bits = 1;
  if ((word & 0xFFFF) == 0)
  {
    word >>= 16;
    bits += 16;
  }

  if ((word & 0xFF) == 0)
  {
    word >>= 8;
    bits += 8;
  }

  if ((word & 0xF) == 0)
  {
    word >>= 4;
    bits += 4;
  }

  if ((word & 0x3) == 0)
  {
    word >>= 2;
    bits += 2;
  }

  return old_word? bits - (word & 0x1) : 32;
}

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

inline unsigned trailing_zero_bits(unsigned word)
{
  // Ограничение на тип word накладывается функцией bit_count,
  // unsigned выбрано в качестве обозначения, что сам метод,
  // используемый trailing_zero_bits, годится для любого размера.
  return bit_count((word - 1) & ~word);
}

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

inline unsigned trailing_zero_bits(unsigned word)
{
  return word? 31 - leading_zero_bits((0 - word) & word): 32;
}

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

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

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

inline unsigned leading_zero_bits(uint32_t word)
{
  const auto old_word = word;
  unsigned bits = 0;
  if ((word & 0xFFFF'0000) == 0)
  {
    word <<= 16;
    bits += 16;
  }

  if ((word & 0xFF00'0000) == 0)
  {
    word <<= 8;
    bits += 8;
  }

  if ((word & 0xF000'0000) == 0)
  {
    word <<= 4;
    bits += 4;
  }

  if ((word & 0xC000'0000) == 0)
  {
    word <<= 2;
    bits += 2;
  }

  const auto non_zero_bits = bits + ((word >> 31) == 0);
  return old_word? non_zero_bits: 32;
}

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

inline unsigned find_first_set(uint32_t word)
{
  assert(word != 0);
  unsigned bit = 31;
  if ((word & 0xFFFF'0000) == 0)
  {
    word <<= 16;
    bit -= 16;
  }

  if ((word & 0xFF00'0000) == 0)
  {
    word <<= 8;
    bit -= 8;
  }

  if ((word & 0xF000'0000) == 0)
  {
    word <<= 4;
    bit -= 4;
  }

  if ((word & 0xC000'0000) == 0)
  {
    word <<= 2;
    bit -= 2;
  }

  return bit - (~word >> 31);
}

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

inline unsigned find_first_set(uint32_t word)
{
  assert(word != 0);
  return 31 - leading_zero_bits(word);
}

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

inline unsigned leading_zero_bits(uint32_t word)
{
  word |= (word >> 1);
  word |= (word >> 2);
  word |= (word >> 4);
  word |= (word >> 8);
  word |= (word >> 16);
  return 32 - bit_count(word);
}

Общее оглавление

Кувшинов Д.Р. © 2015