> Perl uses the following for hashing strings; while it contains a
> multiply (* 33), it could be converted into a shift and an add pretty
> easily.

The FNV multiplications can also be converted into shifts and adds relatively
easily; i.e. the constants in question are relatively sparse in 1 bits
(0x1000193 and 0x100000001B3, if I remember correctly); 6 shifts in the 32-bit
case, with two of the shifts being byte-shifts.  Granted, it's not as fast as
a single shift and add, but multiply-free hardware could still probably do
it with custom assembly code much faster than a general-purpose multiply
routine.