Количество единиц в байте

[OKTA]

Товарищи, есть задача посчитать количество 1-ц в последовательности. В итоге все сводится к подсчету единиц в каждом отдельном байте. Так вот вопрос, как будет быстрее? Побитовым сдвигом или логическим И, используя шабоны байт с единицей в разных местах?

[alex312]

Я думаю, самый быстрый способ - это табличный. Когда позиция в массиве будет хранить количество единиц в байте, соответствующем позиции.

[OKTA]

Я думаю, самый быстрый способ - это табличный. Когда позиция в массиве будет хранить количество единиц в байте, соответствующем позиции.

Не очень понял))

[Bepec]

Я думаю битовым будет быстрее. Хотя тут уже в реализацию надо смотреть.

[Old]

Думаю, быстрее табличного не найти.

[OKTA]

Спасибо за ответы! Попробую так и так для эксперимента

[Vamireh]

int a[255] = {n0, n2, n3.... n254}, где nX - количество единиц в числе X.

for (byte : all)
sum += a[byte]

быстрее вряд ли что-то будет

[Old]

int a[255] = {n0, n2, n3.... n254}, где nX - количество единиц в числе X.

Таблица должна быть длиной 256 байт: от 0 до 255.

[OKTA]

Да, этот метод гораздо быстрее работает! На 50 КБ данных как минимум в 4 раза быстрее!
Спасибо!

[kamre]

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

[Vamireh]

int a[255] = {n0, n2, n3.... n254}, где nX - количество единиц в числе X.

Таблица должна быть длиной 256 байт: от 0 до 255.

Да-да. Давайте не будем к цифрам придираться? Все всё поняли.

[Vamireh]

Хотя может будет быстрее, если по два байта, например проверять:

Код:

*reinterpret_cast<short*>(&buffer[i])

Интерпретация указателей на этапе компиляции устанавливается, а итераций будет меньше. Естественно еще четное/нечетное
количество байт нужно учесть.

[Old]

Да-да. Давайте не будем к цифрам придираться? Все всё поняли.

Ну вообще то, все всё поняли после первого же ответа в теме.
А если вы решили "разжевать" с примерами, то это не плохо делать без ошибок.

[OKTA]

Дальнейшее ускорение уже не столь важно в моей задачке, но с шортами попробую ради интереса. 

[Igors]

Хороший пример premature optimisation - оптимизации того что узким местом не будет. Ну так, из любви к искусству