Efficient coding considered harmful?

[Andrew Koenig]

In article <2730 at hound.UUCP>, rkl1 at hound.UUCP (K.LAUX) writes:
> 	I'm suprized that noone has questioned the validity of shifting
> instead of dividing by (powers of) 2.
> 
> 	What about the difference between Logical and Arithmetic shifts?
> If you want to divide, then divide!  A lot of compilers are smart enough
> to implement the divide as a shift, but only where appropriate.

This correctly picks up a simple problem, but misses a deeper one:
even if you use an arithmetic shift, shifting right one bit is
still not equivalent to dividing by 2 if the dividend is negative,
at least on machines that round the quotient toward zero.

Example: on a 32-bit 2's complement machine, -1 is represented as
0xFFFFFFFF.  Shifting right one bit arithmetically still gives
0xFFFFFFFF.  Dividing -1 by 2, though, gives 0.

It is true, however, that shifting an unsigned integer right is
equivalent to dividing it by a power of 2.  I would expect a good
C compiler to recognize this equivalence and replace a division
by a corresponding shift where applicable.

Section 7.5 (page 90) of `C Traps and Pitfalls' has more to say
about shifting and division.
-- 
				--Andrew Koenig
				  ark at europa.att.com