Delight

**Second Edition (Current) **

This site is an adjunct to the book *Hacker's Delight*
(Addison-Wesley, 2003, 2012). It may become a forum for discussions about the
kind of algorithms that are in that book. There is no mechanism set up
yet for discussion threads, but if you send me email (see the bottom of
this page) I'll post it if it seems appropriate. Please also send email
if you find errors in the book.

There is nothing here about hacking in the sense of breaking into computers.

This web page is about the second edition of Hacker's Delight. If you're interested in material about the first edition, click here. Both editions are described on Amazon.com and BarnesAndNoble.com.

Usage permissions and restrictions

Table of Contents.

Foreword by Guy Steele

Chapter 2, Basics.

Errata
for the second edition, first printing.

Errata
for the second edition, second printing.

The second edition has been translated into Korean and is licensed for a translation into Chinese.

Click here for a directory to the C code
for the algorithms that appear in HD second edition. To download
*all* the code, click
here.
Download hdcodetxt.zip into a directory of your choice, and unzip it
there.

To unzip it in Windows XP, enter the complete file name, "hdcodetxt.zip," click File - Extract All... and select all defaults in the extraction wizard.

To unzip it in Windows 7, enter the complete file name, "hdcodetxt.zip," click "Extract all files" in the resulting window, and in the window that comes up, in the folder name, delete the last component ("hdcodetxt") and click "Extract."

Following one of the above procedures makes a directory named "hdcodetxt," containing about 83 files, plus another 17 in subdirectory "hilbert." If it looks ok you can erase hdcodetxt.zip. You might want to rename the files to delete the ".txt" suffix.

A *superoptimizer* is a program that makes a serious attempt at
finding optimal code, in the sense of a minimal number of instructions,
for a given function. It works by trying all sequences of computational
instructions of a given length, simulating each sequence for various
inputs, until it finds (stumbles on) a sequence that matches a given
user-defined function.

This site includes a relatively simple superoptimizer that's oriented toward RISC computers and is designed to be easy to tailor to a given instruction set. Click here to see the documentation.

To download the superoptimizer itself, including its documentation, click here. Download aha.zip into a directory of your choice, and unzip it there (as explained above for hdcodetxt.zip). You should get about eight files; the important ones are aha.c, abs.h, aha.pdf, make.bat, and Makefile. If it looks ok you can erase aha.zip.

Click here for a page that can be used to
compute the "magic numbers" and multiplicative inverses modulo
2^{32}. These numbers allow you to convert
division by constants into multiplications.

This file describes the theory
and practice of Montgomery multiplication. This is a technique for doing
"modular multiplication" (that is, given *a*, *b*, and
*m*, of computing *ab* mod *m*) that improves performance
when several multiplications are to be done with the same values of
*a*, *b*, and *m*. In particular, it is useful for
computing *a ^{n}* mod

C code for Montgomery multiplication with 64-bit data is given in the code section on this web site. This subject would be of interest only to specialists.

Here is some miscellaneous material that has not been incorporated elsewhere in this web site.

You might enjoy taking Marc LeBrun's Computist Quiz. Most problems are just for fun, but some are even practical! Guaranteed to sharpen your skills.

*Hacker's Delight*, Amazon.com

*Hacker's Delight*, Barnes & Noble

The Aggregate Magic Algorithms, 26 bit twiddling algorithms from Hank Dietz and others

The Assembly Gems page, tips for the x86 and M680x0, by John Eckerdal

Bit Twiddling Hacks, by Sean Anderson

HAKMEM, the famous memo is now computer readable! thanks to Henry Baker

Matters Computational: Ideas, Algorithms,
Source Code, by Jorg Arndt. LOTS of good stuff here. Also available at major book stores.

Plane Filling Curves, Hilbert's and Moore's, by Alexander Bogomolny

Plane Filling Curves: Peano's & Wunderlich's, by Alexander Bogomolny

Programmer's Heaven

Programming Pages of Jasper Neumann, an especially nice section on bit permutations

A Zillion Monkeys, much about programming, particularly about Intel x86 processors, by Paul Hsieh
Has a *huge* list of sites of interest to computer aficionados.

Fast string/integer conversions
SWAR (SIMD Within a Register) algorithms for these conversions

visitors since 1/24/2008