Посчитать количество единиц в числе

#cpp #c

Вопрос предельно прост: надо посчитать количество единиц в двоичном представлении
числа за О(1). Линии и логарифмы даже не предлагайте. Интересует только О(1).
    

Ответы

Ответ 1

Да не вопрос.

unsigned int count = 0;
for (; n; n <<= 1)
    count += n & 1;


Всего не более CHAR_BIT * sizeof(n) итераций, то есть, ограничено константой.



Вот ещё вам классический Кернигановский способ:

unsigned int count = 0;
for (; n; count++)
    n &= (n - 1); // убираем младший бит


Ограничение сверху то же, но на практике работает быстрее, т. к. использует одну
итерацию на единичный бит.



Подборка различных способов подсчёта битов есть тут.


Ответ 2

Ну, я, как обычно, не могу без экспериментов :)
Итак, варианты - 

// Hackers' Delight
int popHD(unsigned int x)
{
    x = x - ((x>>1) & 0x55555555);
    x = (x & 0x33333333) + ((x >>2) & 0x33333333);
    x = (x + (x>>4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x3F;
}

int popLong(unsigned int x)
{
    int n = 0;
    while(x)
    {
        if (x&0x1) ++n;
        x >>= 1;
    }
    return n;
}

int popKern(unsigned int x)
{
    int n = 0;
    for (; x; n++)
        x &= (x - 1); // убираем младший бит
    return n;
}

int pop8(unsigned int x)
{
    static int count8[] =
    {
        // Из-за размера таблица удалена
    };
    return count8[x&0xFF] + count8[(x >> 8)&0xFF]
        + count8[(x >> 16)&0xFF] + count8[(x >> 24)&0xFF];
}

int pop16(unsigned int x)
{
    static int count16[] =
    {
        // Из-за размера таблица удалена
    };
    return count16[x&0xFFFF]+count16[(x>>16)&0xFFFF];
}

__popcnt(unsigned int) // MS VC++ specific


Если кому хочется посмотреть весь код - нет вопросов: http://vpaste.net/fD5DV

Далее набиваю вектор из 100000000 значений:

const int Count = 100000000;
vector v;
v.reserve(Count);
for(int i = 0; i < Count; ++i)
    v.push_back(dis(eng));


Ну, а все тесты имеют один вид:

{
    int count = 0;
    muTimer mu;  // Мой таймер
    for(unsigned int x: v) count += __popcnt(x);
    cout << count << "\n";
}


Для кэширования один проход делаю без засекания времени.

Вот как выглядят результаты на моей машине:

popHD    popLong    popKern     pop8      pop16     __popcnt
------------------------------------------------------------
89 ms    2514 ms    1505 ms    215 ms    200 ms       83 ms
88 ms    2525 ms    1482 ms    210 ms    195 ms       82 ms


Понятно, что от раза к разу пляшет, но несильно - для того и показываю два результата.

Выводы делайте сами :) Чистое суммирование  

{
    int count = 0;
    muTimer mu;  // Мой таймер
    for(unsigned int x: v) count += x;
    cout << count << "\n";
}


дает примерно 25-27 ms.

Update
Посмотрел ассемблер. popHD сразу по 4 числа работает, с xmm регистрами, так что не
знаю даже, радоваться или огорчаться :) Для отдельного значения __popcnt, понятно,
быстрее...


Ответ 3

Создайте lookup-таблицу для 8-битных байтов (и/или 16-битных слов) и затем примените
ее для подсчета битов в типе любого размера. Пока размер рассматриваемых типов константен,
время подсчета тоже является константным.

Является ли такой подход (как, впрочем, и любой другой) O(1) - это уже у вас надо
спрашивать.

P.S. Я обычно не мелочусь и сразу забабахиваю таблицу для 32-битных слов. Солидная
таблица для солидных господ.


Ответ 4

Или же можно просто пользоваться стандартной библиотекой:

#include  //std::cout
#include    //std::bitset
#include    //std::numeric_limits

int main() {
    std::bitset::digits> bitset(7);
    std::cout << "7 has " << bitset.count() << " ones." << std::endl;
    return EXIT_SUCCESS;
}


Ответ 5

В gсс/g++ можете воспользоваться встроенной функцией


  Built-in Function: int __builtin_popcount (unsigned int x)

Returns the number of 1-bits in x.



(хотя, конечно, скорость ее работы по сравнению с предложенными табличными алгоритмами,
неизвестна).

P.S.

для X86 в gcc (g++) семейство функций __builtin_popcount было реализовано на основе
таблицы из 256 элементов (на март 2017 посмотрел disasm  в gdb и увидел реализацию
как в int pop(unsigned long long x) в ответе @Harry (c 0x5555555555555555 и т.д.));

по крайней мере в clang и icc эта функция (__builtin_popcount) называется так же,
а в MSVC ее зовут __popcnt;


Ответ 6

Ну, например, для 64-битового unsigned long long:

int pop(unsigned long long x)
{
    x = (x & 0x5555555555555555) + ((x >>  1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >>  2) & 0x3333333333333333);
    x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >>  4) & 0x0F0F0F0F0F0F0F0F);
    x = (x & 0x00FF00FF00FF00FF) + ((x >>  8) & 0x00FF00FF00FF00FF);
    x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF);
    x = (x & 0x00000000FFFFFFFF) + ((x >> 32) & 0x00000000FFFFFFFF);
    return x & 0x0000000000007F;
}


Или вариант для 32-битного:

int pop(unsigned long long x)
{
    x = (x & 0x55555555) + ((x >>  1) & 0x55555555);
    x = (x & 0x33333333) + ((x >>  2) & 0x33333333);
    x = (x & 0x0F0F0F0F) + ((x >>  4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + ((x >>  8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
    return x & 0x3F;
}


Он же, слегка переделанный:

int pop(unsigned long x)
{
    x = x - ((x>>1) & 0x55555555);
    x = (x & 0x33333333) + ((x >>2) & 0x33333333);
    x = (x + (x>>4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x3F;
}


Ответ 7

Лень формулировать это на крестах, да и главное - идея. Идея такая: делаем в памяти
массив длиной 65536 байт, значениями элементов которого являются количества единиц
для соответствующего 16-битного целого. Потом обрабатываем ваше число фрагментами по
два байта и суммируем количества единиц.