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

Генри Уоррен, мл.

В этой книге слову «хакер» возвращено его первозданное значение - человека увлеченного, талантливого программиста, способного к созданию чрезвычайно эффективного и элегантного кода. В книге воплощен сорокалетний стаж ее автора в области разработки компиляторов и архитектуры компьютеров. Здесь вы найдете множество приемов для работы с отдельными битами, байтами, вычисления различных целочисленных функций. Большей части материала сопутствует строгое математическое обоснование.

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

Издательство: Вильямс, 2007 г.

ISBN 5-8459-0572-7, 0-201-91465-4

Количество страниц: 288.

Содержание книги «Алгоритмические трюки для программистов»:

10 Предисловие
12 Вступление
- 13 Благодарности
15 ГЛАВА 1. Введение
- 15 1.1. Система обозначений
- 18 1.2. Система команд н модель оценки времени выполнения команд
25 ГЛАВА 2. Основы
- 25 2.1. Манипуляции с младшими битами
- 28 2.2. Сложение и логические операции
- 30 2.3. Неравенства с логическими и арифметическими выражениями
- 31 2.4. Абсолютное значение
- 31 2.5. Распространение знака
- 32 2.6. Знаковый сдвиг вправо на основе беззнакового сдвига
- 32 2.7. Функция sign
- 33 2.8. Трехзначная функция сравнения
- 33 2.9. Перенос знака
- 34 2.10. Декодирование поля «0 означает 2**n»
- 34 2.11. Предикаты сравнения
- 39 2.12. Обнаружение переполнения
- 45 2.13. Флаги условий после сложения, вычитания и умножения
- 46 2.14. Циклический сдвиг
- 47 2.15. Сложение/вычитание двойных слов
- 47 2.16. Сдвиг двойного слова
- 48 2.17. Сложение, вычитание и абсолютное значение многобайтовых величин
- 50 2.18. Функции Doz, Max, Min
- 51 2.19. Обмен содержимого регистров
- 53 2.20. Выбор среди двух или большего количества значений
57 ГЛАВА 3. Округление к степени 2
- 57 3.1. Округление к кратному степени 2
- 58 3.2. Округление к ближайшей степени 2
- 60 3.3. Проверка пересечения границы степени 2
63 ГЛАВА 4. Арифметические границы
- 63 4.1. Проверка границ целых чисел
- 65 4.2. Определение границ суммы и разности
- 68 4.3. Определение границ логических выражений
75 ГЛАВА 5. Подсчет битов
- 75 5.1. Подсчет единичных битов
- 83 5.2. Четность
- 86 5.3. Подсчет ведущих нулевых битов
- 92 5.4. Подсчет завершающих нулевых битов
99 ГЛАВА 6. Поиск в слове
- 99 6.1. Поиск первого нулевого байта
- 104 6.2. Поиск строки единичных битов заданной длины
107 ГЛАВА 7. Перестановка битов н байтов
- 107 7.1. Реверс битов и бантов
- 111 7.2. Перемешивание битов
- 113 7.3. Транспонирование битовой матрицы
- 121 7.4. Сжатие, или обобщенное извлечение
- 126 7.5. Обобщенные перестановки
- 129 7.6. Перегруппировки и преобразовании индексов
131 ГЛАВА 8. Умножение
- 131 8.1. Умножение больших чисел
- 133 8.2. Старшее слово 64-битового умножения
- 134 8.3. Преобразование знакового и беззнакового произведений
- 135 8.4. Умножение на константу
139 ГЛАВА 9. Целочисленное деление
- 139 9.1. Предварительные сведения
- 142 9.2. Деление больших чисел
- 146 9.3. Беззнаковое короткое деление на основе знакового
- 149 9.4. Беззнаковое длинное деление
155 ГЛАВА 10. Целое деление на константы
- 155 10.1. Знаковое деление на известную степень 2
- 156 10.2. Знаковый остаток от делении на степень 2
- 157 10.3. Знаковое деление и вычисление остатка для других случаев
- 160 10.4. Знаковое деление на делитель, не меньший 2
- 166 10.5. Знаковое деление на делитель, не превышающий – 2
- 169 10.6. Встраивание в компилятор
- 171 10.7. Дополнительные вопросы
- 175 10.8. Беззнаковое деление
- 177 10.9. Беззнаковое деление на делитель, не меньший 1
- 180 10.10. Встраивание в компилятор при беззнаковом делении
- 181 10.11. Дополнительные вопросы (беззнаковое деление)
- 184 10.12. Применение к модульному делению и делению с округлением к меньшему значению
- 184 10.13. Другие похожие методы
- 186 10.14. Некоторые магические числа
- 186 10.15. Точное деление на константу
- 193 10.16. Проверка нулевого остатка при делении на константу
197 ГЛАВА 11. Некоторые элементарные функции
- 197 11.1. Целочисленный квадратный корень
- 204 11.2. Целочисленный кубический корень
- 205 11.3. Целочисленное возведение в степень
- 207 11.4. Целочисленный логарифм
215 ГЛАВА 12. Системы счисления с необычными основаниями
- 215 12.1. Основание -2
- 221 12.2. Основание -1+i
- 223 12.3. Другие системы счисления
- 224 12.4. Какое основание наиболее эффективно
227 ГЛАВА 13. Код Грея
- 227 13.1. Построение кода Грея
- 229 13.2. Увеличение чисел кода Грея
- 230 13.3. Отрицательно-двоичный код Грея
- 230 13.4. Краткая история и применение
233 ГЛАВА 14. Кривая Гильберта
- 235 14.1. Рекурсивный алгоритм построения кривой Гильберта
- 237 14.2. Преобразование расстояния вдоль кривой Гильберта в координаты
- 243 14.3. Преобразование координат в расстояние вдоль кривой Гильберта
- 245 14.4. Увеличение координат кривой Гильберта
- 248 14.5. Нерекурсивный алгоритм генерации кривой Гильберта
- 248 14.6. Другие кривые, заполняющие пространство
- 249 14.7. Применение
251 ГЛАВА 15. Числа с плавающей точкой
- 251 15.1. Формат IEEE
- 254 15.2. Сравнение чисел с плавающей точкой с использованием целых операций
- 255 15.3. Распределение ведущих цифр
- 257 15.4. Таблица различных значений
261 ГЛАВА 16. Формулы для простых чисел
- 261 16.1. Введение
- 263 16.2. Формулы Вилланса
- 266 16.3. Формула Вормелла
- 267 16.4. Формулы для других сложных функций
273 ПРИЛОЖЕНИЕ А. Арифметические таблицы для 4-битовой машины
277 ПРИЛОЖЕНИЕ Б. Метод Ньютона
279 Источники информации
283 Предметный указатель