Комментарии 70
@Exosphere пожалуйста, дайте работягам markdown вместо wysiwyg
Хорошая компиляция, на литкоде, кстати, много задач на битовые операции и алгоритмы
Должны быть, но едва ли там требуется написать что-то из того, что я в статье описал. Сам я первый раз познакомился с подобными штуками на олимпиадном программировании, но как ни странно эти методы там не особо применимы.
Есть такой типичный сценарий когда нужен LSB: есть стандартное решение задачи о коммивояжёре динамическим программированием на подмножествах. Суть в том, чтобы посчитать функцию "Какая длина минимального пути, проходящего по множеству вершин S и заканчивающегося в T?". Чтобы её вычислить нужно перебрать предпоследнюю вершины из S и взят минимум по путям S\{T}. Перебирать можно все биты и там все просто, а можно методом, который я писал в статье x = x & (x - 1), это в среднем уменьшает в 2 раза количество итераций. Проблема остается в том, что мы выделяем число, у которого ровно один бит, но не знаем какой, а он нужен для вычислений, вот здесь и нужен LSB. Проблема в целом в том, что с использованием LSB в таком сценарии итоговый выигрышь по производительности не очень велик (максимум в 2 раза) -- это значительно для продакшена, но в рамках олимпиадной задачи обычно незначительно.
(про разворот битов) В общем виде такой алгоритм имел бы сложность O(n log n).
А зачем он тогда такой нужен, если наивный алгоритм O(n)?
За De Bruijn метод спасибо, раньше он мне не попадался, а жаль, метод шикарен.
Есть довольно известная книга Алгоритмические трюки для программистов. Там есть все это и еще многое другое.
О, спасибо! Добротная книга, в такой статье грех не сослаться на неё, добавил в описание. Единственное, метода Де Брюина я там не увидел.
Вроде как все описанные методы описаны в TAOCP vol. 4a Кнута, но при всём моем к нему уважении там это написано максимально непонятно
Имеет смысл добавить, что в оригинале она "Hackerʼs Delight", и под этим названием даже лучше известна в мире (и ищется по ссылкам).
На x86 это выполнится внутри кеша L1:
; Разворачивает [EAX], не портит остальные регистры
push ebx
push ecx
mov ecx,32
@@loop:rcr eax,1
rcl ebx,1
loopnz @@loop
mov eax,ebx
pop ecx
pop ebx
retПисал на память, мог ошибиться но тут важна сама идея. Для свапа байтов есть отдельные команды, вроде bswap. Подобную конструкцию можно написать для любого процессора, а у некоторых даже есть свои команды разворота. И когда уже компиляторы научатся в это? Оформить в виде встроенного макроса, чтобы оставаться платформонезависимым.
Для изменения порядка байтов в GCC есть __builtin_bswap16(), __builtin_bswap32(), __builtin_bswap64() (и где-то даже __builtin_bswap128()).
Для изменения порядка битов в Clang есть __builtin_bitreverse32() и т.п.; добавление в GCC пока только обсуждается.
В стандартном заголовке <bit> C++20 есть большинство описанных в статье манипуляций с битами, но нет разворота битов. Предложение добавить разворот битов я даже отправлял кому-то из комитета, но ответили - типа это не основная операция и добавлять не будем. Хотя чем она хуже тех же popcount() или countl_zero() ? ИМХО это невозможно объективно измерить и тут нужно использовать принцип функциональной полноты - операция достаточно фундаментальная, интуитивно очевидная, есть в некоторых архитектурах и в то же время программная реализация достаточно громоздка - значит нужно добавлять.
Я думаю, тут дело в количестве алгоритмов, зависимых от «разворота битов». Я не помню популярных алгоритмов, использующих такую операцию.
Зеркалирование битмапов, например. Что касается перестановки ьайтов, то оно полезно при адаптации данных big/little endian.
Про байты - понятно. А вот биты - не очень.
Для чего применяется зеркалирование битмапов?
bit/little endian - там про порядок байт в слове. Первое, что приходит в голову - hton/ntoh на "стандартном" x86. А вот чтобы прямо на уровне битов разворачивать - вроде сильно экзотично; пока не сталкивался.
bit/little endian - там про порядок байт в слове.
Не совсем, мягко говоря. IEN 137, который ввёл эти термины, явно связывает и с порядком нумерации бит. И это он не сам придумал, а отражает практику.
Вот пример: структура данных - битовый массив (bitset). Делаем код доступа:
#define ACCESS_TYPE uint8_t
#define SHIFT 3
#define LOW_MASK 7u
_Bool get_bit(void *bitset_area, unsigned index) {
unsigned offset = index >> SHIFT;
unsigned shift = index & LOW_MASK;
// специально разложил по отдельным переменным для максимальной понятности...
ACCESS_TYPE memvalue = ((ACCESS_TYPE*) bitset_area)[offset];
ACCESS_TYPE mask = 1 << shift;
return 0 != (memvalue & mask);
}
Теперь если у нас LE, мы можем менять: uint8_t, 3 в сдвиге индекса, 7 в маске - на, соответственно: uint16_t, 4, 15; uint32_t, 5, 31; uint64_t, 6, 63 - будет тот же результат.
А вот если платформа - BE, так не получится, от смены размера используемого значения всё поплывёт, результаты будут отличаться. Надо править. Проще всего поставить в вычислении shift - написать ~index вместо index, тогда они снова будут одинаковыми (в пределах BE - но отличаться от LE).
В компиляторах это ещё отражается, например, в следующем: цитата из <netinet/ip.h> линукса:
struct iphdr
{
#if __BYTE_ORDER == __LITTLE_ENDIAN
unsigned int ihl:4;
unsigned int version:4;
#elif __BYTE_ORDER == __BIG_ENDIAN
unsigned int version:4;
unsigned int ihl:4;
#else
# error "Please fix <bits/endian.h>"
#endif
...
Потому что для LE принято, аналогично описанному с bitset, что битовые поля заполняют отведённое место начиная с младших битов, а для BE - со старших.
В тех случаях, когда нумерация битов явно присутствует в машинных командах, она может быть как 0=LSB (совместимая с LE), так и 0=MSB (совместимая с BE). Так вот, платформа SystemZ (aka IBM Z; потомок S/360), которая последовательно BE, использует (команды типа RISBG) именно 0=MSB. Аналогично у POWER, который разрабатывался как BE, хотя может с памятью работать как LE. В документации у неё тоже 0=MSB. В результате надо следить: одна и та же часть регистра может обозначаться 0..31, если речь про 32-битную часть, и 32..63, если смотрим как на полный 64-битовый.
Тут много таки злобных гитик спряталось...
Ну вот на практике - пишем в заголовок файла магическую константу - число 0x58485053. Т.е. берём адрес числа, и выводим в поток 4 байта. На LE получается символьная последовательность "SPHX"
Собираем бинарь под MIPS, запускаем - в файле оказывается в начале "XHPS". Т.е. порядок байт поменялся, но при этом порядок бит в байте остался тем же (иначе были бы уже совсем другие символы).
Хабр сглючило
Ну, байтсвап это же про "endianess". Кстати, mips адаптируемый и чаще в режиме little endian, как и x86, а вот M68K точно big endian.
ну, LE/BE это тоже про endianess.
Я о том, что всё ограничивается байтсвапом. А биты в байте задом наперёд, в основном, не перекладывают. MIPS может и адаптируется, но в каких-то нетривиальных конфигах. А на тех же SOHO роутерах, где остался - там есть MIPS, есть MIPSel, и с точки зрения пользователя с этим ничего не сделаешь.
Да, если у вас дискрет рассмотрения - один байт (один символ ASCII), проблему можно и не заметить.
Хотя и в этом случае могут быть тонкости. Например, CRC чаще считается в порядке от младших битов в каждом байте (ибо традиция от RS-232), но бывает и наоборот.
Это уже сильно глубокая абстракция.
Байт - он вроде как везде одинаков.
В смысле, что абсолютное (числовое) значение не зависит от порядка бит. Разные операции (&, |, сдвиги) - тоже.
Копирования вроде того же memcpy - копируют целиком байты.
При сериализации (если нужно его побитно записать куда-то) я программно могу двигать в любом удобном направлении. Кажется, единственный момент, где иной порядок бит может выстрелить - это если есть аппаратная сериализация. Где я говорю железу - вот, сериализуй мне этот байтик. А оно внезапно - где-то младшим битом вперёд, где-то старшим. Другие способы "обнаружить" иной порядок бит не приходят в голову.
(не, ну, конечно, если сдвиги тоже "сломаны" - в смысле, есть 0x1, я выполняю 0x1 >> 1 (и ожидаю получить ноль), но вдруг получаю 2, потому что единственный значащий бит оказался крайним левым, и я переместил его на одну позицию вправо... Но это же совсем контр-интуитивно, ведь правда?)
Байт - он вроде как везде одинаков.
В смысле, что абсолютное (числовое) значение не зависит от порядка бит. Разные операции (&, |, сдвиги) - тоже.
Но я описал, как понимание группы байт как одного значения или нескольких - начинают давать зависимость от того, с какой стороны мы считаем биты.
Это не очень очевидно.
Если в одном байте мы не можем определить порядок бит, то что здесь меняет последовательность?
Там те же байты. Её можно перебирать (итерировать) с начала, либо с конца. Но там по-прежнему те же байты.
Как у них там внутри расположены биты - вроде неважно, покуда если я записываю в файл байт с символом "S" - он остаётся им самым, независимо от endianess платформы
Если в одном байте мы не можем определить порядок бит, то что здесь меняет последовательность?
Почему не можем? Можем. Для каждого бита кроме самого старшего есть один и только один, который для него следующий по старшинству вверх. И наоборот.
И это определение не зависит от порядка байт на машине. А вот на что он влияет - это как правильно стыковать группы бит из разных байт в более крупную единицу ("слово" и тому подобные).
Как у них там внутри расположены биты - вроде неважно, покуда если я записываю в файл байт с символом "S" - он остаётся им самым, независимо от endianess платформы
Я описал, для чего это становится важно.
Это уже сильно глубокая абстракция.
Байт - он вроде как везде одинаков.
В смысле, что абсолютное (числовое) значение не зависит от порядка бит. Разные операции (&, |, сдвиги) - тоже.
Копирования вроде того же memcpy - копируют целиком байты.
При сериализации (если нужно его побитно записать куда-то) я программно могу двигать в любом удобном направлении. Кажется, единственный момент, где иной порядок бит может выстрелить - это если есть аппаратная сериализация. Где я говорю железу - вот, сериализуй мне этот байтик. А оно внезапно - где-то младшим битом вперёд, где-то старшим. Другие способы "обнаружить" иной порядок бит не приходят в голову.
(не, ну, конечно, если сдвиги тоже "сломаны" - в смысле, есть 0x1, я выполняю 0x1 >> 1 (и ожидаю получить ноль), но вдруг получаю 2, потому что единственный значащий бит оказался крайним левым, и я переместил его на одну позицию вправо... Но это же совсем контр-интуитивно, ведь правда?)
Быстрое преобразование фурье. Какое-нибудь хеширование. Также эта перестановка вылезает в разных структурах данных для группировки значений.
С хешированием проблема курицы и яйца: применяют имеющиеся быстрые операции.
Не очень понимаю, как в преобразовании Фурье это применяется. Простые примеры реализации вообще без битовых операций. Но, видимо, есть какие-то супер-быстрые.
А какие структуры данных вы имеете в виду? Я интересуюсь структурами данных, но упоминание перестановки битов встречал один раз, и то не помню, в каком контексте.
В быстром перобразовании фурье сначала все элементы перемешивают кладя i-ый на место revbits(i). Про хеширование с аргументом вашим в целом согласен. Про структуры дынных вроде смутно помню, что в каких-то деревьях номер элемента описывал положение элемента в дереве и там битовыми операциями включая разворот можно было быстро находить наименьшего общего предка элементов, но как-то сформулировать не могу.
смутно помню, что в каких-то деревьях номер элемента описывал положение элемента в дереве и там битовыми операциями включая разворот можно было быстро находить наименьшего общего предка элементов
Скорее всего речь идет о представлении дерева виде правильной скобочной последовательности -- одна из основ succint структур данных. Детально не подскажу, но там точно битовых трюков используется. Конкретно реверс битов я нашел немного в другой штуке -- wavelet tree
https://github.com/simongog/sdsl-lite/blob/master/include/sdsl/wt_pc.hpp#L844
Если честно то я и для popcount() и поиска первого единичного/нулевого бита не знаю применений. Но это не делает эти операции менее важными - я интуитивно понимаю что они достаточно фундаментальны с точки зрения computer science, чтобы их включить в библиотеку. А разворот битов однажды доводилось применять - в одном протоколе биты в некотором числовом поле нужно было развернуть, для какой-то древней аппаратуры.
и поиска первого единичного/нулевого бита не знаю применений.
Определение двоичного порядка - например, важная промежуточная операция для вычислений с плавающей точкой, этого уже достаточно, чтобы делать аппаратный ускоритель ("приоритетный энкодер"). Вспомогательное действие для оценки порядка - например, для определения глубины стека для сортировок. Или определение, влезает ли число в поле, отведённое для него (хотя это можно делать через два сдвига и сравнение).
Но последние добавки этих команд (например, lzcnt, tzcnt, popcnt в x86) не из этого, а из каких-то более специфических применений. ChatGPT подсказал про lzcnt, например, "Оптимизация иерархии Bounding Volume Hierarchy (BVH), где требуется быстро находить старший значащий бит." А вот popcnt: "Алгоритмы SHA, MD5, CRC используют POPCNT для быстрого подсчёта различий между битовыми представлениями данных. В шифровании по методу Блюма-Блюма-Шуба (BBS) и других генераторах случайных чисел POPCNT применяется для оценки энтропии." Я не проверял, насколько это им критично и насколько ускоряет, но примерно похоже на правду.
А разворот битов однажды доводилось применять - в одном протоколе биты в некотором числовом поле нужно было развернуть, для какой-то древней аппаратуры.
Ну так это решается через несколько сдвигов - and - or, за логарифмическую цену. Как и вся эта группа - за логарифм от битового размера. Просто имея реализацию в железе получается таки быстрее, а на процессорах в миллиарды транзисторов добавка таких модулей это незаметно для общей массы.
В начале статьи есть ссылки на 4 опен сорс проекта, где они используются
Я использовал поиск последнего единичного бита для сжатия целых чисел, в один битовый стрим писались обрезанные до последнего значащего бита числа, в другой длинна и там работал арифметический кодер сжимавший длинны, а все это вместе применялось в сжатии индекса в СУБД.
Для байтов: __builtin_bswap. Который может разворачиваться и в код типа того, что был в статье, и в машинные команды (если ISA поддерживает), и вычисляться во время компиляции. Более того, LLVM и gcc распознают некоторые варианты рукописных реализаций этого дела и заменяют их на интринсик. Интринсик платформонезависимый, но не компиляторонезависимый, увы; но оно стандартизировано в C++: std::byteswap, в Rust (_type_::swap_bytes). А в C пока нет.
Та же ситуация с popcount, clz/ctz из статьи. Для разворота битов как-то хуже.
Кстати, в архитектуре x86/x64 большинство этих функций уже есть. Для манипуляций битами по индексу BT/BTS/BTC, для поиска единичных битов (BSF, BSR), для подсчета единичных битов (POPCNT). А вот инструкции разворота битов в байте (RBIT) почему-то нет (но зато она есть в ARM). А жаль - было бы хорошо иметь полный набор операций над битами в процессоре, и заодно в виде операций языка программирования. Скажем, унарные << и >> можно было бы приспособить для bit scans (поиск номера единичного бита с начала и с конца слова), бинарные <<< и >>> для битовых вращений (ROR и ROL) и т.д.
Благодарю за статью.
Можете пояснить по бенчмаркам: что в колонках? Например первая строка - 1 итерация и 45.5 секунд - это что?
Бенчмарки сделаны с помощью google benchmark, в статье приведен его консольный вывод, вот он же на гитхабе
Бенчмарки где написано All 32-bit uint -- это прогон метода для всех 2^32 значений uint32_t. Одна итерация означает, что бенчмарк запускался один раз, 45.5 секунд -- время его выполнения. Есть несколько бенчмарков где прогоняется только 32 значения -- числа с одним единичным битом, они очень маленькие и google benchmark сам решает прогонять его несколько раз, число итераций он выбирает сам в этом случае.
Вот код бенчмарка
используется операция деления с остатком, которая обычно более вычислительно затратная, чем другие арифметические действия, впрочем очень похоже, что в современных компиляторах это не так
На самом деле операция и правда затратная, но в данном случае делитель константный, поэтому компилятор может выразить деление через несколько дешевых операций (умножения и сдвиги).
Погодите, а как такое произошло? Код прогоняется вот таким циклом
for (uint32_t x = 0; x != (1 << 24); ++x) { \
for (size_t i = 1; i < 32; ++i) { \
benchmark::DoNotOptimize(method(x, i)); \
} \
}https://github.com/Malkovsky/bit_tricks/blob/main/src/benchmarks.cpp#L19C1-L23C8
метод benchmark::DoNotOptimize не запрещает внутренние оптимизации, но как будто в метод не константы передаются. Непонятно
Там же внутри остаток от деления на 37 - константу. DoNotOptimize просто не дает компилятору выкинуть вызов, потому что результат его работы, вообще говоря, игнорируется.
C 37 понятно, согласен. Но там же потом при делении на 2^k-1 % окказывается лучше всех остальных
https://github.com/Malkovsky/bit_tricks/actions/runs/13550126312/job/37871458130#step:8:63
Возможно компилятор умеет деление на 2^k-1 оптимизировать так же, как деление на 2^k. Компилятор распознал и заменил наивный метод на какой-то еще более оптимальный. Надо смотреть ассемблерный выхлоп. Так-то операция % очень медленная в общем случае. Много раз заменял ее на вычитание и все очень сильно ускорялось.
Или это в процессоре оптимизация? Какая версия компилятора у вас там? Дизассемблер последнего gcc показывает наивную реализацию.
Обстоятельно о подсчёте единичных битов: автор предлагает комбинированный способ, который может быть ещё быстрее.
Та статья безнадёжно устарела:
Инструкция POPCNT из SSE4.2 не включена в список тестирования, потому что у меня нет процессора, который поддерживает SSE4.2.
Почему в текущей статье нет ни слова о POPCNT я не знаю.
Давайте отвечу тут на это и соседнее сообщение. на уровне "__builtin_popcount вызывает процессорную инструкцию" я как раз понимаю, но вот что там внутри уже нет. Подсчет единичных битов с помощью __builtin_popcount включен в сравнение
Чего я не знал до написания статьи -- того, что __builtin_popcount компилируется в POPCNT только при указании директивы #pragma GCC target("popcnt"), а без неё в call __popcountdi2. За это спасибо внимательному зрителю
И да, с popcnt там все на порядок быстрее.
__builtin_popcount компилируется в POPCNT только при указании директивы #pragma GCC target("popcnt"),
Эээ? Я думал что достаточно передать -march в котором инструкция есть.
UPD: возможно надо передать что-то из -msse2/-msse3/-msse4. Но надеюсь что достаточно -march.
И вы тогда гляньте ещё моих ссылок, в современных процах куча инструкций для битовых операций, они покрывают (почти?) всё что вы перечисляете в статье.
Не, в этом то плане я не спорю, сам изначально написал
Точно могу сказать, что в случае их доступности надо использовать их
Осекся только когда результаты бенчмарков посмотрел, собственно самое время немного подправить замеры
они покрывают (почти?)
скорее всего только select(x, i) не покрывается
Хорошая статья, я очень много из неё повторяю, в общем то не секрет, что не я всё это придумал)
Добавил референс
Включаю в сравнение методы __builtin_popcount, __builtin_ctz , но понятия не имею что внутри происходит.
Ну как так-то? Погуглить жеж можно. Оно вызывает процессорные инструкции (при их наличии):
https://en.wikipedia.org/wiki/Find_first_set#Hardware_support
https://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT
alexey@alexey-mini:/opt/work/bit_tricks/build[main]$ ./bt_benchmarks
Unable to determine clock rate from sysctl: hw.cpufrequency: No such file or directory
This does not affect benchmark measurements, only the metadata output.
2025-02-28T19:47:35+07:00
Running ./bt_benchmarks
Run on (12 X 24.121 MHz CPU s)
CPU Caches:
L1 Data 64 KiB
L1 Instruction 128 KiB
L2 Unified 4096 KiB (x12)
Load Average: 2.27, 2.87, 2.86
-------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------------------------
All 32-bit uint/Count bits set naive 44722 ms 44708 ms 1
All 32-bit uint/Count bits set iterate set bits 1247 ms 1247 ms 1
All 32-bit uint/Count bits set in parallel 3961 ms 3960 ms 1
All 32-bit uint/Count bits set with lookup table 2392 ms 2392 ms 1
All 32-bit uint/Count bits set with builtin 1261 ms 1261 ms 1
All 32-bit uint/Reverse naive 43851 ms 43810 ms 1
All 32-bit uint/Reverse parallel 1259 ms 1259 ms 1
All 32-bit uint/Reverse lookup 3059 ms 3058 ms 1
All 24-bit uint/Select naive 5619 ms 5617 ms 1
All 24-bit uint/Select parallel 1407 ms 1407 ms 1
All 32-bit uint/LSB naive 5532 ms 5532 ms 1
All 32-bit uint/LSB parallel 6294 ms 6292 ms 1
All 32-bit uint/LSB float 2061 ms 2061 ms 1
All 32-bit uint/LSB lookup 2630 ms 2629 ms 1
All 32-bit uint/LSB mod lookup 2820 ms 2820 ms 1
All 32-bit uint/LSB De Bruijn 1258 ms 1258 ms 1
All 32-bit uint/LSB builtin ctz 1254 ms 1254 ms 1
All 32-bit single bit uint/LSB naive 178 ns 178 ns 3941619
All 32-bit single bituint/LSB parallel 45.0 ns 45.0 ns 15750512
All 32-bit single bituint/LSB float 13.0 ns 13.0 ns 53948241
All 32-bit single bit uint/LSB lookup 29.3 ns 29.3 ns 24045150
All 32-bit single bituint/LSB mod lookup 21.5 ns 21.5 ns 31944799
All 32-bit single bituint/LSB De Bruijn 0.475 ns 0.475 ns 1000000000
All 32-bit single bituint/LSB builtin ctz 0.476 ns 0.476 ns 1000000000
All 24-bit uint/Division by 2^k-1 naive 319 ms 319 ms 2
All 24-bit uint/Division by 2^k-1 cycle v1 946 ms 946 ms 1
All 24-bit uint/Division by 2^k-1 cycle v2 1285 ms 1284 ms 1
All 24-bit uint/Division by 2^k-1 lookup 2918 ms 2915 ms 1Вот результаты с Apple M2 Max
Подозрительно выглядят 37 и 38. Либо они на arm64 в самом деле настолько быстрые, либо там что-то "порешал" компилятор.
Кстати, собралось не с первого раза. По дефолту бенч собирается в версии Debug, т.е. совсем не для бенча. А при явном указании RelWithDebInfo - сборка падает в недрах google-bench (пришлось туда лезть). Вы, наверное, там где-то добавили во флаги "все варнинги трактовать как ошибки". Не надо так.
Полагаю, что 37 и 38 -- это LSB De Bruijn и LSB builtin ctz. В GCC/Clang весь Де Брюин оптимизируется в tzctz. Почему именно на числах с одним единичным битом получается на порядок быстрее, чем в убунте -- хз.
Кстати, собралось не с первого раза. По дефолту бенч собирается в версии Debug, т.е. совсем не для бенча.
Так тип сборке вообще не указан CMakeLists.txt, это уже на усмотрение пользователя как он хочет собирать, для CI это вот тут прописано
https://github.com/Malkovsky/bit_tricks/blob/main/.github/workflows/cmake-multi-platform.yml#L53
А при явном указании RelWithDebInfo - сборка падает в недрах google-bench (пришлось туда лезть). Вы, наверное, там где-то добавили во флаги "все варнинги трактовать как ошибки". Не надо так.
google benchmark добавляется вот так и никаких патчей для него дальше нет, так что адресуйте претензии к google benchmark, который не собирается с -Werror
Вот ещё немного в копилку https://graphics.stanford.edu/~seander/bithacks.html
Оказалось, что я забыл привести код для параллельного разворота битов, исправил.
Алгоритмы манипуляций с битами