book

Hacker’s Delight, Second Edition

Name: Hacker’s Delight, Second Edition
Author: Henry S. Warren
ISBN: 9780133084993

by Henry S. Warren

September 2012

Intermediate to advanced

512 pages

12h 41m

English

Addison-Wesley Professional

Read now

Unlock full access

Title Page
Copyright Page
Dedication Page
Contents
Foreword
Preface
Acknowledgments
Chapter 1. Introduction
1–1 Notation1–2 Instruction Set and Execution Time Model
Chapter 2. Basics
2–1 Manipulating Rightmost Bits2–2 Addition Combined with Logical Operations2–3 Inequalities among Logical and Arithmetic Expressions2–4 Absolute Value Function2–5 Average of Two Integers2–6 Sign Extension2–7 Shift Right Signed from Unsigned2–8 Sign Function2–9 Three-Valued Compare Function2–10 Transfer of Sign Function2–11 Decoding a “Zero Means 2**n” Field2–12 Comparison Predicates2–13 Overflow Detection2–14 Condition Code Result of Add, Subtract, and Multiply2–15 Rotate Shifts2–16 Double-Length Add/Subtract2–17 Double-Length Shifts2–18 Multibyte Add, Subtract, Absolute Value2–19 Doz, Max, Min2–20 Exchanging Registers2–21 Alternating among Two or More Values2–22 A Boolean Decomposition Formula2–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 23–2 Rounding Up/Down to the Next Power of 23–3 Detecting a Power-of-2 Boundary Crossing
Chapter 4. Arithmetic Bounds
4–1 Checking Bounds of Integers4–2 Propagating Bounds through Add’s and Subtract’s4–3 Propagating Bounds through Logical Operations

