Hacker’s Delight, Second Edition

Hacker’s Delight, Second Edition

by Henry S. Warren
Released September 2012
Publisher(s): Addison-Wesley Professional
ISBN: 9780133084993

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

In Hacker’s Delight, Second Edition, Hank Warren once again compiles an irresistible collection of programming hacks: timesaving techniques, algorithms, and tricks that help programmers build more elegant and efficient software, while also gaining deeper insights into their craft. Warren’s hacks are eminently practical, but they’re also intrinsically interesting, and sometimes unexpected, much like the solution to a great puzzle. They are, in a word, a delight to any programmer who is excited by the opportunity to improve.

Extensive additions in this edition include

  • A new chapter on cyclic redundancy checking (CRC), including routines for the commonly used CRC-32 code

  • A new chapter on error correcting codes (ECC), including routines for the Hamming code

  • More coverage of integer division by constants, including methods using only shifts and adds

  • Computing remainders without computing a quotient

  • More coverage of population count and counting leading zeros

  • Array population count

  • New algorithms for compress and expand

  • An LRU algorithm

  • Floating-point to/from integer conversions

  • Approximate floating-point reciprocal square root routine

  • A gallery of graphs of discrete functions

  • Now with exercises and answers

    •

    Table of contents

    1. Title Page
    2. Copyright Page
    3. Dedication Page
    4. Contents
    5. Foreword
    6. Preface
      1. Acknowledgments
    7. Chapter 1. Introduction
      1. 1–1 Notation
      2. 1–2 Instruction Set and Execution Time Model
    8. Chapter 2. Basics
      1. 2–1 Manipulating Rightmost Bits
      2. 2–2 Addition Combined with Logical Operations
      3. 2–3 Inequalities among Logical and Arithmetic Expressions
      4. 2–4 Absolute Value Function
      5. 2–5 Average of Two Integers
      6. 2–6 Sign Extension
      7. 2–7 Shift Right Signed from Unsigned
      8. 2–8 Sign Function
      9. 2–9 Three-Valued Compare Function
      10. 2–10 Transfer of Sign Function
      11. 2–11 Decoding a “Zero Means 2**n” Field
      12. 2–12 Comparison Predicates
      13. 2–13 Overflow Detection
      14. 2–14 Condition Code Result of Add, Subtract, and Multiply
      15. 2–15 Rotate Shifts
      16. 2–16 Double-Length Add/Subtract
      17. 2–17 Double-Length Shifts
      18. 2–18 Multibyte Add, Subtract, Absolute Value
      19. 2–19 Doz, Max, Min
      20. 2–20 Exchanging Registers
      21. 2–21 Alternating among Two or More Values
      22. 2–22 A Boolean Decomposition Formula
      23. 2–23 Implementing Instructions for All 16 Binary Boolean Operations
    9. Chapter 3. Power-of-2 Boundaries
      1. 3–1 Rounding Up/Down to a Multiple of a Known Power of 2
      2. 3–2 Rounding Up/Down to the Next Power of 2
      3. 3–3 Detecting a Power-of-2 Boundary Crossing
    10. Chapter 4. Arithmetic Bounds
      1. 4–1 Checking Bounds of Integers
      2. 4–2 Propagating Bounds through Add’s and Subtract’s
      3. 4–3 Propagating Bounds through Logical Operations
    11. Chapter 5. Counting Bits
      1. 5–1 Counting 1-Bits
      2. 5–2 Parity
      3. 5–3 Counting Leading 0’s
      4. 5–4 Counting Trailing 0’s
    12. Chapter 6. Searching Words
      1. 6–1 Find First 0-Byte
      2. 6–2 Find First String of 1-Bits of a Given Length
      3. 6–3 Find Longest String of 1-Bits
      4. 6–4 Find Shortest String of 1-Bits
    13. Chapter 7. Rearranging Bits and Bytes
      1. 7–1 Reversing Bits and Bytes
      2. 7–2 Shuffling Bits
      3. 7–3 Transposing a Bit Matrix
      4. 7–4 Compress, or Generalized Extract
      5. 7–5 Expand, or Generalized Insert
      6. 7–6 Hardware Algorithms for Compress and Expand
      7. 7–7 General Permutations, Sheep and Goats Operation
      8. 7–8 Rearrangements and Index Transformations
      9. 7–9 An LRU Algorithm
    14. Chapter 8. Multiplication
      1. 8–1 Multiword Multiplication
      2. 8–2 High-Order Half of 64-Bit Product
      3. 8–3 High-Order Product Signed from/to Unsigned
      4. 8–4 Multiplication by Constants
    15. Chapter 9. Integer Division
      1. 9–1 Preliminaries
      2. 9–2 Multiword Division
      3. 9–3 Unsigned Short Division from Signed Division
      4. 9–4 Unsigned Long Division
      5. 9–5 Doubleword Division from Long Division
    16. Chapter 10. Integer Division By Constants
      1. 10–1 Signed Division by a Known Power of 2
      2. 10–2 Signed Remainder from Division by a Known Power of 2
      3. 10–3 Signed Division and Remainder by Non-Powers of 2
      4. 10–4 Signed Division by Divisors ≥ 2
      5. 10–5 Signed Division by Divisors ≤ –2
      6. 10–6 Incorporation into a Compiler
      7. 10–7 Miscellaneous Topics
      8. 10–8 Unsigned Division
      9. 10–9 Unsigned Division by Divisors ≥ 1
      10. 10–10 Incorporation into a Compiler (Unsigned)
      11. 10–11 Miscellaneous Topics (Unsigned)
      12. 10–12 Applicability to Modulus and Floor Division
      13. 10–13 Similar Methods
      14. 10–14 Sample Magic Numbers
      15. 10–15 Simple Code in Python
      16. 10–16 Exact Division by Constants
      17. 10–17 Test for Zero Remainder after Division by a Constant
      18. 10–18 Methods Not Using Multiply High
      19. 10-19 Remainder by Summing Digits
      20. 10–20 Remainder by Multiplication and Shifting Right
      21. 10–21 Converting to Exact Division
      22. 10–22 A Timing Test
      23. 10–23 A Circuit for Dividing by 3
    17. Chapter 11. Some Elementary Functions
      1. 11–1 Integer Square Root
      2. 11–2 Integer Cube Root
      3. 11–3 Integer Exponentiation
      4. 11–4 Integer Logarithm
    18. Chapter 12. Unusual Bases for Number Systems
      1. 12–1 Base –2
      2. 12-2 Base –1 + i
      3. 12–3 Other Bases
      4. 12–4 What Is the Most Efficient Base?
    19. Chapter 13. Gray Code
      1. 13–1 Gray Code
      2. 13-2 Incrementing a Gray-Coded Integer
      3. 13–3 Negabinary Gray Code
      4. 13–4 Brief History and Applications
    20. Chapter 14. Cyclic Redundancy Check
      1. 14–1 Introduction
      2. 14–2 Theory
      3. 14–3 Practice
    21. Chapter 15. Error-Correcting Codes
      1. 15–1 Introduction
      2. 15–2 The Hamming Code
      3. 15–3 Software for SEC-DED on 32 Information Bits
      4. 15–4 Error Correction Considered More Generally
    22. Chapter 16. Hilbert’s Curve
      1. 16–1 A Recursive Algorithm for Generating the Hilbert Curve
      2. 16–2 Coordinates from Distance along the Hilbert Curve
      3. 16–3 Distance from Coordinates on the Hilbert Curve
      4. 16–4 Incrementing the Coordinates on the Hilbert Curve
      5. 16–5 Non-Recursive Generating Algorithms
      6. 16–6 Other Space-Filling Curves
      7. 16–7 Applications
    23. Chapter 17. Floating-Point
      1. 17–1 IEEE Format
      2. 17–2 Floating-Point To/From Integer Conversions
      3. 17–3 Comparing Floating-Point Numbers Using Integer Operations
      4. 17–4 An Approximate Reciprocal Square Root Routine
      5. 17–5 The Distribution of Leading Digits
      6. 17–6 Table of Miscellaneous Values
    24. Chapter 18. Formulas For Primes
      1. 18–1 Introduction
      2. 18–2 Willans’s Formulas
      3. 18–3 Wormell’s Formula
      4. 18–4 Formulas for Other Difficult Functions
    25. Answers To Exercises
      1. Chapter 1: Introduction
      2. Chapter 2: Basics
      3. Chapter 3: Power-of-2 Boundaries
      4. Chapter 4: Arithmetic Bounds
      5. Chapter 5: Counting Bits
      6. Chapter 6: Searching Words
      7. Chapter 7: Rearranging Bits and Bytes
      8. Chapter 8: Multiplication
      9. Chapter 9: Integer Division
      10. Chapter 10: Integer Division by Constants
      11. Chapter 11: Some Elementary Functions
      12. Chapter 12: Unusual Bases for Number Systems
      13. Chapter 13: Gray Code
      14. Chapter 14: Cyclic Redundancy Check
      15. Chapter 15: Error-Correcting Codes
      16. Chapter 16: Hilbert’s Curve
      17. Chapter 17: Floating-Point
      18. Chapter 18: Formulas for Primes
    26. Appendix A. Arithmetic Tables for A 4-Bit Machine
    27. Appendix B. Newton’s Method
    28. Appendix C. A Gallery of Graphs of Discrete Functions
      1. C–1 Plots of Logical Operations on Integers
      2. C–2 Plots of Addition, Subtraction, and Multiplication
      3. C–3 Plots of Functions Involving Division
      4. C–4 Plots of the Compress, SAG, and Rotate Left Functions
      5. C–5 2D Plots of Some Unary Functions
    29. Bibliography
    30. Index
    31. Footnotes
      1. Foreword
      2. Preface
      3. Chapter 2
      4. Chapter 3
      5. Chapter 4
      6. Chapter 5
      7. Chapter 7
      8. Chapter 8
      9. Chapter 12
      10. Chapter 14
      11. Chapter 15
      12. Chapter 16
      13. Chapter 17
      14. Chapter 18
      15. Answers To Exercises
      16. Appendix B

    Product information

    • Title: Hacker’s Delight, Second Edition
    • Author(s): Henry S. Warren
    • Release date: September 2012
    • Publisher(s): Addison-Wesley Professional
    • ISBN: 9780133084993