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

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

// 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<unsigned int> 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, понятно, быстрее...

Да не вопрос.

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); // убираем младший бит

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

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

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

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

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

В 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;

Ну, например, для 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;
}

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