Битовые операции III: подсчёт бит
Чётность количества установленных бит
Рассмотрим 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;
}
Наконец, если доступна быстрая функция определения числа установленных бит (например, реализованная через команду процессора), обозначенная здесь как bit_count, то достаточно взять младший бит её результата.
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;
}
Два последних варианта позаимствованы отсюда.
Ассемблерные аналоги x86: POPCNT.
Расстояние по Хэммингу
Вес строки бит по Хэммингу (норма) — количество единичных бит (см. предыдущий пример).
Расстояние между строками бит по Хэммингу (метрика) — количество различающихся бит в одинаковых позициях.
При наличии функции bit_count реализовать функцию, вычисляющую расстояние по Хэммингу между бит-строками, не представляет труда.
inline unsigned hamming_distance(uint32_t a, uint32_t b)
{
return bit_count(a ^ b);
}
Определить номер самого правого установленного бита
Будем считать, что эта задача эквивалентна задаче вычисления количества идущих подряд младших нулевых бит (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)
{
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;
}
Ассемблерные аналоги x86: BSF, TZCNT.
Определить номер самого левого установленного бита
Данная задача по сути эквивалентна задаче вычисления округлённого вниз двоичного логарифма числа и родственна задаче подсчёта количества идущих подряд нулевых старших бит (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);
}
Ассемблерные аналоги x86: BSR, LZCNT.
Битовые операции II: изменение порядка бит
Циклический сдвиг
Циклический сдвиг бит представляет собой операцию, напоминающую прокручивание содержимого бит-строки на месте: при сдвиге влево биты, «выпадающие» с левого конца, вставляются с правого конца (сохраняя исходный относительный порядок следования), при сдвиге вправо, наоборот, биты, «выпадающие» с правого конца, вставляются с левого.
Реализовать циклический сдвиг на заданное число бит достаточно просто. Например, сдвиг влево:
inline uint32_t rotate_left(uint32_t word, unsigned bits)
{
return (word << bits) | (word >> (32 - bits));
}
Замечание. Если bits больше 31, то результат может быть различным (зависит от компилятора и процессора). При необходимости корректно обрабатывать случай bits > 31 на любом процессоре следует в качестве bits использовать остаток от деления bits на 32 (применить маску: bits &= 31).
Ассемблерные аналоги x86: ROL, ROR.
Поменять местами половинки слова
Частный случай циклического сдвига: сдвинуть циклически (хоть влево, хоть вправо) на половину разрядности.
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);
}
Ассемблерные аналоги x86: BSWAP.
Обратить порядок тетрад
Способ, применённый для обращения порядка байт, можно расширить для обращения порядка тетрад (половинок байт). Нужно поменять местами соседние тетрады и обратить порядок байт.
inline uint32_t swap_nibbles(uint32_t word)
{
return swap_bytes(
((word & 0x0F0F'0F0F) << 4)
| ((word >> 4) & 0x0F0F'0F0F);
}
Обратить порядок бит
Итак, если мы уже умеем обращать порядок тетрад, то обратить порядок бит можно, обратив его в каждой тетраде, а затем обратив порядок тетрад. Для этого поменяем местами соседние биты, затем пары соседних бит аналогично тому, как поменяли местами соседние тетрады в предыдущем примере.
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) предоставляют встроенную команду для обращения порядка бит.
Битовые операции I: битовые поля, степень двойки
Введение
Решил выложить накопленный материал по реализации некоторых операций с помощью стандартных операторов C. Планируется три части. Данный материал довольно легко найти на английском языке, и некоторые ссылки на источники я здесь размещу.
Предполагается, что читатель осведомлён о том, что такое поразрядные операции, и какие из них доступны в стандартном C. Стандартные целочисленные типы заданной ширины определены в stdint.h (cstdint в C++, «int» в случае C++ можно заменить на bool). Тип «unsigned» используется, чтобы показать отсутствие конкретных требований по разрядности параметра.
Так как во многих случаях описанные операции поддерживаются современными процессорами непосредственно, компиляторы предоставляют реализующие их специальные нестандартные функции («intrinsics» или «builtins»). Если целевой процессор поддерживает нужные команды, то при использовании интринсиков компилятор будет транслировать код в эти команды. К сожалению, не всегда гарантируется автоматическая подмена неподдерживаемых команд программными реализациями, поэтому при написании кроссплатформенного кода могут понадобиться собственные «заменители» для общего случая. Да и не всегда хочется отягощать код использованием интринсиков.
Простейшие манипуляции
Проверить значение заданного бита
Данное действие выполнить весьма просто: нужно установить бит с заданным номером, что легко достигается с помощью операции сдвига влево, и использовать полученное значение как маску.
inline int test_bit(unsigned word, unsigned bit)
{
return (word & (1u << bit)) != 0;
}
Ассемблерные аналоги x86: BT.
Изменить значение заданного бита
Следующие четыре функции возвращают новое значение слова (с изменённым битом в заданной позиции):
// Установить заданный бит
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, int value)
{
unsigned mask = 1u << bit;
return (word & ~mask) | (value? mask: 0);
}
Ассемблерные аналоги x86: BTS, BTR, BTC.
Извлечь битовое поле
Итак, операцией поразрядного сдвига влево можно установить бит в заданной позиции. Если теперь вычесть единицу, то получим битовую строку, в которой установлены все биты в позициях правее ранее установленного бита.
unsigned mask = (1u << bits) - 1;
Теперь можно сдвинуть полученную таким образом маску влево, чтобы установленные биты совпали с битами, стоящими в желаемых позициях (битовым полем). Под «битовым полем» в данном примере понимается непрерывный фрагмент машинного слова (например, все биты с 5-го по 10-й включительно).
Пусть задан номер начального бита, принадлежащего битовому полю (start), и количество бит, входящих в битовое поле (length; соответственно, все биты с 5-го по 10-й включительно: start = 5, length = 6). Тогда извлечь значение битового поля в виде беззнакового целого можно следующей функцией:
inline unsigned get_bitfield(
unsigned word, unsigned start, unsigned length)
{
return (word >> start) & ((1u << length) - 1);
}
Ассемблерные аналоги x86: BEXTR (BMI).
Установить значение битового поля
Обратная к предыдущей задача: требуется записать определённые значения бит в заданное битовое поле. Это можно сделать следующим образом (функция возвращает новое значение машинного слова):
inline unsigned set_bitfield
(
unsigned word, // Исходное значение
unsigned start, // Номер младшего бита поля
unsigned length, // Длина поля
unsigned value // Новое значение поля
)
{
unsigned mask = (1u << length) - 1;
return (word & ~(mask << start))
| ((value & mask) << start);
}
Наложение маски на value можно убрать, если гарантируется, что value не выходит за пределы диапазона значений битового поля (т.е. value ∈ [0, 2length-1]).
Совместить два значения
Изменение значения битового поля является частным случаем поразрядного совмещения (смешивания) значений. Пусть дана маска (mask), каждый бит которой равен 0, если значение соответствующего разряда результата следует взять из первой бит-строки (a), и 1, если значение разряда следует взять из второй бит-строки (b). Тогда выполнить операцию совмещения достаточно легко:
inline unsigned bit_blend(
unsigned mask, unsigned a, unsigned b)
{
return (a & ~mask) | (b & mask);
}
Степень двойки
Проверить, является ли число степенью двойки
Степень двойки в двоичной системе имеет вид 0..010…0 (только один бит установлен). Поэтому при вычитании единицы получаем 0..001…1, т.е. только в случае степени двойки выполняется условие нулевого пересечения числа с самим собой, уменьшенным на единицу. Итак,
inline int is_pow2(unsigned word)
{
return word & (word - 1) == 0;
}
Ряд подобных простых комбинаций, которые могут использоваться как строительные кубики, был введён в систему команд x86 в составе набора BMI.
Вычислить ближайшее сверху кратное заданной степени двойки
Пусть заданы натуральные числа P = 2p и число 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)
{
unsigned pow2m1 = pow2 - 1;
// pow2 обязано быть степенью двойки
assert((pow2 & pow2m1) == 0);
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, подсчитывающей количество идущих подряд старших нулей (можно реализовать её на основе команд x86 BSR или (ABM/BMI) LZCNT, в дальнейшем я планирую привести реализацию на основе стандартных операций), то можно использовать её:
inline unsigned round_up_to_pow2(unsigned x)
{
unsigned not_pow2 = (x & (x - 1)) != 0;
return 1u << (32 - (leading_zero_bits(x) + not_pow2));
}
evetro 