В этой книге слову "хакер" возвращено его первозданное значение — человека увлеченного, талантливого программиста, способного к созданию чрезвычайно эффективного н элегантного кода. В книге воплощен сорокалетний стаж ее автора в области разработки компиляторов и архитектуры компьютеров. Здесь вы найдете множество приемов для работы с отдельными битами, бантами, вычисления различных целочисленных функций; большей части материала сопутствует строгое математическое обоснование. Каким бы не был ваш профессионализм — вы обязательно найдете в этой книге новое для себя; кроме того, книга заставит вас посмотреть на уже знакомые вещи с новой стороны. Не в меньшей степени эта книга пригодится и начинающему программисту, который может просто воспользоваться готовыми советами из книги, применяя их в своей повседневной практике.

Главная тема книги — рассмотреть базовые структурные отношения среди целых чисел и битовых строк и эффективные приемы реализации операций над ними. Рассмотренные в книге методы столь же полезны и практичны при программировании на языках высокого уровня, например С или Java, как и на языке ассемблера. Большинство из програьмных приемов, приведенных в книге, работают только на компьютерах, в которых целые числа представлены в дополнительном коде. Хотя в данной книге речь идет о 32-битовых машинах с соответствующей длиной регистра, большую часть представленных здесь алгоритмов легко перенести на машины с другими размерами регистров.

В этой книге не рассматриваются сложные вопросы наподобие методов сортировки или оптимизации компилируемого кода. Основное внимание уделено приемам работы с отдельными машинными словами или командами, например подсчету количества единичных битов в заданном слове. В подобных приемах часто используется смесь арифметических и логических команд. Предполагается, что прерывания, связанные с переполнением целых чисел, замаскированы и произойти не могут. Программы на С, Fortran и даже Java работают в таком окружении, но программистам на Pascal и ADA следует быть осторожными! Представление материала в книге неформальное. Доказательства приводятся только в том случае, если алгоритм неочевиден, а иногда не приводятся вообще. Все методы используют компьютерную арифметику, базовые функции, комбинации арифметических и логических операций и др., а доказательства теорем в этой предметной области часто сложны и громоздки. Чтобы свести к минимуму количество типографских ошибок и опечаток, многие алгоритмы реализованы на языке программирования высокого уровня, в качестве которого используется С. Это обусловлено его распространенностью и тем, что он позволяет непосредственно комбинировать операции с целыми числами и битовыми строками; кроме того, компилятор языка С генерирует объектный код высокого качества.

Ряд алгоритмов написан на машинном языке. В книге применяется трехадресный формат команд, главным образом для повышения удобочитаемости. Использован язык ассемблера для некой абстрактной машины, которая является представителем современных RISC-компьютеров. Отсутствие ветвлений в программе всячески приветствуется. Это связано с тем, что на многих машинах наличие ветвлений замедляет выборку команд и блокирует их параллельное выполнение. Кроме того, наличие ветвлений может препятствовать выполнению оптимизации компилятором. Оптимизирующий компилятор более эффективно работает с несколькими большими блоками кода, чем с множеством небольших. Крайне желательно использовать малые величины при непосредственном задании операнда, сравнение с 0 (а не с другими числами) и параллелизм на уровне команд

Заказать книгу Алгоритмические трюки для программистов

Скачать книгу Алгоритмические трюки для программистов