Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 72
@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", и под этим названием даже лучше известна в мире (и ищется по ссылкам).
Для изменения порядка байтов в GCC есть __builtin_bswap16(), __builtin_bswap32(), __builtin_bswap64() (и где-то даже __builtin_bswap128()).
Для изменения порядка битов в Clang есть __builtin_bitreverse32() и т.п.; добавление в GCC пока только обсуждается.
В стандартном заголовке <bit> C++20 есть большинство описанных в статье манипуляций с битами, но нет разворота битов. Предложение добавить разворот битов я даже отправлял кому-то из комитета, но ответили - типа это не основная операция и добавлять не будем. Хотя чем она хуже тех же popcount() или countl_zero() ? ИМХО это невозможно объективно измерить и тут нужно использовать принцип функциональной полноты - операция достаточно фундаментальная, интуитивно очевидная, есть в некоторых архитектурах и в то же время программная реализация достаточно громоздка - значит нужно добавлять.
Я думаю, тут дело в количестве алгоритмов, зависимых от «разворота битов». Я не помню популярных алгоритмов, использующих такую операцию.
Про байты - понятно. А вот биты - не очень.
Для чего применяется зеркалирование битмапов?
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". Т.е. порядок байт поменялся, но при этом порядок бит в байте остался тем же (иначе были бы уже совсем другие символы).
ну, 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
Оказалось, что я забыл привести код для параллельного разворота битов, исправил.
UPD. Уже было обсуждение про разворот битов, но думаю стоит добавить: clang 19.1.0 компилирует __builtin_bitreverse64 в .... инструкцию vgf2p8affineqb. Кто не в курсе -- это инструкция общего вида для преобразования байта путем умножения его на битовую матрицу 8х8 с арифметкой поля GF(2). Предназначалось это в большей степени для реализации GF(2^8), но нашло и такое интересное применение
взято из Алиса копается
Когда мне надоедает заниматься перекладыванием джейсонов, и хочется почитать про битовые трюки и их применение, я иду читать Wojciech Muła: http://0x80.pl/notesen.html
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритмы манипуляций с битами