Коробок спичек в изометрии или простые задачи для программистов. Часть I.

Общаясь с одним из своих друзей, я спросил: «что обычно спрашиваю у вас на собеседованиях, когда вы ищете инженеров-кораблестроителей?». Ответ был следующим: «попросят от руки нарисовать коробок спичек в изометрии». Мой друг — недавний выпускник, уже отработавший несколько лет на кораблестроительном заводе инженером-конструктором и ставший небольшим руководителем, был сильно удивлён такому простому вопросу («не мог понять в чём подвох»), и просто нарисовал коробок спичек… После трудоустройства, он рассказал, что участвовал в нескольких собеседованиях при приёме новых сотрудников, и на удивление не все «корабелы» могли пройти такой простой тест. Это меня озадачило, поскольку в моём понимании инженеры-кораблестроители по определению должны рисовать чертежи кораблей, рассчитывать их физику и т.п. Но я не кораблестроитель, чтобы судить, поэтому давайте рассмотрим подобные простые задачи, которые задают программистам на собеседованиях.

Одна из таких простых задач, которую спрашивают наверно на каждом собеседовании — это подсчёт количества бит установленных в единицу. Например, для числа 255₁₀ в десятичной системе счисления количество бит в двоичной системе счисления установленных в единицу равно 8 (11111111₂). Такая метрика — называется вес Хемминга (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, 2ⁿ. Значит если 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. Не претендую на авторство описанных алгоритмов.