About the Book
Preface
Caveat Emptor: The cost of software maintenance
increases with the square of the programmer's
creativity.
First Law of Programmer Creativity, Robert
D. Bliss, 1992
This is a collection of small programming
tricks that I have come across over many years. Most of them will work
only on computers that represent integers in two's-complement form. Although
a 32-bit machine is assumed when the register length is relevant, most
of the tricks are easily adapted to machines with other register sizes.
This book does not deal with large tricks
such as sophisticated sorting and compiler optimization techniques. Rather,
it deals with small tricks that usually involve individual computer words
or instructions, such as counting the number of 1-bits in a word. Such
tricks often use a mixture of arithmetic and logical instructions.
It is assumed throughout that integer overflow
interrupts have been masked off, so they cannot occur. C, Fortran, and
even Java programs run in this environment, but Pascal and ADA users beware!
The presentation is informal. Proofs are
given only when the algorithm is not obvious, and sometimes not even then.
The methods use computer arithmetic, "floor" functions, mixtures of arithmetic
and logical operations, and so on. Proofs in this domain are often difficult
and awkward to express.
To reduce typographical errors and oversights,
many of the algorithms have been executed. This is why they are given in
a real programming language, even though, like every computer language,
it has some ugly features. C is used for the high-level language because
it is widely known, it allows the straightforward mixture of integer and
bit-string operations, and C compilers that produce high-quality object
code are available.
Occasionally, machine language is used.
It employs a three-address format, mainly for ease of readability. The
assembly language used is that of a fictitious machine that is representative
of today's RISC computers.
Branch-free code is favored. This is because
on many computers, branches slow down instruction fetching and inhibit
executing instructions in parallel. Another problem with branches is that
they may inhibit compiler optimizations such as instruction scheduling,
commoning, and register allocation. That is, the compiler may be more effective
at these optimizations with a program that consists of a few large basic
blocks rather than many small ones.
The code sequences also tend to favor small
immediate values, comparisons to zero (rather than to some other number),
and instruction-level parallelism. Although much of the code would become
more concise by using table lookups (from memory), this is not often mentioned.
This is because loads are becoming more expensive relative to arithmetic
instructions, and the table lookup methods are often not very interesting
(although they are often practical). But there are exceptional cases.
Finally, I should mention that the term
"hacker" in the title is meant in the original sense of an aficionado of
computers--someone who enjoys making computers do new things, or do old
things in a new and clever way. The hacker is usually quite good at his
craft, but may very well not be a professional computer programmer or designer.
The hacker's work may be useful or may be just a game. As an example of
the latter, more than one determined hacker has written a program which,
when executed, writes out an exact copy of itself1. This is the sense in
which we use the term "hacker." If you're looking for tips on how to break
into someone else's computer, you won't find them here.
H. S. Warren, Jr.
Yorktown, New York
February 2002
Related Books
Introduction to Computer Programming Courses
(Intro
to Computer Programming)
Table of Contents
Preface.
1. Introduction.
Notation.
Instruction Set and Execution Time
Model.
2. Basis.
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.
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.
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.
4. Arithmetic Bounds.
Checking Bounds of Integers.
Propagating Bounds through Adds and
Subtracts.
Propagating Bounds through Logical
Operations.
Signed Bounds.
5. Counting Bits.
Counting 1-bits.
Parity.
Counting Leading 0's.
Counting Trailing 0's.
6. Searching Words.
Find First 0-Byte.
Find First String of 1-Bits of a Given
Length.
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.
8. Multiplication.
Multiword Multiplication.
High-Order Half of 64-Bit Product.
High-Order Product Signed from/to
Unsigned.
Multiplication by Constants.
9. Integer Division.
Preliminaries.
Multiword Division.
Unsigned Short Division from Signed
Division.
Unsigned Long Division.
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 >= 2.
Signed Division by Divisors #= -2.
Incorporation into a Compiler.
Miscellaneous Topics.
Unsigned Division.
Unsigned Division by Divisors >= 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.
11. Some Elementary Functions.
Integer Square Root.
Integer Cube Root.
Integer Exponentiation.
Integer Logarithm.
12. Unusual Bases for Number Systems.
Base -2.
Base -1 + i.
Other Bases.
What is the Most Efficient Base?
13. Gray Code.
Gray Code.
Incrementing a Gray Coded Integer.
Negabinary Gray Code.
Brief History and Applications.
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.
15. Floating-Point.
IEEE Format.
Comparing Floating-Point Numbers Using
Integer Operations.
The Distribution of Leading Digits.
Table of Miscellaneous Values.
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.
Index. |
