Russian Qt Forum

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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