Hacker's delight

Format:

Book

Author/Creator:

Warren, Henry S, Author.

Language:

English

Subjects (All):

Computer programming.

Physical Description:

1 online resource (1 v.) : ill.

Edition:

2nd ed.

Place of Publication:

[Place of publication not identified] Pearson Education 2013

Language Note:

English

System Details:

text file

Summary:

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

Contents:

Intro

Title Page

Copyright Page

Dedication Page

Contents

Foreword

Preface

Acknowledgments

Chapter 1. Introduction

1-1 Notation

1-2 Instruction Set and Execution Time Model

Chapter 2. Basics

2-1 Manipulating Rightmost Bits

2-2 Addition Combined with Logical Operations

2-3 Inequalities among Logical and Arithmetic Expressions

2-4 Absolute Value Function

2-5 Average of Two Integers

2-6 Sign Extension

2-7 Shift Right Signed from Unsigned

2-8 Sign Function

2-9 Three-Valued Compare Function

2-10 Transfer of Sign Function

2-11 Decoding a "Zero Means 2**n" Field

2-12 Comparison Predicates

2-13 Overflow Detection

2-14 Condition Code Result of Add, Subtract, and Multiply

2-15 Rotate Shifts

2-16 Double-Length Add/Subtract

2-17 Double-Length Shifts

2-18 Multibyte Add, Subtract, Absolute Value

2-19 Doz, Max, Min

2-20 Exchanging Registers

2-21 Alternating among Two or More Values

2-22 A Boolean Decomposition Formula

2-23 Implementing Instructions for All 16 Binary Boolean Operations

Chapter 3. Power-of-2 Boundaries

3-1 Rounding Up/Down to a Multiple of a Known Power of 2

3-2 Rounding Up/Down to the Next Power of 2

3-3 Detecting a Power-of-2 Boundary Crossing

Chapter 4. Arithmetic Bounds

4-1 Checking Bounds of Integers

4-2 Propagating Bounds through Add's and Subtract's

4-3 Propagating Bounds through Logical Operations

Chapter 5. Counting Bits

5-1 Counting 1-Bits

5-2 Parity

5-3 Counting Leading 0's

5-4 Counting Trailing 0's

Chapter 6. Searching Words

6-1 Find First 0-Byte

6-2 Find First String of 1-Bits of a Given Length

6-3 Find Longest String of 1-Bits

6-4 Find Shortest String of 1-Bits

Chapter 7. Rearranging Bits and Bytes

7-1 Reversing Bits and Bytes

7-2 Shuffling Bits.

7-3 Transposing a Bit Matrix

7-4 Compress, or Generalized Extract

7-5 Expand, or Generalized Insert

7-6 Hardware Algorithms for Compress and Expand

7-7 General Permutations, Sheep and Goats Operation

7-8 Rearrangements and Index Transformations

7-9 An LRU Algorithm

Chapter 8. Multiplication

8-1 Multiword Multiplication

8-2 High-Order Half of 64-Bit Product

8-3 High-Order Product Signed from/to Unsigned

8-4 Multiplication by Constants

Chapter 9. Integer Division

9-1 Preliminaries

9-2 Multiword Division

9-3 Unsigned Short Division from Signed Division

9-4 Unsigned Long Division

9-5 Doubleword Division from Long Division

Chapter 10. Integer Division By Constants

10-1 Signed Division by a Known Power of 2

10-2 Signed Remainder from Division by a Known Power of 2

10-3 Signed Division and Remainder by Non-Powers of 2

10-4 Signed Division by Divisors ≥ 2

10-5 Signed Division by Divisors ≤ -2

10-6 Incorporation into a Compiler

10-7 Miscellaneous Topics

10-8 Unsigned Division

10-9 Unsigned Division by Divisors ≥ 1

10-10 Incorporation into a Compiler (Unsigned)

10-11 Miscellaneous Topics (Unsigned)

10-12 Applicability to Modulus and Floor Division

10-13 Similar Methods

10-14 Sample Magic Numbers

10-15 Simple Code in Python

10-16 Exact Division by Constants

10-17 Test for Zero Remainder after Division by a Constant

10-18 Methods Not Using Multiply High

10-19 Remainder by Summing Digits

10-20 Remainder by Multiplication and Shifting Right

10-21 Converting to Exact Division

10-22 A Timing Test

10-23 A Circuit for Dividing by 3

Chapter 11. Some Elementary Functions

11-1 Integer Square Root

11-2 Integer Cube Root

11-3 Integer Exponentiation

11-4 Integer Logarithm

Chapter 12. Unusual Bases for Number Systems

12-1 Base -2.

12-2 Base -1 + i

12-3 Other Bases

12-4 What Is the Most Efficient Base?

Chapter 13. Gray Code

13-1 Gray Code

13-2 Incrementing a Gray-Coded Integer

13-3 Negabinary Gray Code

13-4 Brief History and Applications

Chapter 14. Cyclic Redundancy Check

14-1 Introduction

14-2 Theory

14-3 Practice

Chapter 15. Error-Correcting Codes

15-1 Introduction

15-2 The Hamming Code

15-3 Software for SEC-DED on 32 Information Bits

15-4 Error Correction Considered More Generally

Chapter 16. Hilbert's Curve

16-1 A Recursive Algorithm for Generating the Hilbert Curve

16-2 Coordinates from Distance along the Hilbert Curve

16-3 Distance from Coordinates on the Hilbert Curve

16-4 Incrementing the Coordinates on the Hilbert Curve

16-5 Non-Recursive Generating Algorithms

16-6 Other Space-Filling Curves

16-7 Applications

Chapter 17. Floating-Point

17-1 IEEE Format

17-2 Floating-Point To/From Integer Conversions

17-3 Comparing Floating-Point Numbers Using Integer Operations

17-4 An Approximate Reciprocal Square Root Routine

17-5 The Distribution of Leading Digits

17-6 Table of Miscellaneous Values

Chapter 18. Formulas For Primes

18-1 Introduction

18-2 Willans's Formulas

18-3 Wormell's Formula

18-4 Formulas for Other Difficult Functions

Answers To Exercises

Chapter 1: Introduction

Chapter 2: Basics

Chapter 3: Power-of-2 Boundaries

Chapter 4: Arithmetic Bounds

Chapter 5: Counting Bits

Chapter 6: Searching Words

Chapter 7: Rearranging Bits and Bytes

Chapter 8: Multiplication

Chapter 9: Integer Division

Chapter 10: Integer Division by Constants

Chapter 11: Some Elementary Functions

Chapter 12: Unusual Bases for Number Systems

Chapter 13: Gray Code

Chapter 14: Cyclic Redundancy Check

Chapter 15: Error-Correcting Codes.

Chapter 16: Hilbert's Curve

Chapter 17: Floating-Point

Chapter 18: Formulas for Primes

Appendix A. Arithmetic Tables for A 4-Bit Machine

Appendix B. Newton's Method

Appendix C. A Gallery of Graphs of Discrete Functions

C-1 Plots of Logical Operations on Integers

C-2 Plots of Addition, Subtraction, and Multiplication

C-3 Plots of Functions Involving Division

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

C-5 2D Plots of Some Unary Functions

Bibliography

Index

Footnotes

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 7

Chapter 8

Chapter 12

Chapter 14

Chapter 15

Chapter 16

Chapter 17

Chapter 18

Appendix B.

Notes:

Bibliographic Level Mode of Issuance: Monograph

Includes bibliographical references and index.

Description based on publisher supplied metadata and other sources.

ISBN:

9780133085006

0133085007

9780321842688

0321842685

OCLC:

825819424