Подскажите пожалуйста каким самым быстрым способом сделать подсчет единичных бит в значении типа unsigned int;

Сразу что приходит в голову цикл 32итерации и суммировать единичные биты... как еще можно чтобы не делать 32 итерации?

Здравствуйте, Аноним, Вы писали:

А>Подскажите пожалуйста каким самым быстрым способом сделать подсчет единичных бит в значении типа unsigned int;
А>Сразу что приходит в голову цикл 32итерации и суммировать единичные биты... как еще можно чтобы не делать 32 итерации?

Допустим, для 8 бит считаем поиском по таблице, а для 32 бит суммируем результат 8 битных компонент.

Здравствуйте, D14, Вы писали:

D14>Здравствуйте, Аноним, Вы писали:

А>>Подскажите пожалуйста каким самым быстрым способом сделать подсчет единичных бит в значении типа unsigned int;
А>>Сразу что приходит в голову цикл 32итерации и суммировать единичные биты... как еще можно чтобы не делать 32 итерации?

D14>Допустим, для 8 бит считаем поиском по таблице, а для 32 бит суммируем результат 8 битных компонент.

для 8-ми бит нужна таблица 256 элементов получается!!!!

Здравствуйте, Аноним,

uint8_t num_of_bits32(uint32_t _arg)
{
    _arg = (_arg & 0x55555555L) + ((_arg >> 1) & 0x55555555L);
    _arg = (_arg & 0x33333333L) + ((_arg >> 2) & 0x33333333L);
    _arg = (_arg + (_arg >> 4)) & 0x0F0F0F0FL;
    _arg = _arg + (_arg >> 8);

    return (uint8_t)(_arg + (_arg >> 16)) & 0x3F;
}

По-моему, идея изложена в книге: Генри Уоррен, Алгоритмические трюки для программистов.... Хотя могу соврать.

Здравствуйте, Аноним, Вы писали:

А>для 8-ми бит нужна таблица 256 элементов получается!!!!

Кошмар!

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, Аноним, Вы писали:

А>>для 8-ми бит нужна таблица 256 элементов получается!!!!

N>Кошмар!

А как правильно?

Здравствуйте, Аноним, Вы писали:

А>Подскажите пожалуйста каким самым быстрым способом сделать подсчет единичных бит в значении типа unsigned int;

А>Сразу что приходит в голову цикл 32итерации и суммировать единичные биты... как еще можно чтобы не делать 32 итерации?

Я обычно пишу так:

int ones(unsigned int i)
{
  int j = 0;
  while (i)
  {
     i &= i-1;
     ++j;
  }
  return j;  
}

Здравствуйте, Аноним, Вы писали:

А>Подскажите пожалуйста каким самым быстрым способом сделать подсчет единичных бит в значении типа unsigned int;

А>Сразу что приходит в голову цикл 32итерации и суммировать единичные биты... как еще можно чтобы не делать 32 итерации?

Есть много способов.
* Прямой -- в твоей реализации (требует, видимо, 64 операции, или даже 96),
* Алгоритм Кернигана -- то, что предложил Дейл (он требует в среднем 16 операций, хотя если у тебя числа в ограниченном диапазоне, то гораздо меньше)
* "Параллельный" алгоритм -- то, что предложил Vlad_SP (он требует фиксированное число операций немного меньше 16, т.е. предыдущий метод может быть лучше или хуже), идея его предельно проста. Биты подсчитываются сначала парами, потом четверками и т.д. Там только первую операцию a = (a & 0x55555555) + ((a >> 1) & 0x55555555); можно заменить на a -= (a >> 1) & 0x55555555;

