Bit Hacks & Superoptimizers

Computers tend to shift bits and add numbers faster than they multiply or divide. Because this is the case one kind of speed optimization involves replacing multiplications and divisions with shifts and adds. For example, since (x*5) = (x*4 + x), one might replace (x*5) with ((x<<2)+x).

There are many clever optimizations that can be done by twiddling bits. Excellent sites on the subject include Sean Anderson's Bit Twiddling Hacks, The Aggregate Magic Algorithms by Hank Dietz, et al. and Hacker's Delight by Henry S. Warren, Jr.

A while back, I had the idea of writing a program to search for bit hacks. Given a simple function y = f(x), are there any interesting sets of machine instructions capable of emulating the function?

Given the speed of today's machines, much like a chess program, a simple algorithm could take millions of stabs at the problem each second. Add some decent pruning, I figured, and one might be in business.

Recently I learned there's a word for the object of my imagination--it's called a superoptimizer. The Wikipedia page on superoptimization has some decent links at the end of it.

At this point, I think it's worth pointing out a rule:

If you think of a good idea that's outside your area of expertise, someone else has already thought of it.

If I were naive, I'd claim ownership of that rule, but I'm sure somebody else has said that too.

I discovered my lack of originality while persuing Warren's Hacker's Delight web site. On the site he includes source code for a superoptimizer he's written called Aha! (code, docs).

It's easy to get it running. Compile the C code and implement the function for which you're seeking a bit hack. Finally, specify the number of operations allowed (recommendation: stay below five).

Also, if you'd like some puzzles, another good I found on Warren's site is this Computist Quiz.