Hacker's Delight

Henry S. Warren, Jr., has had a fifty-year career with IBM, spanning from the IBM 704 to the PowerPC and beyond. He has worked on various military command and control systems and on the SETL (SET Language) project under Jack Schwartz. Since 1973, Hank has been with IBM’s Research Division, focusing on compilers and computer architectures. He currently works on a supercomputer project aimed at an exaflop. Hank received his Ph.D. in computer science from the Courant Institute at New York University.

"This is the first book that promises to tell the deep, dark secrets of computer arithmetic, and it delivers in spades. It contains every trick I knew plus many, many more. A godsend for library developers, compiler writers, and lovers of elegant hacks, it deserves a spot on your shelf right next to Knuth. In the ten years since the first edition came out, it's been absolutely invaluable to my work at Sun and Google. I'm thrilled with all of the new material in the second edition." - Joshua Bloch "When I first saw the title, I figured that the book must be either a cookbook for breaking into computers (unlikely) or some sort of compendium of little programming tricks. It's the latter, but it's thorough, almost encyclopedic, in its coverage. The second edition covers two new major topics and expands the overall collection with dozens of additional little tricks, including one that I put to use right away in a binary search algorithm: computing the average of two integers without risking overflow. This hacker is indeed delighted!" - Guy Steele

