Как посчитать единицы в байте?

Alexei70

На любом языке. Главное - минимум операции процессора.
Уже голову сломал думать. Только дубовые решение в голову приходят. Знаю только, что существует некое короткое решение, использующее возможности, входящие в любой язык программирования.

vall

http://www.google.com/search?q=bit+hacks

ryshiy28

На входе: al - проверяемый байт
На выходе: ah - число единичных бит в байте



                      mov ecx,8

                       xor ah,ah

                       setnc

@@startloop: shr al,1

                       jnc @@contloop

                       inc ah

@@contloop:  dec ecx

                       jnz @@startloop

vall

бред, для байта даже табличка будет существенно быстрее.

amkharchenko

Как правильно мне тут подсказывают, все это --- сплошные выебоны. Правильный вариант: табличка значений.

ryshiy28

Согласен, табличкой быстрее.
А табличку будешь вручную строить?

vall

может всё-таки сходишь по ссылке?
const unsigned char BitsSetTable256[] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

Alexei70

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

vall

хуже — условные переходы это всегда не очень хорошо.
если раскрутить цикл то будет возможно лучше,
но всё можно сделать за 3 операции, без условных переходов и таблиц.

Ober

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

думаешь? — проверь!

Alexei70

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

poi1981

делишь исходное слово на двуразрядные поля и в каждое поле помещаешь количество имевшихся в нём единичных битов, затем значения в соседних двуразрядных полях складываются и результаты помещаются в четырёхразрядное поле и т.д. выполнение подзадач на каждом уровне можно делать параллельно. итого для 32-битового слова - 5 шагов.
есть ещё мелкие улучшения, подробно написано в Уоррене, алгоритмические трюки для программистов

vall

почитай внимательно, там есть и вычисление за 3 операции * & %

maggi14

Г.Уоррен, Алгоритмические трюки для программистов

Оставить комментарий