можно обойти, введя несколько дополнительных операций и используя таблицы меньшего размера. Мы зададим таблицу, содержащую число единичных битов для всех 8-битовых байтов, а потом ответим на вопрос о 32-разрядных словах, суммируя ответы на четыре вопроса о 8-разрядных словах. Таблица CountTable, содержащая число единичных битов, устанавливается в исходное состояние двумя циклами, которые по своему действию соответствуют следующим операторам присваивания (см. задачу 2).
CountTable[0] :- 0; CountTable[13 :- 1;
CountTableC2] := 1; CountTable[3] := 2;
■ ■ ■
CountTableC2543 := 7; CountTable[255] := 8;
Для подсчета битов во всех байтах слова W мы могли бы использовать четырехпроходный цикл, но так же просто и, вероятно, несколько эффективнее развернуть этот цикл:
WordCount ;= CountTable[ W and 11111111В]
+ CountTable[(W rshift 8) and 111U111B] + CountTable[(W rshift 16) and U111111B] + CountTableE(W rshift 24) and И111111В]
Программа выделяет байты посредством сдвига и последующей операции AND, которая устанавливает в нуль все биты, кроме восьми младших. Эта операция зависит от языка и типа ЭВМ. В то время как в исходном варианте решения требуется около 100 машинных команд, вышеприведенный подход обычно можно реализовать, используя около дюжины операторов. Нередко такое изменение приводит (опять) к ускорению времени выполнения программы на порядок. (Некоторые другие подходы к подсчету числа битов рассматриваются Рейнгоулдом, Нивергильтом и Део в разд. 1.1 книги "Комбинированные алгоритмы: теория и практика" (Reingold, Nievergelt, Deo. Combinatorial Algorithms: Theory and Practice), опубликованной издательством Prentice-Hall в 1977 г.)
Последняя проблема типична для прикладных задач, имеющих дело с географическими и геометрическими данными.
Задача 3 - вычисление расстояний на сфере. Первая часть входных данных - множество S из 5 тыс. точек на поверхности шара. Каждая точка представляется своей широтой и долготой. После того, как эт»
106
