# Hacker's Delight, 2nd edition

Published by Addison-Wesley Professional (September 25, 2012) © 2013

**Henry S. Warren**

## eTextbook

- Available for purchase from all major ebook resellers, including InformIT.com.
- To request a review copy, click on the "Request a Review Copy" button.

- A print text (hardcover or paperback)
- Free shipping
- Also available for purchase as an ebook from all major ebook resellers, including InformIT.com

**, Henry 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.**

*Hacker’s Delight*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

A chapter on cyclic redundancy checking (CRC) Routines for the commonly used CRC-32 code

A chapter on error correcting codes (ECC) Hamming code

More on integer division by constants Methods using only shifts and adds

Computing the remainder without computing the quotient More on population count and leading zeros count

Counting the 1-bits in an array 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

Exercises and answers

Foreword xiii

Preface xv

**Chapter 1: Introduction 1**

1.1 Notation 1

1.2 Instruction Set and Execution Time Model 5

**Chapter 2: Basics 11**

2.1 Manipulating Rightmost Bits 11

2.2 Addition Combined with Logical Operations 16

2.3 Inequalities among Logical and Arithmetic Expressions 17

2.4 *Absolute Value* Function 18

2.5 Average of Two Integers 19

2.6 Sign Extension 19

2.7 Shift Right Signed from Unsigned 20

2.8 *Sign* Function 20

2.9 *Three-Valued Compare* Function 21

2.10 *Transfer of Sign* Function 22

2.11 Decoding a “Zero Means 2***n*” Field 22

2.12 Comparison Predicates 23

2.13 Overflow Detection 28

2.14 Condition Code Result of *Add*, *Subtract*, and *Multiply* 36

2.15 Rotate Shifts 37

2.16 Double-Length Add/Subtract 38

2.17 Double-Length Shifts 39

2.18 Multibyte *Add*, *Subtract*, *Absolute* *Value* 40

2.19 Doz, Max, Min 41

2.20 Exchanging Registers 45

2.21 Alternating among Two or More Values 48

2.22 A Boolean Decomposition Formula 51

2.23 Implementing Instructions for all 16 Binary Boolean Operations 53

**Chapter 3: Power-of-2 Boundaries 59**

3.1 Rounding Up/Down to a Multiple of a Known Power of 2 59

3.2 Rounding Up/Down to the Next Power of 2 60

3.3 Detecting a Power-of-2 Boundary Crossing 63

**Chapter 4: Arithmetic Bounds 67**

4.1 Checking Bounds of Integers 67

4.2 Propagating Bounds through *Add*’s and *Subtract*’s 70

4.3 Propagating Bounds through Logical Operations 73

**Chapter 5: Counting Bits 81**

5.1 Counting 1-Bits 81

5.2 Parity 96

5.3 Counting Leading 0’s 99

5.4 Counting Trailing 0’s 107

**Chapter 6: Searching Words 117**

6.1 Find First 0-Byte 117

6.2 Find First String of 1-Bits of a Given Length 123

6.3 Find Longest String of 1-Bits 125

6.4 Find Shortest String of 1-Bits 126

**Chapter 7: Rearranging Bits And Bytes 129**

7.1 Reversing Bits and Bytes 129

7.2 Shuffling Bits 139

7.3 Transposing a Bit Matrix 141

7.4 *Compress*, or *Generalized* *Extract* 150

7.5 *Expand*, or *Generalized* *Insert* 156

7.6 Hardware Algorithms for Compress and Expand 157

7.7 General Permutations, Sheep and Goats Operation 161

7.8 Rearrangements and Index Transformations 165

7.9 An LRU Algorithm 166

**Chapter 8: Multiplication 171**

8.1 Multiword Multiplication 171

8.2 High-Order Half of 64-Bit Product 173

8.3 High-Order Product Signed from/to Unsigned 174

8.4 Multiplication by Constants 175

**Chapter 9: Integer Division 181**

9.1 Preliminaries 181

9.2 Multiword Division 184