* А есть еще такой метод. Если у тебя используется меньше битов, чем все в числе, то можно число скопировать несколько раз, а затем считать биты в разных копиях одновременно.
Идея его такая. Допустим, что у тебя есть k-битное число. Сделаем несколько его копий. Для этого достаточно умножить число на 0x10..010..01...0..01. Теперь возьмем каждый m-й бит этого числа, причем так, чтобы каждый бит изначального значения остался ровно в одной копии. Теперь, у нас единичными могут быть только биты 0,m,2m,..., причем число единичных битов такое же, как и в изначальном числе, хотя они могут теперь оказаться в другом порядке. Возьмем теперь остаток от деления на 2^m-1. Если у нас стоит единица на позиции pm, то значение этого бита в числе 2^(pm) и остаток от деления на 2^m-1 будет 2^(pm)=2^m^p-1^p+1=(2^m-1)(...)+1, т.е. остаток будет 1, а остаток от деления всего числа будет равен количеству единичных битов.
У этого алгоритма есть два ограничения:
— во-первых, m не должно быть маленьким, чтобы в конце получилось количество битов, а не количество битов по модулю 2^m-1, т.е. максимальное количество возможных установленных битов должно быть меньше 2^m-1: k<2^m-1;
— во-вторых, число копий должно быть достаточным для того, чтобы каждый бит получил свое место в одной из копий, когда мы берем каждый m-й бит. Число копий должно быть равно m, но последняя старшая копия может быть неполной, там надо только k-m+1 бит. Т.е. всего (k-1)m+1<=максимальная разрядность или (k-1)m<разрядность.

P.S. Кстати, насколько я помню, я видел для 64-битной арифметики подсчет максимум для 12-битных чисел, т.е. k=12. Давайте прикинем, сколько бит максимум можно обработать таким методом с помощью 64-битной арифметики (64-битное умножение и деление поддерживается даже на 32-битных машинах, насколько я помню, т.к. там результат произведения и делимое можно поместить в двух регистрах). С одной стороны, k<2^m-1, с другой стороны, (k-1)m<64. Т.е. (k-1)log2(k+1)<64, (k+1)^(k-1)<2^64, k<=16. Если k=16, то m=5, но тогда 5 копий не влезут. Если k=15, m=7 (взаимнопростое). Если k=14, то m=5, надо 13*5+1=66 бит. k=13, m=4, по идее, должно работать:

// 13 bits
count =  (a * 0x8004002001 & 0x1111111111111) % 15; // 64-bit arithmetic

Кстати, если для k=15 взять m=4 (взаимнопростое), то разрядности хватит, единственная проблема, это то, что, если ВСЕ биты установлены, то число битов = 15, остаток от деления на 2^m-1=15 даст 0 вместо 15. Т.е. можно даже исхитриться для 15 бит с одной единственной поправкой:

// 15 bits
count = a == 32767 ? 15 : (a * 0x200040008001 & 0x111111111111111) % 15; // 64-bit arithmetic

Кто-нибудь, у кого компилятор под рукой, может проверить, что это все работает (там всего перебор 2^15=32768 чисел)?

Здравствуйте, Аноним, Вы писали:

int count1(int t)
{
    __asm {
        mov edx,t
        mov eax, 0
cycle : bsf ecx, edx
        jz finish
        inc eax
        inc ecx
        shr edx, cl
        jmp cycle
finish:
    }
}

Быстрее, чем у Vlad_SP — не будет. Цикл все же, хоть и не 32 раза.

Здравствуйте, vadimcher, Вы писали:

V>Кто-нибудь, у кого компилятор под рукой, может проверить, что это все работает (там всего перебор 2^15=32768 чисел)?

>>> def c0(x):
    n = 0
    while x :
        n += x & 1
        x >>= 1
    return n

>>> def c(x):
    return (x * 0x200040008001 & 0x111111111111111) % 15 if x != 32767 else 15

>>> r=range(32768)
>>> map(c, r) == map(c0, r)
True

Работает. Но, на мой взгляд, предложенный Vlad_SP вариант должен быть быстрее практически на любом процессоре -- особенно на менее чем 64-разрядных. Однако, идея интересная

Здравствуйте, quodum, Вы писали:

Q>Здравствуйте, vadimcher, Вы писали:

V>>Кто-нибудь, у кого компилятор под рукой, может проверить, что это все работает (там всего перебор 2^15=32768 чисел)?

Q>

>>>> def c0(x):
Q>    n = 0
Q>    while x :
Q>        n += x & 1
Q>        x >>= 1
Q>    return n

>>>> def c(x):
Q>    return (x * 0x200040008001 & 0x111111111111111) % 15 if x != 32767 else 15

>>>> r=range(32768)
>>>> map(c, r) == map(c0, r)
Q>True
Q>

Q>Работает. Но, на мой взгляд, предложенный Vlad_SP вариант должен быть быстрее практически на любом процессоре -- особенно на менее чем 64-разрядных. Однако, идея интересная

