Наверх

Генри Уоррен, 2003 (Rus)
Алгоритмические трюки для программистов

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


СОДЕРЖАНИЕ
Предисловие
Вступление
Благодарности

ГЛАВА 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. Декодирование поля "О означает 2**п"
   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-битовой машины
Метод Ньютона


ИСТОЧНИКИ ИНФОРМАЦИИ
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