Новая книга была добавлена в корзину

Книга "Алгоритмические трюки для программистов" 2-е издание (Hacker's Delight-2) позволит повысить квалификацию профессиональному программисту, но при этом книга будет понятна и чрезвычайно полезна даже начинающему и даже студенту, тем более что в новом издании появилась масса упражнений, интересных как с теоретической, так и с практической точки зрений. Работа программиста всегда немного хакерство, а также смесь арифметики и логики, особенно это касается программиста, который создает элегантный и эффективно работающий код. В этой книге программист-ветеран IBM Генри Уоррен делится с читателями разнообразными приемами из своей коллекции, пополняемой в течение многих десятилетий работы в области разработки компиляторов и архитектуры компьютеров, прикладного и системного программирования. Большинство из них носят практический характер, хотя некоторые представляют в первую очередь теоретический интерес.

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

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

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

Добавления во 2-е издание книги "Алгоритмические трюки для программистов" включают:

- Новую главу, посвященную циклическому избыточному коду (CRC), включая широко используемый код CRC-32.
- Новую главу о кодах с коррекцией ошибок (ECC), включая подпрограммы для работы с кодом Хэмминга.
- Большее количество материала, посвященного делению на константы, включая методы, использующие только сдвиги и сложения.
- Вычисление остатков от деления без вычисления частного.
- Более подробное изложение методов подсчета количества единичных битов и ведущих нулевых битов.
- Подсчет единичных битов в массивах.
- Новые алгоритмы сжатия и расширения.
- Алгоритм LRU.
- Преобразования между числами с плавающей точкой и целыми числами.
- Программу приближенного вычисления обратного к квадратному корню.
- Галерею графиков дискретных функций.
- Появившиеся во втором издании упражнения и ответы к ним.

Об авторе книги "Алгоритмические трюки для программистов":
Генри Уоррен, мл. имеет пятидесятилетний стаж работы в IBM, его деятельность простирается от IBM 704 до PowerPC и далее. Он работал над рядом военных командно-управляющих систем и над проектом SETL под руководством Джека Шварца (Jack Schwartz) из университета Нью-Йорка. С 1973 года Уоррен занимается компиляторами и архитектурой компьютеров в исследовательском подразделении IBM. В настоящее время он работает над проектами суперкомпьютеров, которые должны достичь быстродействия, измеряемого эксафлопсами (EFLOPS). Генри Уоррен получил докторскую степень в области информационных технологий в университете Нью-Йорка.

"Это первая книга, в которой так глубоко раскрыты секреты компьютерной арифметики. В ней есть все известные мне трюки и множество ранее не известных. Эта книга - настоящая находка для разработчиков библиотек и компиляторов, для всех, кто обожает элегантность в программировании. Место этой книги на полке - рядом с книгами Кнута. Все десять лет, прошедших с выхода первого издания, книга была неоценимым помощником в моей работе в Sun и Google. Я просто дрожу от нетерпения познакомиться с новым материалом во втором издании."
Джошуа Блох (Joshua Bloch)

"Впервые увидев эту книгу, я решил, что это не то советы по взлому компьютеров, не то набор мелких программистских трюков. И только познакомившись с ней поближе, я понял, что под ее обложкой скрыта целая компьютерная энциклопедия. Второе издание охватывает две большие новые темы, и расширяет коллекцию десятками новых небольших трюков, включая те, которые я тут же применил на практике - например, вычисление среднего двух целых чисел без риска переполнения. Этот хакер действительно умеет принести удовольствие читателю!"
Гай Стил (Guy Steele)




СОДЕРЖАНИЕ книги Генри Уоррен "Алгоритмические трюки для программистов"





Предисловие 14
Введение 16
Благодарности 17
ГЛАВА 1. ВВЕДЕНИЕ 19
1.1. Система обозначений 19
1.2. Система команд и модель оценки времени выполнения команд 23
Время выполнения 28
Упражнения 30
ГЛАВА 2. ОСНОВЫ 31
2.1. Манипуляции младшими битами 31
Расширенные законы де Моргана 33
Проверка выполнимости справа налево 33
Новое применение 35
2.2. Сложение и логические операции 36
2.3. Неравенства с логическими и арифметическими выражениями 38
2.4. Абсолютное значение 39
2.5. Среднее двух целых 39
2.6. Распространение знака 40
2.7. Знаковый сдвиг вправо на основе беззнакового сдвига 40
2.8. Функция sign 41
2.9. Трехзначная функция сравнения 42
2.10. Перенос знака 42
2.11. Декодирование поля "0 означает 2**n" 43
2.12. Предикаты сравнения 43
Команды сравнения и бит переноса 47
Вычисление отношений 48
2.13. Обнаружение переполнения 49
Знаковое сложение и вычитание 49
Установка переполнения при знаковом сложении и вычитании 51
Беззнаковое сложение/вычитание 52
Умножение 53
Деление 55
2.14. Флаги условий после сложения, вычитания и умножения 58
2.15. Циклический сдвиг 59
2.16. Сложение/вычитание двойных слов 60
2.17. Сдвиг двойного слова 61
2.18. Сложение, вычитание и абсолютное значение многобайтовых величин 62
2.19. Функции doz, max, min 63
2.20. Обмен содержимого регистров 68
Обмен соответствующих полей регистров 68
Обмен двух полей одного регистра 69
Условный обмен 70
2.21. Выбор среди двух или более значений 70
2.22. Формула булева разложения 73
2.23. Реализация команд для всех 16 бинарных булевых операций 75
Исторические примечания 77
Упражнения 77
ГЛАВА 3. ОКРУГЛЕНИЕ К СТЕПЕНИ 2 81
3.1. Округление к кратному степени 2 81
3.2. Округление к ближайшей степени 2 82
Округление в меньшую сторону 83
Округление в большую сторону 84
3.3. Проверка пересечения границы степени 2 85
Упражнения 87
ГЛАВА 4. АРИФМЕТИЧЕСКИЕ ГРАНИЦЫ 89
4.1. Проверка границ целых чисел 89
4.2. Определение границ суммы и разности 92
Знаковые числа 94
4.3. Определение границ логических выражений 96
Знаковые границы 100
Упражнения 101
ГЛАВА 5. ПОДСЧЕТ БИТОВ 103
5.1. Подсчет единичных битов 103
Сумма и разность количества единичных битов в двух словах 110
Сравнение степени заполнения двух слов 111
Подсчет единичных битов в массиве 111
Применение 117
5.2. Четность 118
Вычисление четности слова 119
Добавление бита четности к 7-битовой величине 121
Применение 121
5.3. Подсчет ведущих нулевых битов 122
Методы с плавающей точкой 127
Сравнение количества ведущих нулевых битов двух слов 129
Связь с логарифмом 129
Применения 130
5.4. Подсчет завершающих нулевых битов 130
Применение 137
Упражнения 140
ГЛАВА 6. ПОИСК В СЛОВЕ 141
6.1. Поиск первого нулевого байта 141
Некоторые простые обобщения 145
Поиск значения из заданного диапазона 146
6.2. Поиск строки единичных битов заданной длины 147

6.3. Поиск наидлиннейшей строки единичных битов 150
6.4. Поиск кратчайшей строки единичных битов 152
Упражнения 153
ГЛАВА 7. ПЕРЕСТАНОВКА БИТОВ И БАЙТОВ 155
7.1. Реверс битов и байтов 155
Обобщенный реверс битов 160
Современные методы реверса битов 161
Увеличение обращенного целого числа 163
7.2. Перемешивание битов 165
7.3. Транспонирование битовой матрицы 167
Транспонирование битовой матрицы размером 32?32 171
7.4. Сжатие, или Обобщенное извлечение 176
Использование команд вставки и извлечения 181
Сжатие влево 182
7.5. Расширение, или Обобщенная вставка 182
7.6. Аппаратные алгоритмы сжатия и расширения 183
Сжатие 183
Расширение 185
7.7. Обобщенные перестановки 187
7.8. Перегруппировки и преобразования индексов 191
7.9. Алгоритм LRU 192
Упражнения 195
ГЛАВА 8. УМНОЖЕНИЕ 197
8.1. Умножение больших чисел 197
8.2. Старшее слово 64-битового произведения 200
8.3. Преобразование знакового и беззнакового
произведений одно в другое 200
Беззнаковое произведение из знакового 201
8.4. Умножение на константы 201
Упражнения 205
ГЛАВА 9. ЦЕЛОЧИСЛЕННОЕ ДЕЛЕНИЕ 207
9.1. Предварительные сведения 207
9.2. Деление больших чисел 210
Знаковое деление больших чисел 215
9.3. Беззнаковое короткое деление на основе знакового 215
Использование знакового длинного деления 215
Использование знакового короткого деления 216
9.4. Беззнаковое длинное деление 219
Аппаратный алгоритм сдвига и вычитания 219
Использование короткого деления 222
9.5. Деление двойных слов из длинного деления 224
Беззнаковое деление двойных слов 225
Знаковое деление двойных слов 228
Упражнения 229

ГЛАВА 10. ЦЕЛОЕ ДЕЛЕНИЕ НА КОНСТАНТЫ 231
10.1. Знаковое деление на известную степень 2 231
10.2. Знаковый остаток от деления на известную степень 2 232
10.3. Знаковое деление и вычисление остатка для других случаев 233
Деление на 3 233
Деление на 5 235
Деление на 7 235
10.4. Знаковое деление на делитель, не меньший 2 236
Алгоритм 238
Доказательство пригодности алгоритма 239
Доказательство корректности произведения 240
10.5. Знаковое деление на делитель, не превышающий -2 243
Для каких делителей m(-d) -m(d)? 245
10.6. Встраивание в компилятор 246
10.7. Дополнительные вопросы 249
Единственность 249
Делители с лучшими программами 250
10.8. Беззнаковое деление 253
Беззнаковое деление на 3 253
Беззнаковое деление на 7 254
10.9. Беззнаковое деление на делитель, не меньший 1 256
Беззнаковый алгоритм 257
Доказательство пригодности беззнакового алгоритма 257
Доказательство корректности произведения в случае беззнакового деления 258
10.10. Встраивание в компилятор при беззнаковом делении 258
10.11. Дополнительные вопросы (беззнаковое деление) 260
Делители с лучшими программами (беззнаковое деление) 260
Использование знакового деления вместо беззнакового и наоборот 261
Более простой беззнаковый алгоритм 262
10.12. Применение к модульному делению и делению
с округлением к меньшему значению 263
10.13. Другие похожие методы 263
10.14. Некоторые магические числа 265
10.15. Простой код на языке программирования Python 266
10.16. Точное деление на константу 266
Вычисление мультипликативного обратного по алгоритму Евклида 268
Вычисление мультипликативного обратного по методу Ньютона 271
Некоторые мультипликативные обратные 273
10.17. Проверка нулевого остатка при делении на константу 274
Беззнаковое деление 275
Знаковое деление, делитель ?2 276
10.18. Методы, не использующие команды умножения со старшим словом 278
Беззнаковое деление 278
Знаковое деление 286
10.19. Получение остатка суммированием цифр 288
Беззнаковый остаток 289
Знаковый остаток 293

10.20. Получение остатка путем умножения и сдвига вправо 295
Беззнаковый остаток 295
Знаковый остаток 299
10.21. Преобразование в точное деление 301
10.22. Проверка времени выполнения 302
10.23. Аппаратная схема для деления на 3 303
Упражнения 304
ГЛАВА 11. НЕКОТОРЫЕ ЭЛЕМЕНТАРНЫЕ ФУНКЦИИ 305
11.1. Целочисленный квадратный корень 305
Метод Ньютона 305
Бинарный поиск 309
Аппаратный алгоритм 310
11.2. Целочисленный кубический корень 313
11.3. Целочисленное возведение в степень 314
Вычисление xn бинарным разложением n 314
2n в Fortran 315
11.4. Целочисленный логарифм 316
Целочисленный логарифм по основанию 2 317
Целочисленный логарифм по основанию 10 317
Упражнения 323
ГЛАВА 12. СИСТЕМЫ СЧИСЛЕНИЯ С НЕОБЫЧНЫМИ ОСНОВАНИЯМИ 325
12.1. Основание -2 325
12.2. Основание -1+i 332
12.3. Другие системы счисления 335
12.4. Какое основание наиболее эффективно 335
Упражнения 336
ГЛАВА 13. КОД ГРЕЯ 337
13.1. Код Грея 337
13.2. Увеличение чисел кода Грея 339
13.3. Отрицательно-двоичный код Грея 341
13.4. Краткая история и применение 341
Упражнения 343
ГЛАВА 14. ЦИКЛИЧЕСКИЙ ИЗБЫТОЧНЫЙ КОД 345
14.1. Введение 345
Основы 345
14.1. Теория 347
14.3. Практика 349
Аппаратное обеспечение 351
Программная реализация 353
Упражнения 356
ГЛАВА 15. КОДЫ С КОРРЕКЦИЕЙ ОШИБОК 357
15.1. Введение 357
15.2. Код Хэмминга 358
Код SEC-DED 360

Минимально необходимое количество проверочных битов 362
Заключительные замечания 362
15.3. Программная реализация SEC-DED для 32 информационных битов 364
15.4. Общее рассмотрение задачи коррекции ошибок 369
Расстояние Хэмминга 370
Основная задача теории кодирования 372
Сферы 374
Упражнения 379
ГЛАВА 16. КРИВАЯ ГИЛЬБЕРТА 381
16.1. Рекурсивный алгоритм построения кривой Гильберта 383
16.2. Преобразование расстояния вдоль кривой Гильберта в координаты 385
16.3. Преобразование координат в расстояние вдоль кривой Гильберта 393
16.4. Увеличение координат кривой Гильберта 395
16.5. Нерекурсивный алгоритм генерации кривой Гильберта 398
16.6. Другие кривые, заполняющие пространство 398
16.7. Применения 399
Упражнения 400
ГЛАВА 17. ЧИСЛА С ПЛАВАЮЩЕЙ ТОЧКОЙ 401
17.1. Формат IEEE 401
17.2. Преобразование чисел с плавающей точкой в целые и обратно 404
17.3. Сравнение чисел с плавающей точкой с использованием целых операций 408
17.4. Программа приближенного вычисления обратного к квадратному корню 410
17.5. Распределение ведущих цифр 413
17.6. Таблица различных значений 415
Упражнения 417
ГЛАВА 18. ФОРМУЛЫ ДЛЯ ПРОСТЫХ ЧИСЕЛ 419
18.1. Введение 419
18.2. Формулы Вилланcа 421
Первая формула 421
Вторая формула 422
Третья формула 423
Четвертая формула 424
18.3. Формула Вормелла 424
18.4. Формулы для других сложных функций 425
Упражнения 431
ОТВЕТЫ К УПРАЖНЕНИЯМ 433
Глава 1. Введение 433
Глава 2. Основы 435
Глава 3. Округление к степени 2 444
Глава 4. Арифметические границы 444
Глава 5. Подсчет битов 445
Глава 6. Поиск в слове 446
Глава 7. Перестановка битов и байтов 451
Глава 8. Умножение 453

Глава 9. Целочисленное деление 456
Глава 10. Целое деление на константы 459
Глава 11. Некоторые элементарные функции 462
Глава 12. Системы счисления с необычными основаниями 464
Глава 13. Код Грея 468
Глава 14. Циклический избыточный код 470
Глава 15. Коды с коррекцией ошибок 470
Глава 16. Кривая Гильберта 475
Глава 17. Числа с плавающей точкой 475
Глава 18. Формулы для простых чисел 478
ПРИЛОЖЕНИЕ А. АРИФМЕТИЧЕСКИЕ ТАБЛИЦЫ ДЛЯ 4-БИТОВОЙ МАШИНЫ 483
ПРИЛОЖЕНИЕ Б. МЕТОД НЬЮТОНА 487
ПРИЛОЖЕНИЕ В. ГРАФИКИ ДИСКРЕТНЫХ ФУНКЦИЙ 489
В.1. Графики логических операций над целыми числами 489
В.2. Графики для сложения, вычитания и умножения 491
В.3. Графики функций, включающих деление 493
В.4. Графики функций сжатия, обобщенного упорядочения
и циклического сдвига влево 494
В.5. Графики некоторых унарных функций 496
СПИСОК ЛИТЕРАТУРЫ 501
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 506