Генри С. Уоррен - Алгоритмические трюки для программистов

Алгоритмические
трюки
для
программистов
ИСПРАВЛЕННОЕ ИЗДАНИЕ

Hacker's Delight
Henry S. Warren, Jr.

ADDISON-WESLEY
Boston * San Francisco * New York 4 Toronto 4 Montreal
London 4 Munich * Paris 4 Madrid
Capetown 4 Sydney 4 Tokyo * Singapore Ф Mexico City

Алгоритмические
трюки
для
программистов
ИСПРАВЛЕННОЕ ИЗДАНИЕ
Генри Уоррен, мл.

Издательский дом "Вильяме"
Москва * Санкт-Петербург * Киев
2004

ББК 32.973.26-018.2.75
У64
УДК 681.3.07

Издательский дом "Вильяме"
Зав. редакцией С.Н. Тригуб
Перевод с английского канд. техн наук И.В. Красикова, Г.И. Сингаевской
Под редакцией канд. техн наук И.В. Красикова
По общим вопросам обращайтесь в Издательский дом "Вильяме" по адресу:
info@williamspublishing.com, http://www.williamspublishing.com

Уоррен. Генри, С.
У64
Алгоритмические трюки для программистов, испр. изд. : Пер. с англ. — М.:
Издательский дом "Вильяме", 2004. — 288с. : ил. — Парал. тит. англ.
ISBN 5-8459-0572-9 (рус.)
В этой книге слову "хакер" возвращено его первозданное значение — человека
увлеченного, талантливого программиста, способного к созданию чрезвычайно эффективного и элегантного кода. В книге воплощен сорокалетний стаж ее автора в области разработки компиляторов и архитектуры компьютеров. Здесь вы найдете множество приемов для
работы с отдельными битами, байтами, вычисления различных целочисленных функций;
большей части материала сопутствует строгое математическое обоснование. Каким бы ни
был ваш уровень профессиональной подготовки — вы обязательно найдете в этой книге
новое для себя; кроме того, книга заставит вас посмотреть на уже знакомые вещи с новой
стороны. Не в меньшей степени эта книга пригодится и начинающему программисту,
который может просто воспользоваться готовыми советами из книги, применяя их в своей
повседневной практике.
ББК 32.973.26-018.2.75
Все названия программных продуктов являются зарегистрированными торговыми марками
соответствующих фирм.
Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни было
форме и какими бы то ни было средствами, будь то электронные или механические, включая
фотокопирование и запись на магнитный носитель, если на это нет письменного разрешения издательства
Addison-Wesley Publishing Company, Inc.
Authorized translation from the English language edition published by Addison-Wesley Publishing Company, Inc,
Copyright © 2002
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic
or mechanical, including photocopying, recording or by any information storage retrieval system, without permission
from the Publisher.
Russian language edition published by Williams Publishing House according to the Agreement with R&I
Enterprises International, Copyright © 2004
ISBN 5-8459-0572-9 (рус.)
ISBN 0-201-91465-4 (англ.)

© Издательский дом "Вильяме", 2004
© Addison-Wesley Publishing Company, Inc, 2002

ОГЛАВЛЕНИЕ
Предисловие

10

Вступление

12

ГЛАВА 1. Введение

15

ГЛАВА 2. Основы

25

ГЛАВА 3. Округление к степени 2

57

ГЛАВА 4. Арифметические границы

63

ГЛАВА 5. Подсчет битов

75

ГЛАВА 6. Поиск в слове

99

ГЛАВА 7. Перестановка битов и байтов

107

ГЛАВА 8. Умножение

131

ГЛАВА 9. Целочисленное деление

139

ГЛАВА 10. Целое деление на константы

155

ГЛАВА 11. Некоторые элементарные функции

197

ГЛАВА 12. Системы счисления с необычными основаниями

215

ГЛАВА 13. Код Грея

227

ГЛАВА 14. Кривая Гильберта

233

ГЛАВА 15. Числа с плавающей точкой

251

ГЛАВА 16. Формулы для простых чисел

261

ПРИЛОЖЕНИЕ А. Арифметические таблицы для 4-битовой машины

273

ПРИЛОЖЕНИЕ Б. Метод Ньютона

277

Источники информации

279

Предметный указатель

283

СОДЕРЖАНИЕ
Предисловие

10

Вступление

12

Благодарности

13

ГЛАВА 1. Введение

15

1.1. Система обозначений
1.2. Система команд и модель оценки времени выполнения команд

18

ГЛАВА 2. Основы

25

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. Сложение, вычитание и абсолютное значение --">