Bit counting, обзор методов

Одна из классических задач в программировании (по крайней мере, о способах ее решения упоминает Дональд Кнут в своем классическом труде) - подсчет выставленных в “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 и еще куча опций), исходники здесь.

 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, которая содержит море полезной информации по различным операциям над битами и битовыми массивами.

comments powered by Disqus