Способ с подсчетом битов a &= a — 1; хорош тем, что он не зависит от разрядности, т.е. он "автонастраиваемый" -- если реально используется меньше битов или если количество установленных битов обычно мало, то он может, видимо, работать быстрее. Для него проще написать единую шаблонную реализацию. "Параллельный" хорош тем, что он самый быстрый в среднем, я бы предпочел его. Ну а последний способ просто интересный, математическая попытка уменьшить число операций, хотя понятно, что заменяя 12 сложений и сдвигов на умножение и деление мы только проигрываем. Его можно использовать, чтобы запутать врагов, особенно красиво выглядит, если m<>4.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, Аноним, Вы писали:


PD>

PD>int count1(int t)
PD>{
PD>    __asm {
PD>        mov edx,t
PD>        mov eax, 0
PD>cycle : bsf ecx, edx
PD>        jz finish
PD>        inc eax
PD>        inc ecx
PD>        shr edx, cl
PD>        jmp cycle
PD>finish:
PD>    }
PD>}

PD>

PD>Быстрее, чем у Vlad_SP — не будет. Цикл все же, хоть и не 32 раза.

Фу, неспортивно. Какой же тут алгоритм ? Не более чем заточка под определённый процессор/семейство. Тогда уж POPCNT надо использовать.

Кстати, Уоррен утверждает:

На компьютере IBM Stretch (выпущенном в 1960 году) имелась возможность под-
счета количества единичных битов в слове и количества ведущих нулевых битов слова
(причем эти величины являлись побочным результатом выполнения любой логической
операции!). Функция подсчета количества единичных битов иногда носила название сте-
пени заполнения (population count), например на машинах Stretch или SPARCv9.

1960 год! А у x86 это появилось только в SSE4a (LZCNT/POPCNT), и то не нахаляву

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, Аноним, Вы писали:


PD>

PD>int count1(int t)
PD>{
PD>    __asm {
PD>        mov edx,t
PD>        mov eax, 0
PD>cycle : bsf ecx, edx
PD>        jz finish
PD>        inc eax
PD>        inc ecx
PD>        shr edx, cl
PD>        jmp cycle
PD>finish:
PD>    }
PD>}

PD>

PD>Быстрее, чем у Vlad_SP — не будет. Цикл все же, хоть и не 32 раза.

Кстати, код содержит баг!!! Поведение bsf в случае нулевого операнда неопределено. Цитата из интеловского мануала:

If the contents source operand are 0, the contents of the destination operand is undefined.

Здравствуйте, IID, Вы писали:

IID>Здравствуйте, Pavel Dvorkin, Вы писали:

IID>Кстати, код содержит баг!!! Поведение bsf в случае нулевого операнда неопределено. Цитата из интеловского мануала:
IID>

IID>If the contents source operand are 0, the contents of the destination operand is undefined.

Да, ты прав. Но исправить недолго.

V>* Алгоритм Кернигана -- то, что предложил Дейл (он требует в среднем 16 операций, хотя если у тебя числа в ограниченном диапазоне, то гораздо меньше)

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

Здравствуйте, Аноним, Вы писали:

А>Подскажите пожалуйста каким самым быстрым способом сделать подсчет единичных бит в значении типа unsigned int;
А>Сразу что приходит в голову цикл 32итерации и суммировать единичные биты... как еще можно чтобы не делать 32 итерации?

Задачки из тестов на должность программиста требуется решать самостоятельно

Здравствуйте, K13, Вы писали:


V>>* Алгоритм Кернигана -- то, что предложил Дейл (он требует в среднем 16 операций, хотя если у тебя числа в ограниченном диапазоне, то гораздо меньше)

K13>Думаю, тут ошибка.
K13>Поскольку вероятность 1 в старшем (младшем) разряде одна вторая, то неважно, идем мы от младшего разряда к старшему или наоборот, при полном диапазоне целых чисел у нас в половине случаев понадобится по операции на разряд целого (а не "половина разрядности в среднем").

Цикл повторяется пока число ненулевое, т.е. пока в нем есть хотя бы одна единица. За каждый проход цикла одна единица (самая младшая) пропадает. Количество единиц в среднем 16 (для каждого значения возьмем инвертированное, если в одном единиц k, то в другом 32-k, в среднем ровно 16). Но правильно было бы сказать, конечно, что количество итераций, а не операций, равно в среднем 16.

Здравствуйте, Аноним, Вы писали:

А>Подскажите пожалуйста каким самым быстрым способом сделать подсчет единичных бит в значении типа unsigned int;

Counting bits set
Hamming weight, Efficient implementation
Population Count (Ones Count)