Efficient coding considered harmful?

[Tim Olson]

In article <8386 at alice.UUCP> ark at alice.UUCP (Andrew Koenig) writes:
| 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.

A good compiler can also recognize a signed integer divided by a power
of 2, and use the following trick:

	;f(int a, unsigned b)
	;{
	;       int i, j;
	;
	;       i = a/2;
	        srl     gr121,lr2,31	; copy sign bit of a into lsb
	        add     gr121,gr121,lr2	; add sign bit to a
	        sra     gr120,gr121,1	; now we can divide by 2 (sra!)
	;       j = b/2;
	        srl     gr121,lr3,1	; b is unsigned -- just shift
	;       return i+j;
	;}

	-- Tim Olson
	Advanced Micro Devices
	(tim at crackle.amd.com)