Алгоритмические трюки для программистов. 2-е изд

Автор: Уоррен Г.С., «Алгоритмические трюки для программистов. 2-е изд»: Перед вами сборник программных приемов, которые я собирал много лет. Большинство из них работают только на компьютерах, на которых целые числа представлены в дополнительном до 2 коде. Хотя в данной книге речь идет о 32-разрядных машинах с соответствующей длиной регистра, большую часть представленных здесь алгоритмов легко перенести на машины с регистрами других размеров. В этой книге не рассматриваются сложные вопросы наподобие методов сортировки или оптимизации компилируемого кода. Основное внимание здесь уделяется приемам работы с отдельными машинными словами или командами, например подсчету количества единичных битов в заданном слове. В подобных приемах часто используется смесь арифметических и логических команд. Предполагается, что прерывания, связанные с переполнением целых чисел, замаскированы и произойти не могут. Программы на С, Fortran и даже Java работают именно в таком окружении, но программистам на Pascal и ADA следует быть осторожными! Представление материала в книге — неформальное. Доказательства приводятся только в том случае, если алгоритм неочевиден, а иногда не приводятся вообще. Все методы используют компьютерную арифметику, функции типа "пол", комбинации арифметических и логических операций и тому подобные средства, а доказательства теорем в этой предметной области часто сложны и громоздки. Чтобы свести к минимуму количество типографских ошибок и опечаток, многие алгоритмы реализованы на языке программирования высокого уровня, в качестве которого используется С. Это обусловлено его распространенностью и тем, что он позволяет непосредственно комбинировать операции с целыми числами и битовыми строками; кроме того, компиляторы языка С генерируют объектный код высокого качества. Ряд алгоритмов написан на машинном языке. В книге применяется трехадресный формат команд, главным образом для повышения удобочитаемости. Использован язык ассемблера для некой абстрактной машины, которая является представителем современных RISC-компьютеров.