''Hacker's Delight'' is a software algorithm book by Henry S. Warren, Jr. first published in 2002. It presents fast bit-level and low-level arithmetic

algorithms In mathematics and computer science, an algorithm () is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for per ...

for common tasks such as counting bits or improving speed of division by using multiplication.

Background

The author, an IBM researcher working on systems ranging from the

IBM 704 The IBM 704 is the model name of a large digital computer, digital mainframe computer introduced by IBM in 1954. Designed by John Backus and Gene Amdahl, it was the first mass-produced computer with hardware for floating-point arithmetic. The I ...

to the

PowerPC PowerPC (with the backronym Performance Optimization With Enhanced RISC – Performance Computing, sometimes abbreviated as PPC) is a reduced instruction set computer (RISC) instruction set architecture (ISA) created by the 1991 Apple Inc., App ...

, collected what he called "programming tricks" over the course of his career. These tricks concern efficient low-level manipulation of bit strings and numbers. According to the book's foreword by Guy L. Steele, the target audience includes

compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...

writers and people writing high-performance code.

Summary

Programming examples are written in C and assembler for a

RISC In electronics and computer science, a reduced instruction set computer (RISC) is a computer architecture designed to simplify the individual instructions given to the computer to accomplish tasks. Compared to the instructions given to a comp ...

architecture similar, but not identical to

. Algorithms are given as formulas for any number of bits, the examples usually for 32 bits. Apart from the introduction, chapters are independent of each other, each focusing on a particular subject. Many algorithms in the book depend on

two's complement Two's complement is the most common method of representing signed (positive, negative, and zero) integers on computers, and more generally, fixed point binary values. Two's complement uses the binary digit with the ''greatest'' value as the ''s ...

integer numbers. The subject matter of the second edition of the book includes algorithms for * Basic algorithms for manipulating individual bits, formulas for identities, inequalities, overflow detection for arithmetic operations and shifts * Rounding up and down to a multiple of a known

power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number 2, two as the Base (exponentiation), base and integer as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^ ...

, the next power of two and for detecting whether an operation crossed a power-of-two boundary * Checking bounds * Counting total,

leading In typography, leading ( ) is the space between adjacent lines of type; the exact definition varies. In hand typesetting, leading is the thin strips of lead (or aluminium) that were inserted between lines of type in the composing stick to incre ...

and trailing zeros * Searching for bit strings * Permutations of bits and bytes in a word * Software algorithms for multiplication * Integer division * Efficient integer division and calculating of the remainder when the divisor is known * Integer

square In geometry, a square is a regular polygon, regular quadrilateral. It has four straight sides of equal length and four equal angles. Squares are special cases of rectangles, which have four equal angles, and of rhombuses, which have four equal si ...

and

cube A cube or regular hexahedron is a three-dimensional space, three-dimensional solid object in geometry, which is bounded by six congruent square (geometry), square faces, a type of polyhedron. It has twelve congruent edges and eight vertices. It i ...

roots * Unusual number systems, including base −2 * Transfer of values between

floating-point In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a ''significand'' (a Sign (mathematics), signed sequence of a fixed number of digits in some Radix, base) multiplied by an integer power of that ba ...

and

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

Cyclic redundancy check A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data. Blocks of data entering these systems get a short ''check value'' attached, based on ...

error-correcting code In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The centra ...

s and

Gray code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray (researcher), Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For ...

s * Hilbert curves, including a discussion of applications

Style

The style is that of an informal mathematical textbook. Formulas are used extensively.

Mathematical proofs A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof c ...

are given for some non-obvious algorithms, but are not the focus of the book.

Reception

Overall reception has been generally positive.

Publication history

The book was published by Addison-Wesley Professional. The first edition was released in 2002 and the second in 2013. Japanese language edition of this book was published by SIBaccess Co. Ltd., in 2004.

References

External links

Archive of Hacker's Delight website
2002 non-fiction books 2013 non-fiction books Computer programming books Addison-Wesley books Computer science books