Divisions with shifts

Andrew Koenig ark at alice.UucP
Sat Jan 11 08:33:21 AEST 1986


> Just shifting using an arithmetic shift may give the wrong answer, but
> you could correct the rounding and still get much faster execution like:
>
>	shiftRightArithmetic	register
>	branchIfPositive	label
>	increment		register
> label:
>
> so -23/2 = -23>>1 + 1 = 11101001>>2 + 1 = 11110100 + 1 = 11110101 = -11
> which is the right answer...
>
>					-Miles

Yet another example of why this problem is harder than it appears.
The algorithm suggested above gives the wrong answer whenever
the remainder from the division is 0.  Thus (-2>>1)+1 is (11111110>>1)+1
is 11111111+1 is 0.

Oh yes, 11101001>>2 + 1 is really 11111101, because addition binds
more tightly than shifting.



More information about the Comp.lang.c mailing list