book

Hacker’s Delight, Second Edition

by Henry S. Warren

September 2012

Intermediate to advanced

512 pages

12h 41m

English

Addison-Wesley Professional

Read now

Unlock full access

Acknowledgments
1–1 Notation1–2 Instruction Set and Execution Time Model
2–1 Manipulating Rightmost Bits2–2 Addition Combined with Logical Operations2–3 Inequalities among Logical and Arithmetic Expressions2–4 Absolute Value Function2–5 Average of Two Integers2–6 Sign Extension2–7 Shift Right Signed from Unsigned2–8 Sign Function2–9 Three-Valued Compare Function2–10 Transfer of Sign Function2–11 Decoding a “Zero Means 2**n” Field2–12 Comparison Predicates2–13 Overflow Detection2–14 Condition Code Result of Add, Subtract, and Multiply2–15 Rotate Shifts2–16 Double-Length Add/Subtract2–17 Double-Length Shifts2–18 Multibyte Add, Subtract, Absolute Value2–19 Doz, Max, Min2–20 Exchanging Registers2–21 Alternating among Two or More Values2–22 A Boolean Decomposition Formula2–23 Implementing Instructions for All 16 Binary Boolean Operations
3–1 Rounding Up/Down to a Multiple of a Known Power of 23–2 Rounding Up/Down to the Next Power of 23–3 Detecting a Power-of-2 Boundary Crossing
4–1 Checking Bounds of Integers4–2 Propagating Bounds through Add’s and Subtract’s4–3 Propagating Bounds through Logical Operations

5–1 Counting 1-Bits5–2 Parity5–3 Counting Leading 0’s5–4 Counting Trailing 0’s
6–1 Find First 0-Byte6–2 Find First String of 1-Bits of a Given Length6–3 Find Longest String of 1-Bits6–4 Find Shortest String of 1-Bits
7–1 Reversing Bits and Bytes7–2 Shuffling Bits7–3 Transposing a Bit Matrix7–4 Compress, or Generalized Extract7–5 Expand, or Generalized Insert7–6 Hardware Algorithms for Compress and Expand7–7 General Permutations, Sheep and Goats Operation7–8 Rearrangements and Index Transformations7–9 An LRU Algorithm
8–1 Multiword Multiplication8–2 High-Order Half of 64-Bit Product8–3 High-Order Product Signed from/to Unsigned8–4 Multiplication by Constants
9–1 Preliminaries9–2 Multiword Division9–3 Unsigned Short Division from Signed Division9–4 Unsigned Long Division9–5 Doubleword Division from Long Division
10–1 Signed Division by a Known Power of 210–2 Signed Remainder from Division by a Known Power of 210–3 Signed Division and Remainder by Non-Powers of 210–4 Signed Division by Divisors ≥ 210–5 Signed Division by Divisors ≤ –210–6 Incorporation into a Compiler10–7 Miscellaneous Topics10–8 Unsigned Division10–9 Unsigned Division by Divisors ≥ 110–10 Incorporation into a Compiler (Unsigned)10–11 Miscellaneous Topics (Unsigned)10–12 Applicability to Modulus and Floor Division10–13 Similar Methods10–14 Sample Magic Numbers10–15 Simple Code in Python10–16 Exact Division by Constants10–17 Test for Zero Remainder after Division by a Constant10–18 Methods Not Using Multiply High10-19 Remainder by Summing Digits10–20 Remainder by Multiplication and Shifting Right10–21 Converting to Exact Division10–22 A Timing Test10–23 A Circuit for Dividing by 3
11–1 Integer Square Root11–2 Integer Cube Root11–3 Integer Exponentiation11–4 Integer Logarithm
12–1 Base –212-2 Base –1 + i12–3 Other Bases12–4 What Is the Most Efficient Base?
13–1 Gray Code13-2 Incrementing a Gray-Coded Integer13–3 Negabinary Gray Code13–4 Brief History and Applications
14–1 Introduction14–2 Theory14–3 Practice
15–1 Introduction15–2 The Hamming Code15–3 Software for SEC-DED on 32 Information Bits15–4 Error Correction Considered More Generally
16–1 A Recursive Algorithm for Generating the Hilbert Curve16–2 Coordinates from Distance along the Hilbert Curve16–3 Distance from Coordinates on the Hilbert Curve16–4 Incrementing the Coordinates on the Hilbert Curve16–5 Non-Recursive Generating Algorithms16–6 Other Space-Filling Curves16–7 Applications
17–1 IEEE Format17–2 Floating-Point To/From Integer Conversions17–3 Comparing Floating-Point Numbers Using Integer Operations17–4 An Approximate Reciprocal Square Root Routine17–5 The Distribution of Leading Digits17–6 Table of Miscellaneous Values
18–1 Introduction18–2 Willans’s Formulas18–3 Wormell’s Formula18–4 Formulas for Other Difficult Functions
Chapter 1: IntroductionChapter 2: BasicsChapter 3: Power-of-2 BoundariesChapter 4: Arithmetic BoundsChapter 5: Counting BitsChapter 6: Searching WordsChapter 7: Rearranging Bits and BytesChapter 8: MultiplicationChapter 9: Integer DivisionChapter 10: Integer Division by ConstantsChapter 11: Some Elementary FunctionsChapter 12: Unusual Bases for Number SystemsChapter 13: Gray CodeChapter 14: Cyclic Redundancy CheckChapter 15: Error-Correcting CodesChapter 16: Hilbert’s CurveChapter 17: Floating-PointChapter 18: Formulas for Primes
C–1 Plots of Logical Operations on IntegersC–2 Plots of Addition, Subtraction, and MultiplicationC–3 Plots of Functions Involving DivisionC–4 Plots of the Compress, SAG, and Rotate Left FunctionsC–5 2D Plots of Some Unary Functions
ForewordPrefaceChapter 2Chapter 3Chapter 4Chapter 5Chapter 7Chapter 8Chapter 12Chapter 14Chapter 15Chapter 16Chapter 17Chapter 18Answers To ExercisesAppendix B

Content preview from Hacker’s Delight, Second Edition

Chapter 16. Hilbert’s Curve

In 1890, Giuseppe Peano discovered a planar curve¹ with the rather surprising property that it is “space-filling.” The curve winds around the unit square and hits every point (x, y) at least once.

Peano’s curve is based on dividing each side of the unit square into three equal parts, which divides the square into nine smaller squares. His curve traverses these nine squares in a certain order. Then, each of the nine small squares is similarly divided into nine still smaller squares, and the curve is modified to traverse all these squares in a certain order. The curve can be described using fractions expressed in base 3; in fact, that’s the way Peano first described it.

In 1891, David Hilbert [Hil] discovered a variation ...