Contents
1–2 Instruction Set and Execution Time Model
2–1 Manipulating Rightmost Bits
2–2 Addition Combined with Logical Operations
2–3 Inequalities among Logical and Arithmetic Expressions
2–7 Shift Right Signed from Unsigned
2–9 Three-Valued Compare Function
2–10 Transfer of Sign Function
2–11 Decoding a “Zero Means 2n” Field
2–14 Condition Code Result of Add, Subtract, and Multiply
2–16 Double-Length Add/Subtract
2–18 Multibyte Add, Subtract, Absolute Value
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
4–1 Checking Bounds of Integers
4–2 Propagating Bounds through Add’s and Subtract’s
4–3 Propagating Bounds through Logical Operations
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–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
8–2 High-Order Half of 64-Bit Product
8–3 High-Order Product Signed from/to Unsigned
8–4 Multiplication by Constants
9–3 Unsigned Short Division from Signed 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–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–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–23 A Circuit for Dividing by 3
CHAPTER 11. SOME ELEMENTARY FUNCTIONS
CHAPTER 12. UNUSUAL BASES FOR NUMBER SYSTEMS
12–4 What Is the Most Efficient Base?
13–2 Incrementing a Gray-Coded Integer
13–4 Brief History and Applications
CHAPTER 14. CYCLIC REDUNDANCY CHECK
CHAPTER 15. ERROR-CORRECTING CODES
15–3 Software for SEC-DED on 32 Information Bits
15–4 Error Correction Considered More Generally
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
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–4 Formulas for Other Difficult Functions
APPENDIX A. ARITHMETIC TABLES FOR A 4-BIT MACHINE
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