Общаясь с одним из своих друзей, я спросил: «что обычно спрашиваю у вас на собеседованиях, когда вы ищете инженеров-кораблестроителей?». Ответ был следующим: «попросят от руки нарисовать коробок спичек в изометрии». Мой друг — недавний выпускник, уже отработавший несколько лет на кораблестроительном заводе инженером-конструктором и ставший небольшим руководителем, был сильно удивлён такому простому вопросу («не мог понять в чём подвох»), и просто нарисовал коробок спичек… После трудоустройства, он рассказал, что участвовал в нескольких собеседованиях при приёме новых сотрудников, и на удивление не все «корабелы» могли пройти такой простой тест. Это меня озадачило, поскольку в моём понимании инженеры-кораблестроители по определению должны рисовать чертежи кораблей, рассчитывать их физику и т.п. Но я не кораблестроитель, чтобы судить, поэтому давайте рассмотрим подобные простые задачи, которые задают программистам на собеседованиях.
Одна из таких простых задач, которую спрашивают наверно на каждом собеседовании — это подсчёт количества бит установленных в единицу. Например, для числа 25510 в десятичной системе счисления количество бит в двоичной системе счисления установленных в единицу равно 8 (111111112). Такая метрика — называется вес Хемминга (Hamming weight). Сам подсчёт битов установленных в единицу используется в криптографии, алгоритмах сжатия, теории кодирования и в других областях. Но если говорить с точки зрения практического программирования, задача интересна, поскольку проверяет знания кандидата в области битовых операций.
Решений данной задачи существует множество и в принципе они все правильные, поскольку в условиях задачи нет требований к производительности. Но давайте добавим это требование и рассмотрим ряд решений.
Решение 1. Наивный подход. Берём число и делим его на 2. Если остаток от операции равен 1, то увеличиваем счётчик на 1. Делаем это 32 раза.
int popcount1(unsigned int x) { int result = 0; int cnt = 32; while (cnt--) { if ((x % 2) == 1) { result++; } x /= 2; } return result; }
Для измерения скорости работы алгоритма выберем интервал: [(UINT_MAX — UINT_MAX/100),UINT_MAX]. В этом интервале много чисел, у которых почти все «старшие» биты установлены в единицу.
Время работы алгоритма (секунд): ~13.3. Измерение проводилось на машине Intel Pentium Dual-Core 2.2 GHz, Ubuntu 10, GCC 4.4.3 усредняя результаты нескольких прогонов. Измерения включают время на проверку корректности алгоритма unit test-ом для каждого значения в интервале.
Решение 1.1. Небольшие оптимизации решения 1: деление на 2 – есть побитовое смещение на 1; если результат после деления равен нулю, то останавливаемся, поскольку очевидно, что 0 не содержит бит равных единице.
int popcount1_1(unsigned int x) { int result = 0; while (x) { if ((x % 2) == 1) { result++; } x >>= 1; } return result; }
Время работы (секунд): ~16.
Решение 1.2. Заменяем деление на проверку младшего бита.
int popcount1_2(unsigned int x) { int result = 0; while (x) { if (x & 0x1) { result++; } x >>= 1; } return result; }
Время работы (секунд): ~15.
Как видим время работы в решениях 1, 1.1 и 1.2 практически одинаковое. Это объясняется тем, что операции целочисленного деления, побитовое и – «&» и побитового смещение выполняются процессором примерно за одинаковое количество тактов.
Решение 2. Можно подсчитать заранее количество бит установленных в единицу для каждого числа в виде lookup таблицы. Очевидно, для 32-х битного числа такая таблица потребует много памяти, что является не рациональным. Но мы можем сделать таблицу для 8-битного числа и подсчитать количество бит 32-х битного числа как сумму бит каждого байта:
unsigned int popcount2_byte_array[256]; inline int popcount2_byte(unsigned char x) { return popcount2_byte_array[x]; } int popcount2(unsigned int x) { return popcount2_byte(x & 0xFF) + popcount2_byte((x >> 8) & 0xFF) + popcount2_byte((x >> 16) & 0xFF) + popcount2_byte((x >> 24) & 0xFF); }
Время работы (секунд): ~2.5. Ускорение 6.4 раз по сравнению с решением 1.1.
Решение 2.1. Подсчитаем заранее массив unsigned short-ов, чтобы уменьшить количество операций. Минус такого похода то, что требуется 64-256 KB RAM.
unsigned int popcount2_1_ushort_array[256*256]; inline int popcount2_1_ushort(unsigned short x) { return popcount2_1_ushort_array[x]; } inline int popcount2_1(unsigned int x) { return popcount2_1_ushort(x & 0xFFFF) + popcount2_1_ushort((x >> 16) & 0xFFFF); }
Время работы (секунд): 1.8. Ускорение 8.8 раз!
Решение 2.2. Подсчитаем заранее массив 4-х битовых чисел [http://c-faq.com/misc/bitcount.html]. Такой поход позволяет сэкономить на памяти, но всё ещё иметь неплохую производительность.
int popcount2_2(unsigned int x) { static int bits[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; int result = 0; while(x) { result += bits[x & 0x0f]; x >>= 4; } return result; }
Время работы (секунд): ~3.2.
В решениях 1, 1.1 и 1.2 есть недостаток — эти алгоритмы будут выполнять все итерации, даже если установлен только один старший бит. Можно ли как-то уменьшить количество итераций и проверить сразу старший бит в таких вырожденных случаях? Следующее алгоритм позволяет это сделать.
Решение 3. x & (x — 1) — при каких x — это выражение будет равно нулю? 0, 2n. Значит если x содержит только 1 старший бит выставленный в единицу, то выражение x & (x — 1) будет равно нулю. Если воспользоваться этой формулой, то можно получить алгоритм Вегнера:
unsigned int popcount3(unsigned int x) { int result = 0; while (x) { x &= x - 1; result++; } return result; }
Время работы (секунд): 7.5. Не самый оптимальный, но очевидно самый «изящный» алгоритм ;). Ускорение в 2.1 раза по сравнению с решением 1.1.
Решение 4. Есть ряд алгоритмов основанных на свойствах чисел. Например, следующий алгоритм:
inline unsigned int popcount4(unsigned int x) { x = x - ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); int result = ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; return result; }
Время работы (секунд): 1.58. Ускорение 10.12 раз по сравнению с алгоритмом 1.1! Также этот метод быстрее всех описанных выше! Но у него есть один недостаток — его практически невозможно понять без изучения оригинальной статьи.
Решение 5. Можно использовать встроенные команды языка программирования или компилятора. Например, в GCC есть интринсити __builtin_popcount.
inline unsigned int popcount5(unsigned int x) { return __builtin_popcount(x); }
Время работы (секунд): 1.7.
Если дизассемблировать __builtin_popcount, то можно увидеть что это библиотечная функция реализующая метод описанный в решении 2.
Решение 6. Можно использовать векторные инструкции, см. SSE popcount. Рассмотрение этого метода я оставлю за рамками этого поста.
Таким образом, самым оптимальным решением с точки зрения производительности и читаемости кода является использование готовой функции GCC __builtin_popcount ;).
P.S. Не претендую на авторство описанных алгоритмов.
Еще предлагаю один вариант добавить в замерки
#include
#include
size_t cpp_popcount(unsigned int x)
{
std::bitset bs(val);
return bs.count();
}
есть предположение, что оптимизирующий компилятор как раз заменит на 5 или 4.
как-то так…
блин, проглотил все же код неправильно.
вторая попытка с тэгами
#include
#include
size_t cpp_popcount(unsigned int val)
{
const std::bitset bs(val);
return bs.count();
}