Одна из классических задач в программировании (по крайней мере, о способах ее решения упоминает Дональд Кнут в своем классическом труде) – подсчет выставленных в “1″ бит в числе.
Зачем?
Почему эта задача важна? Во-первых, она интересна сама по себе – есть несколько способов решения, которые кардинально отличаются производительностью и выбор правильной реализации может значительно ускорить ваш код. Во-вторых, у нее много практических применений – например, в протоколах маршрутизации или поиска. И, в-третьих, она встречается на собеседованиях в крупных компаниях, так что будет не лишним немного освежить свои знания.
Поиск в сети даст достаточно подробностей, здесь же я хочу привести краткую сводку фактов.
Методы подсчета можно условно разделить на три области – shifting, algebraic logic и table lookup.
Shifting
С первыми, в принципе, все понятно – они занимаются посчетом битов в числе, постепенно сдвигая его вправо. Небольшие вариации (обнуление самого правого единичного бита вместо сдвига всего числа) могут дать выигрыш в скорости, если заранее известно, что в данных преобладают “0″ или, наоборот, “1″. В целом, это самая медленная группа методов подсчета.
Algebraic logic
Методы этой группы основаны различных математических операциях, например, на группировке битов внутри числа в несколько проходов. Так, один из методов сначала разбивает биты в числе попарно, переводя кол-во единиц в каждой паре в бинарное представление (00 -> 00, 01 -> 01, 10 -> 01, 11 -> 10), потом по 4 бита, 8 и так далее. Группа методов работает в среднем в несколько (у меня – порядка 4) раз быстрее, чем итеративный подсчет.
Table lookup
Наконец, последняя группа методов сначала строит таблицы вида [число]->[количество выставленных в "1" битов] и потом пользуется ими для быстрого получения значения. Варьируется в основном только размер таблиц (8-16-… бит). Эти методы самые быстрые, особенно на больших объемах данных, когда потери времени на расчет таблиц незначительны по сравнению со временем самого подсчета.
Сравнение производительности
Вот конкретные результаты прогона различных алгоритмов на моей машине (Darwin Kernel Version 10.3.0, Intel Core 2 Duo 2.26 GHz). Собрано с оптимизацией под скорость (-O3 и еще куча опций). Исходники - https://github.com/dreamiurg/bitcount.
8-bit lookup table calculation took 0.32 ms 16-bit lookup table calculation took 2.34 ms ---> Shitfing methods Iterated 4.646 sec 21.524 Mcps Sparse 3.475 sec 28.775 Mcps Dense 3.670 sec 27.251 Mcps ---> Algebraic methods Parallel 1.172 sec 85.328 Mcps Nifty 1.204 sec 83.083 Mcps Hakmem 1.217 sec 82.193 Mcps ---> Table lookup methods Precomp 8 0.732 sec 136.684 Mcps Precomp 16 0.688 sec 145.268 Mcps
Как видим, самый медленный метод отличается от самого быстрого практически в 7 раз, при этом потери на создание таблиц минимальны и измеряются миллисекундами.
Дальнейшее чтение
Конкретные алгоритмы легко найти в сети. Среди хороших ресурсов для начала – статья “Puzzle: Fast Bit Counting“, к ней и отсылаю к ней за деталями. Кроме того, обратите внимание на статью “Bit Twiddling Hacks“, которая содержит море полезной информации по различным операциям над битами и битовыми массивами.
Tags: algorithms, c++, performance