H<SUP>a</SUP><SUB>c</SUB><SUP>k</SUP><SUB>e</SUB><SUP>r</SUP>'<SUB>s</SUB> Delight (reposted)

I read an interesting book some time ago that I meant to review but never got around to. The book is called Hackers Delight, and its a compendium of little boolean tricks. The book is heavy going, with mathematical equations a-plently that briefly revived previously dormant parts of my brain from my engineering degree. Here is an excerpt from quite early on (p.18 - section 2-6)

2-6 Shift Right Signed from Unsigned

If your machine does not have the shift right signed instruction, it may be computed using the formulas shown below. The first formula is from [GM], and the second is based on the same idea. Assuming the machine has mod 64 shifts, the first formulas hold for 0 =< n =< 31 and the last holds for 0 =< n =< 63. The last formula holds for any n if by “holds“ we mean “treats the shift amount to the same modulus as does the logical shift“. When n is a variable, each formula requires five or six instructions on a basic RISC.

((x + 0x80000000) >>u n) - (0x80000000 >>u n)

t <- 0x80000000 >>u n; ((x >>u n) (+) t) - t

…and so on…

Clearly this ‘aint Windows for Dummies. It deals with pretty low-level stuff like registers and instructions, with the occasional C program thrown in for good measure. If you’re used to working at a higher level of abstraction then this might not be the book for you. Each page that I read took me several hours to mentally “digest”, and I did not complete the book. For people doing performance-critical stuff or optimizing compilers I’m sure there are some rich veins of gold in here. I didn’t manage to find the operation for setting the bozo bit, but I’m sure it is in there.