Can someome explain how arithmetic works?

From: John Wilson <wilson_at_dbit.dbit.com>
Date: Fri Jun 2 11:48:09 2000

On Fri, Jun 02, 2000 at 05:52:12AM -0700, Daniel A. Seagraves wrote:
>Need this for my emulator, and nobody can explain to me how it works, and
>I can't find any documentation that's useful to me. Specifically, I need stuff
>like "you shift left and then check the last bit" etc. etc. Basically, I have
>a bunch of ones and zeroes and I have to know how to add/subtract/multiply/
>divide with them.

I'll assume you mean integer math.

ADD -- I hope I get this right:

For each bit, you have the two input bits, plus one sum output, and also one
carry in and one carry out. For the LSB, carry in is zero.

The sum output is the XOR of all three inputs (A, B, Cin), i.e. a change in
any input will toggle it. The Cout bit is set any time 2 or more of the
three inputs are set, so whatever that works out to (the OR of the three
possible ANDs would do it, but maybe there's an easier way).

SUB:

This is done by adding, with one of the inputs (hmm, is "subtrahend" the
word???) negated. Two's complement negation is done by complementing all the
bits and then adding one. And you can add the one by playing with the Cin bit
to the LSB (my mind is going blank, I can't think whether it has to be 1 or 0,
the sense of the carry is inverted when subtracting in this way).

MUL:

This is unsigned, for signed you have to take the absolute value and then
negate the result if the XOR of the input sign bits is 1.

It works exactly like multiplication by hand, except that you do it in binary,
which means you're just multiplying by 0 or 1 so the whole multiplication table
can be summed up with the AND operation:

- init sum to 0
- cycle through all the bits in A (doesn't matter which order), and for each
  bit that's a 1, add in B shifted left by that number of places. So really,
  just AND all the bits of B with that bit, shift it left to the same position,
  and add it to the sum.
- you're done

DIV:

Once again this is unsigned, signed DIV instructions typically do funny things
with the sign of the remainder so check that carefully. Again it works just
like long division by hand, only in binary. So instead of wondering how many
times the divisor (?) goes into the dividend (?), you just wonder whether it
goes in at *all*, since you know the answer for each bit will just be 0 or 1.
So you can do it with a comparator and a subtractor, or you can always subtract
and decide whether to keep the result depending on whether it borrowed:

- init remainder to 0
- for all bits in the dividend, shift one bit left, filling the LSB with a 0
  and shifting the bit out of the MSB into the LSB of the remainder (you
  lose the MSB but it's always 0)
- if the remainder is .GE. the divisor, subtract the divisor from the
  remainder and change the LSB of the (shifted) dividend from 0 to 1 (i.e.
  INC it)

When you're done, the remainder is correct, and what was the dividend is now
the quotient. You could have assembled the quotient in its own register (since
you're generating it one bit at a time), but those LSBs of the dividend are
never used again so this is a cute way to do it all with one shift, and leads
to a very short routine in PDP-11 code (11 instructions IIRC).


Floating point */+- is exactly the same, but you have to worry about adding
and removing leading 1s (in formats that do that), chopping vs. rounding of the
LSB, and fixing the exponents to match. MUL and DIV are actually the easiest,
since all you have to do is add or sub the exponents and then do the integer
* or / operation on the mantissa, you can normalize it again in just one
or two shifts. With + and - you have to worry about shifting to align the
binary points before you start, and if the exponents are different by more
than the size of the mantissa there will be no overlap at all so you have
to ignore one or the other argument, depending on the FPU's rounding rules.
Once you align the points, do the + or -, and now you have to worry about
shifting left to re-normalize.

John Wilson
D Bit
Received on Fri Jun 02 2000 - 11:48:09 BST