Path: utzoo!utgpu!attcan!uunet!husc6!mailrus!purdue!decwrl!amdcad!crackle!tim
From: tim@crackle.amd.com (Tim Olson)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <23459@amdcad.AMD.COM>
Date: 4 Nov 88 01:52:26 GMT
References: <3105@hubcap.UUCP> <34112@XAIT.XEROX.COM> <1700@dataio.Data-IO.COM> <2730@hound.UUCP> <8386@alice.UUCP>
Sender: news@amdcad.AMD.COM
Reply-To: tim@crackle.amd.com (Tim Olson)
Organization: Advanced Micro Devices, Inc. Sunnyvale CA
Lines: 34
Summary:
Expires:
Sender:
Followup-To:

In article <8386@alice.UUCP> ark@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@crackle.amd.com)