Copyright
Foreword
Preface
Acknowledgments
Chapter 1. Introduction
Notation
Instruction Set and Execution Time Model
Chapter 2. Basics
Manipulating Rightmost Bits
Addition Combined with Logical Operations
Inequalities among Logical and Arithmetic Expressions
Absolute Value Function
Sign Extension
Shift Right Signed from Unsigned
Sign Function
Three-Valued Compare Function
Transfer of Sign
Decoding a "Zero Means 2**n" Field
Comparison Predicates
Overflow Detection
Condition Code Result of Add, Subtract, and Multiply
Rotate Shifts
Double-Length Add/Subtract
Double-Length Shifts
Multibyte Add, Subtract, Absolute Value
Doz, Max, Min
Exchanging Registers
Alternating among Two or More Values
Chapter 3. Power-of-2 Boundaries
Rounding Up/Down to a Multiple of a Known Power of 2
Rounding Up/Down to the Next Power of 2
Detecting a Power-of-2 Boundary Crossing
Chapter 4. Arithmetic Bounds
Checking Bounds of Integers
Propagating Bounds through Add's and Subtract's
Propagating Bounds through Logical Operations
Chapter 5. Counting Bits
Counting 1-Bits
Parity
Counting Leading 0's
Counting Trailing 0's
Chapter 6. Searching Words
Find First 0-Byte
Find First String of 1-Bits of a Given Length
Chapter 7. Rearranging Bits and Bytes
Reversing Bits and Bytes
Shuffling Bits
Transposing a Bit Matrix
Compress, or Generalized Extract
General Permutations, Sheep and Goats Operation
Rearrangements and Index Transformations
Chapter 8. Multiplication
Multiword Multiplication
High-Order Half of 64-Bit Product
High-Order Product Signed from/to Unsigned
Multiplication by Constants
Chapter 9. Integer Division
Preliminaries
Multiword Division
Unsigned Short Division from Signed Division
Unsigned Long Division
Chapter 10. Integer Division by Constants
Signed Division by a Known Power of 2
Signed Remainder from Division by a Known Power of 2
Signed Division and Remainder by Non-Powers of 2
Signed Division by Divisors greater than or equal to 2
Signed Division by Divisors less than or equal to -2
Incorporation into a Compiler
Miscellaneous Topics
Unsigned Division
Unsigned Division by Divisors greater than or equal to 1
Incorporation into a Compiler (Unsigned)
Miscellaneous Topics (Unsigned)
Applicability to Modulus and Floor Division
Similar Methods
Sample Magic Numbers
Exact Division by Constants
Test for Zero Remainder after Division by a Constant
Chapter 11. Some Elementary Functions
Integer Square Root
Integer Cube Root
Integer Exponentiation
Integer Logarithm
Chapter 12. Unusual Bases for Number Systems
Base -2
Base -1 + i
Other Bases
What Is the Most Efficient Base?
Chapter 13. Gray Code
Gray Code
Incrementing a Gray-Coded Integer
Negabinary Gray Code
Brief History and Applications
Chapter 14. Hilbert's Curve
A Recursive Algorithm for Generating the Hilbert Curve
Coordinates from Distance along the Hilbert Curve
Distance from Coordinates on the Hilbert Curve
Incrementing the Coordinates on the Hilbert Curve
Non-recursive Generating Algorithms
Other Space-Filling Curves
Applications
Chapter 15. Floating-Point
IEEE Format
Comparing Floating-Point Numbers Using Integer Operations
The Distribution of Leading Digits
Table of Miscellaneous Values
Chapter 16. Formulas for Primes
Introduction
Willans's Formulas
Wormell's Formula
Formulas for Other Difficult Functions
Appendix A. Arithmetic Tables for a 4-Bit Machine
Appendix B. Newton's Method
Bibliography