Chapter 5. Counting Bits
5–1 Counting 1-Bits5–2 Parity5–3 Counting Leading 0’s5–4 Counting Trailing 0’s
Chapter 6. Searching Words
6–1 Find First 0-Byte6–2 Find First String of 1-Bits of a Given Length6–3 Find Longest String of 1-Bits6–4 Find Shortest String of 1-Bits
Chapter 7. Rearranging Bits and Bytes
7–1 Reversing Bits and Bytes7–2 Shuffling Bits7–3 Transposing a Bit Matrix7–4 Compress, or Generalized Extract7–5 Expand, or Generalized Insert7–6 Hardware Algorithms for Compress and Expand7–7 General Permutations, Sheep and Goats Operation7–8 Rearrangements and Index Transformations7–9 An LRU Algorithm
Chapter 8. Multiplication
8–1 Multiword Multiplication8–2 High-Order Half of 64-Bit Product8–3 High-Order Product Signed from/to Unsigned8–4 Multiplication by Constants
Chapter 9. Integer Division
9–1 Preliminaries9–2 Multiword Division9–3 Unsigned Short Division from Signed Division9–4 Unsigned Long Division9–5 Doubleword Division from Long Division
Chapter 10. Integer Division By Constants
10–1 Signed Division by a Known Power of 210–2 Signed Remainder from Division by a Known Power of 210–3 Signed Division and Remainder by Non-Powers of 210–4 Signed Division by Divisors ≥ 210–5 Signed Division by Divisors ≤ –210–6 Incorporation into a Compiler10–7 Miscellaneous Topics10–8 Unsigned Division10–9 Unsigned Division by Divisors ≥ 110–10 Incorporation into a Compiler (Unsigned)10–11 Miscellaneous Topics (Unsigned)10–12 Applicability to Modulus and Floor Division10–13 Similar Methods10–14 Sample Magic Numbers10–15 Simple Code in Python10–16 Exact Division by Constants10–17 Test for Zero Remainder after Division by a Constant10–18 Methods Not Using Multiply High10-19 Remainder by Summing Digits10–20 Remainder by Multiplication and Shifting Right10–21 Converting to Exact Division10–22 A Timing Test10–23 A Circuit for Dividing by 3
Chapter 11. Some Elementary Functions
11–1 Integer Square Root11–2 Integer Cube Root11–3 Integer Exponentiation11–4 Integer Logarithm
Chapter 12. Unusual Bases for Number Systems
12–1 Base –212-2 Base –1 + i12–3 Other Bases12–4 What Is the Most Efficient Base?
Chapter 13. Gray Code
13–1 Gray Code13-2 Incrementing a Gray-Coded Integer13–3 Negabinary Gray Code13–4 Brief History and Applications
Chapter 14. Cyclic Redundancy Check
14–1 Introduction14–2 Theory14–3 Practice
Chapter 15. Error-Correcting Codes
15–1 Introduction15–2 The Hamming Code15–3 Software for SEC-DED on 32 Information Bits15–4 Error Correction Considered More Generally
Chapter 16. Hilbert’s Curve
16–1 A Recursive Algorithm for Generating the Hilbert Curve16–2 Coordinates from Distance along the Hilbert Curve16–3 Distance from Coordinates on the Hilbert Curve16–4 Incrementing the Coordinates on the Hilbert Curve16–5 Non-Recursive Generating Algorithms16–6 Other Space-Filling Curves16–7 Applications
Chapter 17. Floating-Point
17–1 IEEE Format17–2 Floating-Point To/From Integer Conversions17–3 Comparing Floating-Point Numbers Using Integer Operations17–4 An Approximate Reciprocal Square Root Routine17–5 The Distribution of Leading Digits17–6 Table of Miscellaneous Values
Chapter 18. Formulas For Primes
18–1 Introduction18–2 Willans’s Formulas18–3 Wormell’s Formula18–4 Formulas for Other Difficult Functions
Answers To Exercises
Chapter 1: IntroductionChapter 2: BasicsChapter 3: Power-of-2 BoundariesChapter 4: Arithmetic BoundsChapter 5: Counting BitsChapter 6: Searching WordsChapter 7: Rearranging Bits and BytesChapter 8: MultiplicationChapter 9: Integer DivisionChapter 10: Integer Division by ConstantsChapter 11: Some Elementary FunctionsChapter 12: Unusual Bases for Number SystemsChapter 13: Gray CodeChapter 14: Cyclic Redundancy CheckChapter 15: Error-Correcting CodesChapter 16: Hilbert’s CurveChapter 17: Floating-PointChapter 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 IntegersC–2 Plots of Addition, Subtraction, and MultiplicationC–3 Plots of Functions Involving DivisionC–4 Plots of the Compress, SAG, and Rotate Left FunctionsC–5 2D Plots of Some Unary Functions
Bibliography
Index
Footnotes
ForewordPrefaceChapter 2Chapter 3Chapter 4Chapter 5Chapter 7Chapter 8Chapter 12Chapter 14Chapter 15Chapter 16Chapter 17Chapter 18Answers To ExercisesAppendix B

Content preview from Hacker’s Delight, Second Edition

Chapter 10. Integer Division By Constants

On many computers, division is very time consuming and is to be avoided when possible. A value of 20 or more elementary add times is not uncommon, and the execution time is usually the same large value even when the operands are small. This chapter gives some methods for avoiding the divide instruction when the divisor is a constant.

10–1 Signed Division by a Known Power of 2

Apparently, many people have made the mistake of assuming that a shift right signed of k positions divides a number by 2^k, using the usual truncating form of division [GLS2]. It’s a little more complicated than that. The code shown below computes q = n ÷ 2^k, for 1 ≤ k ≤ 31 [Hop].

shrsi t,n,k-1 Form the integershri t,t,32-k 2**k ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Code: The Hidden Language of Computer Hardware and Software, 2nd Edition

Publisher Resources

ISBN: 9780133084993Purchase book

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Hacker’s Delight, Second Edition

by Henry S. Warren

Chapter 10. Integer Division By Constants

10–1 Signed Division by a Known Power of 2

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.