В этой книге слову “хакер” возвращено его первозданное значение — человека увлеченного, талантливого программиста, способного к созданию чрезвычайно эффективного и элегантного кода. В книге воплощен сорокалетний стаж ее автора в области разработки компиляторов и архитектуры компьютеров. Здесь вы найдете множество приемов для работы с отдельными битами, байтами, вычисления различных целочисленных функций; большей части материала сопутствует строгое математическое обоснование. Каким бы не был ваш профессионализм — вы обязательно найдете в этой книге новое для себя; кроме того, книга заставит вас посмотреть на уже знакомые вещи с новой стороны. Не в меньшей степени эта книга пригодится и начинающему программисту, который может просто воспользоваться готовыми советами из книги, применяя их в своей повседневной практике.
Время выполнения.
Предполагается, что все команды выполняются за один такт процессора, за исключением команд умножения, деления и получения остатка от деления, для которых невозможно точно определить время выполнения. Команды перехода занимают один такт, независимо от того, был выполнен переход или нет.
Команда загрузки непосредственного значения выполняется за один или два такта, в зависимости от того, сколько элементарных арифметических команд требуется для формирования константы в регистре.
Команды загрузки и сохранения не часто упоминаются в данной книге, но будем считать, что они выполняются за один такт, пренебрегая при этом задержкой при загрузке (промежутком времени между моментом завершения команды в арифметическом модуле и моментом, когда данные становятся доступны следующей команде).
ОГЛАВЛЕНИЕ.
Предисловие.
Вступление.
Благодарности.
ГЛАВА 1. Введение.
1.1. Система обозначений.
1.2. Система команд и модель оценки времени выполнения команд.
ГЛАВА 2. Основы.
2.1. Манипуляции с младшими битами.
2.2. Сложение и логические операции.
2.3. Неравенства с логическими и арифметическими выражениями.
2.4. Абсолютное значение.
2.5. Распространение знака.
2.6. Знаковый сдвиг вправо на основе беззнакового сдвига.
2.7. Функция sign.
2.8. Трехзначная функция сравнения.
2.9. Перенос знака.
2.10. Декодирование поля “0 означает 2**n”.
2.11. Предикаты сравнения.
2.12. Обнаружение переполнения.
2.13. Флаги условий после сложения, вычитания и умножения.
2.14. Циклический сдвиг.
2.15. Сложение вычитание двойных слов.
2.16. Сдвиг двойного слова.
2.17. Сложение, вычитание и абсолютное значение многобайтовых величин.
2.18. Функции Doz, Max, Min.
2.19. Обмен содержимого регистров.
2.20. Выбор среди двух или большего количества значений.
ГЛАВА 3. Округление к степени 2.
3.1. Округление к кратному степени 2.
3.2. Округление к ближайшей степени 2.
3.3. Проверка пересечения границы степени 2.
ГЛАВА 4. Арифметические границы.
4.1. Проверка границ целых чисел.
4.2. Определение границ суммы и разности.
4.3. Определение границ логических выражений.
ГЛАВА 5. Подсчет битов.
5.1. Подсчет единичных битов.
5.2. Четность.
5.3. Подсчет ведущих нулевых битов.
5.4. Подсчет завершающих нулевых битов.
ГЛАВА 6. Поиск в слове.
6.1. Поиск первого нулевого байта.
6.2. Поиск строки единичных битов заданной длины.
ГЛАВА 7. Перестановка битов и байтов.
7.1. Реверс битов и байтов.
7.2. Перемешивание битов.
7.3. Транспонирование битовой матрицы.
7.4. Сжатие, или обобщенное извлечение.
7.5. Обобщенные перестановки.
7.6. Перегруппировки и преобразования индексов.
ГЛАВА 8. Умножение.
8.1. Умножение больших чисел.
8.2. Старшее слово 64-битового умножения.
8.3. Преобразование знакового и беззнакового произведений.
8.4. Умножение на константу.
ГЛАВА 9. Целочисленное деление.
9.1. Предварительные сведения.
9.2. Деление больших чисел.
9.3. Беззнаковое короткое деление на основе знакового.
9.4. Беззнаковое длинное деление.
ГЛАВА 10. Целое деление на константы.
10.1. Знаковое деление на известную степень 2.
10.2. Знаковый остаток от деления на степень 2.
10.3. Знаковое деление и вычисление остатка для других случаев.
10.4. Знаковое деление на делитель, не меньший 2.
10.5. Знаковое деление на делитель, не превышающий -2.
10.6. Встраивание в компилятор.
10.7. Дополнительные вопросы.
10.8. Беззнаковое деление.
10.9. Беззнаковое деление на делитель, не меньший 1.
10.10. Встраивание в компилятор при беззнаковом делении.
10.11. Дополнительные вопросы (беззнаковое деление).
10.12. Применение к модульному делению и делению с округлением к меньшему значению.
10.13. Другие похожие методы.
10.14. Некоторые магические числа.
10.15. Точное деление на константу.
10.16. Проверка нулевого остатка при делении на константу.
ГЛАВА 11. Некоторые элементарные функции.
11.1. Целочисленный квадратный корень.
11.2. Целочисленный кубический корень.
11.3. Целочисленное возведение в степень.
11.4. Целочисленный логарифм.
ГЛАВА 12. Системы счисления с необычными основаниями.
12.1. Основание -2.
12.2. Основание -1+i.
12.3. Другие системы счисления.
12.4. Какое основание наиболее эффективно.
ГЛАВА 13. Кол Грея.
13.1. Построение кода Грея.
13.2. Увеличение чисел кода Грея.
13.3. Отрицательно-двоичный код Грея.
13.4. Краткая история и применение.
ГЛАВА 14. Кривая Гильберта.
14.1. Рекурсивный алгоритм построения кривой Гильберта.
14.2. Преобразование расстояния вдоль кривой Гильберта в координаты.
14.3. Преобразование координат в расстояние вдоль кривой Гильберта.
14.4. Увеличение координат кривой Гильберта.
14.5. Нерекурсивный алгоритм генерации кривой Гильберта.
14.6. Другие кривые, заполняющие пространство.
14.7. Применение.
ГЛАВА 15. Числа с плавающей точкой.
15.1. Формат IEEE.
15.2. Сравнение чисел с плавающей точкой с использованием целых операций.
15.3. Распределение ведущих цифр.
15.4. Таблица различных значений.
ГЛАВА 16. Формулы для простых чисел.
16.1. Введение.
16.2. Формулы Вилланса.
16.3. Формула Вормелла.
16.4. Формулы для других сложных функций.
ПРИЛОЖЕНИЕ А. Арифметические таблицы для 4-битовой машины.
ПРИЛОЖЕНИЕ Б. Метод Ньютона.
Источники информации.
Предметный указатель.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Алгоритмические трюки для программистов, Уоррен Г., 2007 - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги
Скачать - pdf - Яндекс.Диск.
Дата публикации:
Теги: учебник по программированию :: программирование :: Уоррен
Смотрите также учебники, книги и учебные материалы:
Предыдущие статьи:
