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 for common tasks such as counting bits or improving speed of division by using multiplication.
 Hacker's Delight First edition (2002) | |
| Author | Henry S. Warren, Jr. |
|---|---|
| Language | English |
| Publisher | Addison-Wesley Professional |
Publication date | 2002 |
| Publication place | United States |
| Pages | 306 (first edition), 494 (second edition) |
| ISBN | 0201914654 (Second edition 0321842685) |
| LC Class | QA76.6.W375 |
Background
editThe author, an IBM researcher working on systems ranging from the IBM 704 to the PowerPC,[1] 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 writers and people writing high-performance code.
Summary
editProgramming examples are written in C and assembler for a RISC architecture similar, but not identical to PowerPC. 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 integer numbers.
The subject matter of the second edition of the book[1] 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 2, the next power of 2 and for detecting if an operation crossed a power-of-2 boundary
- Checking bounds
- Counting total, leading 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 and cube roots
- Unusual number systems, including base -2
- Transfer of values between floating point and integer
- Cyclic redundancy checks, error-correcting codes and Gray codes
- Hilbert curves including a discussion of applications
Style
editThe style is that of an informal mathematical textbook. Formulas are used extensively. Mathematical proofs are given for some non-obvious algorithms, but are not the focus of the book.
Reception
editPublication history
editThe book was published by Addison-Wesley Professional. The first edition was released in 2002[4] and the second in 2013.[1] Japanese language edition of this book was published by SIBaccess Co. Ltd., in 2004.
See also
editReferences
edit- ^ a b c Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
- ^ Baxter, Michael (2003-04-01). "Hacker's Delight". Reviews. Linux Journal. Archived from the original on 2020-09-27. Retrieved 2021-08-28.
- ^ Maxfield, Clive "Max" (2012-04-05). "Book Review: Engineer's Bookshelf - Hacker's Delight by Henry S. Warren, Jr". EE Times. Archived from the original on 2017-04-02. Retrieved 2017-04-02.
- ^ Warren Jr., Henry S. (2002). Hacker's Delight (1 ed.). Addison Wesley. ISBN 978-0-201-91465-8.
Further reading
edit- Beeler, Michael; Gosper, Ralph William; Schroeppel, Richard C. (April 1995) [1972-02-29]. "Artificial Intelligence Memo No. 239". In Baker, Henry Givens Jr. (ed.). HAKMEM (retyped & converted ed.). Cambridge, Massachusetts, USA: Artificial Intelligence Laboratory, Massachusetts Institute of Technology (MIT). Archived from the original on 2019-10-08. Retrieved 2016-01-02.
- Jones, Douglas W. (2014-09-10) [1999]. "Arithmetic Tutorials". Iowa City, Iowa, USA: The University of Iowa, Department of Computer Science. Archived from the original on 2019-07-10. Retrieved 2016-01-03.
- Cowlishaw, Mike F. (2015) [1981, 2008]. "General Decimal Arithmetic". Archived from the original on 2019-11-02. Retrieved 2016-01-02.
- Ingenoso, Tony (1999-02-03) [1998]. "Chapter 11 - More tricks in C and Assembler code". Making Code Work Better - How to minimize the size of 80x86 code and sometimes make it faster (e-book). Archived from the original on 2019-11-18. Retrieved 2019-11-18.
- Anderson, Sean Eron, ed. (2009-11-26) [1997]. "Bit Twiddling Hacks". Stanford University. Archived from the original on 2020-06-01. Retrieved 2020-06-01.