Path: utzoo!utgpu!attcan!uunet!husc6!rutgers!att!ulysses!andante!alice!ark
From: ark@alice.UUCP (Andrew Koenig)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <8386@alice.UUCP>
Date: 3 Nov 88 16:28:25 GMT
References: <3105@hubcap.UUCP> <34112@XAIT.XEROX.COM> <1700@dataio.Data-IO.COM> <2730@hound.UUCP>
Organization: AT&T Bell Laboratories, Liberty Corner NJ
Lines: 27

In article <2730@hound.UUCP>, rkl1@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@europa.att.com