Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!bpa!cbmvax!jesup
From: jesup@cbmvax.commodore.com (Randell Jesup)
Newsgroups: comp.arch
Subject: Re: Integer Multiply/Divide
Message-ID: <9229@cbmvax.commodore.com>
Date: 6 Jan 90 01:03:55 GMT
References: <84768@linus.UUCP> <4057@brazos.Rice.edu> <9193@cbmvax.commodore.com> <22705@princeton.Princeton.EDU>
Reply-To: jesup@cbmvax.commodore.com (Randell Jesup)
Organization: Commodore, West Chester, PA
Lines: 27

In article <22705@princeton.Princeton.EDU> nfs@notecnirp.UUCP (Norbert Schlenker) writes:
>In article <9193@cbmvax.commodore.com> jesup@cbmvax.commodore.com (Randell Jesup) writes:
>>	Easy solution: x/2^n = (x >> n) + (x & 1 & (bit 31 of x)).  Of course,
>>the >> operation must be "arithmetic" and not "logical" (i.e. sign-extending).
>
>This doesn't work.  Consider -10/2^3, which results in -2.

	Yes, this has been pointed out to me by mail.  I grabbed my "divide by
2" algorithm without checking it.  The more general form is:

	if ((x < 0) && (x & "n-ones"))
		result = (x >> n) + 1;
	else
		result = x >> n;

"n-ones" means n ones filled in starting at low order working up.  Also could
be some funky bit-field test instruction; however this would be hard to code
in C for a variable n (constant n isn't bad, and may well still be faster than
integer divide).  The original formula for x/2 has the advantage of not
requiring any branches.

Hopefully I haven't stuck my foot any further down my throat... :-)

-- 
Randell Jesup, Keeper of AmigaDos, Commodore Engineering.
{uunet|rutgers}!cbmvax!jesup, jesup@cbmvax.cbm.commodore.com  BIX: rjesup  
Common phrase heard at Amiga Devcon '89: "It's in there!"