Алгоритмы и программы

  • Быстрый алгоритм подсчета единиц

    Исходные данные:
    r0, r1, r2, r3 - байты регистра, в которых надо подсчитать количество единиц.
    Последовательность действий:
    1. По маске 10101010 выделяются разряды из регистра r0 и сдвигаются на один разряд вправо.
    2. По маске 01010101 выделяются разряды из этого же регистра.
    3. Далее они складываются. После этого в разрядах 0 - 1, 2 - 3, 4 - 5, 6 - 7 регистра r0 лежат суммы единиц из этих разрядов.
    4. По маске 11001100 выделяются разряды из регистра r0 и сдвигаются на два разряда вправо.
    5. По маске 00110011 выделяются разряды из этого же регистра.
    6. Далее они складываются. После этого в разрядах 0 - 3, 4 - 7 регистра r0 лежат суммы единиц из этих разрядов.
    7. По маске 11110000 выделяются разряды из регистра r0 и сдвигаются на четыре разряда вправо.
    8. По маске 00001111 выделяются разряды из этого же регистра.
    9. Далее они складываются. После этого в разрядах 0-7 регистра r0 лежит сумма единиц всех разрядов.
    Такая операция выполняется для всех остальных регистров.
    Количество строк в программе увеличивается, но время выполнения программы уменьшается в разы по сравнению с использованием циклов.