henry@utzoo.UUCP (Henry Spencer) (01/03/86)
> > >Almost but not quite true. A compiler CANNOT normally replace a divide > > >by a right-shift if it is an integer divide. This is because a right > > >shift of a negative integer is not the same as a divide. > > > > However most useable processors provide arithmetic shifts which will give > > the right result even if it is a signed divide. > > The first is correct, the second is WRONG. -1/2 is 0 not -1. Ah, but is it? It depends on whose definition of integer division you use. The problem is that arithmetic shifts and conventional divide instructions disagree. Neither is inarguably "wrong". Consider: what we want is a mapping <a,b> -> <q,r>, where q*b+r = a and |r|<|b|. When r != 0, there is more than one such mapping. For positive numbers there is general consensus on which is wanted: keep everything positive. When negative numbers enter the scene explicitly, it's not so clear. Even with a constraint of being consistent with the positive-numbers rule, there is an ambiguity: do you truncate the quotient toward zero, or toward negative infinity? For negative numbers, these give different answers. Truncation toward negative infinity is more highly regarded by mathematicians (ask a mathematician what the value of "-1 mod 2" is, and then figure out which kind of division that is consistent with), and is what two's-complement arithmetic shifts do. Truncation toward zero is what most languages and machines do, following the lead of Fortran and the 709. Hence the mess. There are exceptions. CLU defined integer division as negative-infinity style, and the manual noted (as a bug!) that some implementations did it the other way. The 32032 gives you your choice. The value of -1/2 depends on whether you mean -(1/2) [definitely 0] or (-1)/2 [it depends]. -- Henry Spencer @ U of Toronto Zoology {allegra,ihnp4,linus,decvax}!utzoo!henry
thomas@kuling.UUCP (Thomas H{meenaho) (01/10/86)
In article <6263@utzoo.UUCP> henry@utzoo.UUCP (Henry Spencer) writes: >> > >Almost but not quite true. A compiler CANNOT normally replace a divide >> > >by a right-shift if it is an integer divide. This is because a right >> > >shift of a negative integer is not the same as a divide. >> > >> > However most useable processors provide arithmetic shifts which will give >> > the right result even if it is a signed divide. >> >> The first is correct, the second is WRONG. -1/2 is 0 not -1. > [long story about different ways to divide negative numbers] Enough about my comment on arithmetic shifts. I thought the problem was the sign bit which is lost if one uses a logical shift. x x However the idea of adding 2 -1 when dividing a negative number with 2 seems like a win. -- Thomas Hameenaho, Dept. of Computer Science, Uppsala University, Sweden Phone: +46 18 138650 UUCP: thomas@kuling.UUCP (...!{seismo,mcvax}!enea!kuling!thomas)