9.3 Unsigned Short Division from Signed Division 189

9.4 Unsigned Long Division 192

9.5 Doubleword Division from Long Division 197

**Chapter 10: Integer Division By Constants 205**

10.1 Signed Division by a Known Power of 2 205

10.2 Signed Remainder from Division by a Known Power of 2 206

10.3 Signed Division and Remainder by Non-Powers of 2 207

10.4 Signed Division by Divisors ≥ 2 210

10.5 Signed Division by Divisors ≤ —2 218

10.6 Incorporation into a Compiler 220

10.7 Miscellaneous Topics 223

10.8 Unsigned Division 227

10.9 Unsigned Division by Divisors ≥ 1 230

10.10 Incorporation into a Compiler (Unsigned) 232

10.11 Miscellaneous Topics (Unsigned) 234

10.12 Applicability to Modulus and Floor Division 237

10.13 Similar Methods 237

10.14 Sample Magic Numbers 238

10.15 Simple Code in Python 240

10.16 Exact Division by Constants 240

10.17 Test for Zero Remainder after Division by a Constant 248

10.18 Methods Not Using Multiply High 251

10.19 Remainder by Summing Digits 262

10.20 Remainder by Multiplication and Shifting Right 268

10.21 Converting to Exact Division 274

10.22 A Timing Test 276

10.23 A Circuit for Dividing by 3 276

**Chapter 11: Some Elementary Functions 279**

11.1 Integer Square Root 279

11.2 Integer Cube Root 287

11.3 Integer Exponentiation 288

11.4 Integer Logarithm 291

**Chapter 12: Unusual Bases For Number Systems 299**

12.1 Base —2 299

12.2 Base —1 + *i* 306

12.3 Other Bases 308

12.4 What Is the Most Efficient Base? 309

**Chapter 13: Gray Code 311**

13.1 Gray Code 311

13.2 Incrementing a Gray-Coded Integer 313

13.3 Negabinary Gray Code 315

13.4 Brief History and Applications 315

**Chapter 14: Cyclic Redundancy Check 319**

14.1 Introduction 319

14.2 Theory 320

14.3 Practice 323

**Chapter 15: Error-Correcting Codes 331**

15.1 Introduction 331

15.2 The Hamming Code 332

15.3 Software for SEC-DED on 32 Information Bits 337

15.4 Error Correction Considered More Generally 342

**Chapter 16: Hilbert's Curve 355**

16.1 A Recursive Algorithm for Generating the Hilbert Curve 356

16.2 Coordinates from Distance along the Hilbert Curve 358

16.3 Distance from Coordinates on the Hilbert Curve 366

16.4 Incrementing the Coordinates on the Hilbert Curve 368

16.5 Non-Recursive Generating Algorithms 371

16.6 Other Space-Filling Curves 371

16.7 Applications 372

**Chapter 17: Floating-Point 375**

17.1 IEEE Format 375

17.2 Floating-Point To/From Integer Conversions 377

17.3 Comparing Floating-Point Numbers Using Integer Operations 381

17.4 An Approximate Reciprocal Square Root Routine 383

17.5 The Distribution of Leading Digits 385

17.6 Table of Miscellaneous Values 387

**Chapter 18: Formulas For Primes 391**

18.1 Introduction 391

18.2 Willans’s Formulas 393

18.3 Wormell’s Formula 397

18.4 Formulas for Other Difficult Functions 398

**Answers To Exercises: 405**

**Appendix A: Arithmetic Tables For A 4-Bit Machine 453**

**Appendix B: Newton's Method 457**

**Appendix C: A Gallery Of Graphs Of Discrete Functions 459**

C.1 Plots of Logical Operations on Integers 459

C.2 Plots of Addition, Subtraction, and Multiplication 461

C.3 Plots of Functions Involving Division 463

C.4 Plots of the Compress, SAG, and Rotate Left Functions 464

C.5 2D Plots of Some Unary Functions 466

Bibliography 471

Index 481

** 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.

Need help? Get in touch