Восторг хакера

Hacker's Delight - это книга алгоритмов программного обеспечения, написанная Генри С. Уорреном-младшим. В ней представлены быстрые битовые и низкоуровневые арифметические алгоритмы для общих задач, таких как подсчет битов или повышение скорости деления с помощью умножения.

• 1 Справочная информация
• 2 Резюме
• 3 Стиль
• 4 Прием
• 5 История публикации
• 6 См. Также
• 7 ссылки
• 8 Дальнейшее чтение
• 9 Внешние ссылки

Автор, исследователь IBM, работающий над системами от IBM 704 до PowerPC, в течение своей карьеры собирал то, что он называл «трюками программирования». Эти уловки касаются эффективных низкоуровневых манипуляций с битовыми строками и числами. Согласно предисловию к книге Гая Л. Стила, целевая аудитория - это авторы компиляторов и люди, пишущие высокопроизводительный код.

Примеры программирования написаны на C и ассемблере для архитектуры RISC, аналогичной, но не идентичной PowerPC. Алгоритмы представлены в виде формул для любого числа битов, примеры обычно для 32 битов.

Помимо введения, главы независимы друг от друга, каждая из которых посвящена определенной теме. Многие алгоритмы в книге зависят от целых чисел с дополнением до двух.

Тематика второго издания книги включает алгоритмы для

• Базовые алгоритмы для управления отдельными битами, формулы для идентичностей, неравенств, обнаружение переполнения для арифметических операций и сдвигов
• Округление в большую и меньшую сторону до кратной известной степени 2, следующей степени 2 и для определения того, пересекла ли операция границу степени двойки
• Проверка границ
• Подсчет общей, ведущие и конечные нули
• Поиск битовых строк
• Перестановки битов и байтов в слове
• Программные алгоритмы умножения
• Целочисленное деление
• Эффективное целочисленное деление и вычисление остатка при известном делителе
• Целочисленные квадратные и кубические корни
• Необычные системы счисления, включая основание -2
• Передача значений между числами с плавающей запятой и целыми числами
• Циклический контроль избыточности, коды исправления ошибок и коды Грея
• Кривые Гильберта, включая обсуждение приложений

Стиль неформального учебника математики. Формулы используются широко. Математические доказательства приведены для некоторых неочевидных алгоритмов, но им не посвящена книга.

В целом прием был положительным.

Книга была опубликована издательством Addison-Wesley Professional. Первое издание было выпущено в 2002 году, а второе - в 2013 году.

• HAKMEM
• Popcount
• Найти первый набор

• Билер, Майкл; Госпер, Ральф Уильям ; Schroeppel, Ричард К. (апрель 1995 г.) [1972-02-29]. «Памятка по искусственному интеллекту № 239». В Бейкер-младший, Генри Гивенс (ред.). ХАКМЕМ (перепечатано и преобразовано под ред.). Кембридж, Массачусетс, США: Лаборатория искусственного интеллекта, Массачусетский технологический институт (MIT). Архивировано 8 октября 2019 года. Проверено 2 января 2016.
• Джонс, Дуглас В. (2014-09-10) [1999]. «Учебники по арифметике». Айова-Сити, штат Айова, США: Университет штата Айова, факультет компьютерных наук. Архивировано 10 июля 2019 года. Проверено 3 января 2016.
• Коулишоу, Майк Ф. (2015) [1981, 2008]. «Общая десятичная арифметика». Архивировано 2 ноября 2019 года. Проверено 2 января 2016.
• Ингеносо, Тони (1999-02-03) [1998]. «Глава 11 - Дополнительные приемы в коде C и Assembler». Улучшение работы кода - Как уменьшить размер кода 80x86, а иногда и сделать его быстрее (электронная книга). Архивировано 18 ноября 2019 года. Проверено 18 ноября 2019.
• Андерсон, Шон Эрон, изд. (2009-11-26) [1997]. "Bit Twiddling Hacks". Стэнфордский университет. Архивировано 01 июня 2020 года. Проверено 1 июня 2020.

• Архив сайта Hacker's Delight