• Foreword xiiiPreface xvChapter 1: Introduction 11.1 Notation 11.2 Instruction Set and Execution Time Model 5Chapter 2: Basics 112.1 Manipulating Rightmost Bits 112.2 Addition Combined with Logical Operations 162.3 Inequalities among Logical and Arithmetic Expressions 172.4 Absolute Value Function 182.5 Average of Two Integers 192.6 Sign Extension 192.7 Shift Right Signed from Unsigned 202.8 Sign Function 202.9 Three-Valued Compare Function 212.10 Transfer of Sign Function 222.11 Decoding a “Zero Means 2**n” Field 222.12 Comparison Predicates 232.13 Overflow Detection 282.14 Condition Code Result of Add, Subtract, and Multiply 362.15 Rotate Shifts 372.16 Double-Length Add/Subtract 382.17 Double-Length Shifts 392.18 Multibyte Add, Subtract, Absolute Value 402.19 Doz, Max, Min 412.20 Exchanging Registers 452.21 Alternating among Two or More Values 482.22 A Boolean Decomposition Formula 512.23 Implementing Instructions for all 16 Binary Boolean Operations 53Chapter 3: Power-of-2 Boundaries 593.1 Rounding Up/Down to a Multiple of a Known Power of 2 593.2 Rounding Up/Down to the Next Power of 2 603.3 Detecting a Power-of-2 Boundary Crossing 63Chapter 4: Arithmetic Bounds 674.1 Checking Bounds of Integers 674.2 Propagating Bounds through Add’s and Subtract’s 704.3 Propagating Bounds through Logical Operations 73Chapter 5: Counting Bits 815.1 Counting 1-Bits 815.2 Parity 965.3 Counting Leading 0’s 995.4 Counting Trailing 0’s 107Chapter 6: Searching Words 1176.1 Find First 0-Byte 1176.2 Find First String of 1-Bits of a Given Length 1236.3 Find Longest String of 1-Bits 1256.4 Find Shortest String of 1-Bits 126Chapter 7: Rearranging Bits And Bytes 1297.1 Reversing Bits and Bytes 1297.2 Shuffling Bits 1397.3 Transposing a Bit Matrix 1417.4 Compress, or Generalized Extract 1507.5 Expand, or Generalized Insert 1567.6 Hardware Algorithms for Compress and Expand 1577.7 General Permutations, Sheep and Goats Operation 1617.8 Rearrangements and Index Transformations 1657.9 An LRU Algorithm 166Chapter 8: Multiplication 1718.1 Multiword Multiplication 1718.2 High-Order Half of 64-Bit Product 1738.3 High-Order Product Signed from/to Unsigned 1748.4 Multiplication by Constants 175Chapter 9: Integer Division 1819.1 Preliminaries 1819.2 Multiword Division 1849.3 Unsigned Short Division from Signed Division 1899.4 Unsigned Long Division 1929.5 Doubleword Division from Long Division 197Chapter 10: Integer Division By Constants 20510.1 Signed Division by a Known Power of 2 20510.2 Signed Remainder from Division by a Known Power of 2 20610.3 Signed Division and Remainder by Non-Powers of 2 20710.4 Signed Division by Divisors ≥ 2 21010.5 Signed Division by Divisors ≤ —2 21810.6 Incorporation into a Compiler 22010.7 Miscellaneous Topics 22310.8 Unsigned Division 22710.9 Unsigned Division by Divisors ≥ 1 23010.10 Incorporation into a Compiler (Unsigned) 23210.11 Miscellaneous Topics (Unsigned) 23410.12 Applicability to Modulus and Floor Division 23710.13 Similar Methods 23710.14 Sample Magic Numbers 23810.15 Simple Code in Python 24010.16 Exact Division by Constants 24010.17 Test for Zero Remainder after Division by a Constant 24810.18 Methods Not Using Multiply High 25110.19 Remainder by Summing Digits 26210.20 Remainder by Multiplication and Shifting Right 26810.21 Converting to Exact Division 27410.22 A Timing Test 27610.23 A Circuit for Dividing by 3 276Chapter 11: Some Elementary Functions 27911.1 Integer Square Root 27911.2 Integer Cube Root 28711.3 Integer Exponentiation 28811.4 Integer Logarithm 291Chapter 12: Unusual Bases For Number Systems 29912.1 Base —2 29912.2 Base —1 + i 30612.3 Other Bases 30812.4 What Is the Most Efficient Base? 309Chapter 13: Gray Code 31113.1 Gray Code 31113.2 Incrementing a Gray-Coded Integer 31313.3 Negabinary Gray Code 31513.4 Brief History and Applications 315Chapter 14: Cyclic Redundancy Check 31914.1 Introduction 31914.2 Theory 32014.3 Practice 323Chapter 15: Error-Correcting Codes 33115.1 Introduction 33115.2 The Hamming Code 33215.3 Software for SEC-DED on 32 Information Bits 33715.4 Error Correction Considered More Generally 342Chapter 16: Hilbert's Curve 35516.1 A Recursive Algorithm for Generating the Hilbert Curve 35616.2 Coordinates from Distance along the Hilbert Curve 35816.3 Distance from Coordinates on the Hilbert Curve 36616.4 Incrementing the Coordinates on the Hilbert Curve 36816.5 Non-Recursive Generating Algorithms 37116.6 Other Space-Filling Curves 37116.7 Applications 372Chapter 17: Floating-Point 37517.1 IEEE Format 37517.2 Floating-Point To/From Integer Conversions 37717.3 Comparing Floating-Point Numbers Using Integer Operations 38117.4 An Approximate Reciprocal Square Root Routine 38317.5 The Distribution of Leading Digits 38517.6 Table of Miscellaneous Values 387Chapter 18: Formulas For Primes 39118.1 Introduction 39118.2 Willans’s Formulas 39318.3 Wormell’s Formula 39718.4 Formulas for Other Difficult Functions 398Answers To Exercises: 405Appendix A: Arithmetic Tables For A 4-Bit Machine 453Appendix B: Newton's Method 457Appendix C: A Gallery Of Graphs Of Discrete Functions 459C.1 Plots of Logical Operations on Integers 459C.2 Plots of Addition, Subtraction, and Multiplication 461C.3 Plots of Functions Involving Division 463C.4 Plots of the Compress, SAG, and Rotate Left Functions 464C.5 2D Plots of Some Unary Functions 466Bibliography 471Index 481