Поразрядные операции с целыми числами

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

2015


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


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

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

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

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

Число 9512 в позиционной десятичной системе
цифра разряд название разряда
9 3 тысячи
5 2 сотни
1 1 десятки
2 0 единицы

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

цn–1 цn–2ц1 ц0 = val(цn–1rn–1 + val(цn–2rn–2 + … + val(ц1r1 + val(ц0r0.

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

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

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

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

цn–1 цn–2цi цi–1ц1 ц0 = цn–1 цn–2цi · ri + цi–1ц1 ц0.

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

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

x0 = x,

xi · r + val(цi–1) = xi–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 (получаемые остатки выписываем справа налево).

Откуда заключаем, что 12510 = 11111012.

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

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

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

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

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

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

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

1 / -10

== 0

1 % -10

== 1

21 / -10

== -2

21 % -10

== 1

-1 / 10

== 0

-1 % 10

== -1

-21 / 10

== -2

-21 % 10

== -1

-1 / -10

== 0

-1 % -10

== -1

-21 / -10

== 2

-21 % -10

== -1

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

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

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

Благодаря своей минимальности двоичная система проще остальных реализуется “в железе”. Так, если заряд ячейки памяти больше порогового уровня Q1, считаем, что она хранит 1, если же заряд меньше порогового уровня Q0, считаем, что она хранит 0. Таким образом, ячейка памяти, способная находиться в двух различимых состояниях, может хранить один бит. Две таких ячейки могут хранить два бита и суммарно находиться в 22 = 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. Тетрада может хранить 24 = 16 разных значений, поэтому её значение удобно записывать одной шестнадцатеричной цифрой hexadecimal digit. Традиционно в качестве шестнадцатеричных цифр используются десять арабских цифр и латинские буквы A, B, C, D, E и F для недостающих цифр со значениями 10, 11, 12, 13, 14 и 15 соответственно. В свою очередь, байт может принимать 28 = 256 = 162 разных значений. Значение байта можно записать двумя шестнадцатеричными цифрами.

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

Перевод между системами
Биты Цифра Значение
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) = 011001002 + (–001011002) = 011001002 + 110100112 + 1 = (1)001110002 = 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) = –100000002 = 011111112 + 1 = 100000002 = –128.

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

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

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

Встроенные

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

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

Минимумы и максимумы, задающие минимальные гарантированные диапазоны целочисленных типов, выписаны по приложению 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

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

Заголовочный файл 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 или инверсией), которое обозначается ~.

Пример действия поразрядных операций на тетрадах
Операция Слева Справа Результат
& 1100 1010 1000
| 1100 1010 1110
^ 1100 1010 0110
~ нет 1100 0011


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

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

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

// Пара переменных.
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;

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


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

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

Обозначение в 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++).

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

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

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


Маской называют последовательность бит, задающую, значения каких бит требуется извлечь путем применения поразрядного и к другой последовательности бит (соответствующие биты в маске установлены в 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-битный байт может служить представлением произвольного подмножества MB. Если iM, то i-й бит байта установлен в единицу (в противном случае — в ноль). Указанный способ представления подмножеств позволяет выполнять теоретико-множественные операции с помощью поразрядных операций.

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

Конечные множества и последовательности бит
Операция кратко C++
пустое множество 0
полное множество All ?
принадлежность i ∈ A ((1u << i) & A) != 0
подмножество A ⊆ B ?
дополнение All \ A ~A
пересечение A ∩ B A & B
объединение A ∪ B ?
разность A \ B ?
симм. разность A Δ B ?


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

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

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

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

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, 2length–1]).

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

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

Пусть заданы натуральные числа P = 2p и число X. Необходимо вычислить наименьшее число N такое, что NX и 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-битное число, составленное из бит с b0 по b7. Число установленных бит можно получить, сложив все разряды числа: b0 + b1 + … + b7. Чётность равна остатку от деления этой суммы на 2. Иными словами, вместо сложения отдельных бит можно использовать операцию исключающее или, выполняющую сложение по модулю 2.

Обратим внимание, что благодаря ассоциативности и коммутативности сложения можно складывать биты в произвольном порядке, например, так: ((b7 + b6) + (b5 + b4)) + ((b3 + b2) + (b1 + b0)), то есть сложить пары соседних бит, потом соседние пары бит результата (из которых важен только младший бит), потом соседние четверки бит и т.д. Данный метод применим к произвольному числу бит и позволяет ускорить вычисление с помощью применения поразрядных операций, одновременно задействующих группы бит, уложенные в одном машинном слове.

Вариант для 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; // четность в младшем бите  
}

Получить сумму младших бит во всех четвёрках бит числа можно одной операцией умножения на число, составленное из четвёрок бит 00012, длиной в машинное слово (почему?), при этом результат будет находиться в четырёх старших битах. Таким образом, вышеприведённый код можно заменить на следующий код. Этот код эффективнее, если целевой процессор умеет быстро умножать (что, в частности, справедливо для современных процессоров семейства 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