Title: Using Bit Patterns

Dr Martin Richards has a paper called "Backtracking Algorithms in MCPL using Bit Patterns and Recursion" (July 1997) on his website www.cl.cam.ac.uk/users/mr/, . MCPL is a typeless language and is a successor to BCPL, which inspired B and then C. BCPL and MCPL seem suited to bit pattern techniques because they guarantee 32-bit integers (bit patterns rely heavily on an integer being of the required size), but languages like C have other advantages as well as being more widely used and researched. Richards' bit pattern techniques deserve to be more widely known and not limited to MCPL (much as he likes it).

Richards' first example is a solution of the eight-queens (in fact N-queens) problem - count the number of ways that N queens can be placed on an NxN Chess board in such a way that no two are attacking each other. The obvious way is to place a queen on each row, checking for attacks as you do so; recursion can be used to go through all possibilities and a counter incremented when a valid one is found.

Richards has a very efficient way of doing this that takes advantage of the fact that parallel logic operations on registers (AND, OR etc) are usually cheap. He keeps track of the occupied columns using the bit pattern of a single integer, and tracks the occupied left and right diagonals with two more integers. For each row, he shifts them appropriately, ORs them to get the illegal squares, complements the result to get the legal ones and tries each bit in turn on the recursive call. (In one of his lecture courses he challenges the students to come up with a faster implementation in one of the backtracking-centred languages like Prolog; as far as I know nobody has succeeded.)

The main problem is that reading the source without comments is like reading assembler - you know exactly what the computer's doing but you have to work out why (this is a debugger's nightmare). In C++ you could use inline functions to make things clearer, for example:

inline int selectOneBitOf(int p) { return(p&-p); }
inline int removeOneBitFrom(int p) { return(p&(p-1)); }
inline int hashFromBit(int p) { return((p>>1)%29); }

(hashFromBit is a hash function to 29 values that are unique if only one of p's bits is a 1; other numbers to try are 2,4,5,9,11,13,19,25,37,53,59,61, 67. This is useful if you want to call a different function or something depending on which bit is set.)

In C you'd be stuck with macros (unless you want calling overhead) which means you have to be careful how they're used - macro arguments that are used twice are evaluated twice.

Richards gives several other bit pattern tech-niques in the paper, although many of them seem specific to the particular problems he is solving. The approach is useful when problems can be cast into a form involving small sets, which are then represented as bits in registers - the trouble in C is that assumptions about size can make the program rather architecture-dependent.

General problems are often unbounded - the N-queens program won't work with N bigger than the bits in an integer, but real applications might need more. This could be addressed by only using bit patterns for the special cases they can cope with, by splitting problems into parts small enough for them, or by using a C++ class that can handle arbitrary-length bit patterns (like the big integer classes but with logic) - this would lose the efficiency of keeping everything in single ints but could still gain something as the logical operations can be done several bits at a time.

Bit patterns could be a useful tool for your optimiser's toolbox. Prototyping algorithms with them might not be so good an idea - if your algorithm doesn't work and you're not a bit pattern expert, you may well not know whether it's your algorithm or your bit pattern techniques at fault, so it would be better to get the algorithm working without them to begin with and then add the bit patterns if you're prepared to spend the extra development time on the speed increase. Using the right algorithm in the first place, though, often makes a difference of several orders of magnitude.

Now, I wonder if we can twist Silas' arm into writing a series on bit pattern techniques. I also wonder if we can get someone to write about MCPL and what it has to offer that its cousin (once removed) C does not.