# Only because I could...

I managed to write an algorithm that would perform 16-bit long division using just the ADD, AND and NOT operators of the LC-3 machine simulator.

Just to make sure everyone understands, I am teaching an assembly language class at UVU and the class uses the LC-3 machine simulator. It's nice, but it has a grand total of three arithmetic operators: ADD, AND and NOT. Subtraction is done by performing a 2s complement inversion on the number being subtracted, then performing addition. Division could be performed by counting the number of subtractions of the denominator from the numerator, but this method scales horribly. Long division would be nice, but you probably noticed the lack of a bitwise shift operator in my list of arithmetic operators.

This stymied me for a while, until last night when I was reminded that left-shifting bits will multiply a number by two, thus adding a number to itself is a fine simulation of the left-shift operator. This is actually so stinking obvious that I feel the need for penance for my obvious act of slothfulness.

So, here's what I did. One LC3 register was maintained for the original numerator and would be rotated through the range of 16-bits. Another register would maintain a bitmask to allow only the bits that had been rotated. This would allow me to subtract the denominator from only the rotated bits. For every successful positive subtraction I would shift in a bit the last register - the quotient. When the bitmask became negative (the high-bit was set), then I was done.

Again, obvious. Here's the code I wrote in about 30 minutes at 11:00pm last night:

```
NOT R3, R1
ADD R3, R3, #1 ; R3 will be the subtracting denominator
ADD R1, R0, #0 ; R1 will be the rotated numerator
AND R0, R0, #0 ; R0 will be the advancing quotient
AND R2, R2, #0 ; R2 will be the numerator bitmask
DIVROLL ADD R2, R2, #0 ; First, are we done? Test if the bitmask is negative
BRn DIVSIGN
ADD R2, R2, R2 ; Shift mask left and add one
ADD R2, R2, #1
ADD R0, R0, R0 ; Shift the quotient left
ADD R4, R1, R1 ; Roll numerator
ADD R1, R1, #0
BRzp DIVRLBT
ADD R4, R4, #1 ; Roll the high bit into the low
DIVRLBT ADD R1, R4, #0
AND R4, R1, R2 ; Mask
ADD R4, R4, R3 ; Test
BRn DIVROLL
ADD R1, R1, R3 ; Subtract from numerator and set a bit in the quotient
ADD R0, R0, #1
BRnzp DIVROLL ; And do it again
```

Special thanks to Yale Patt of The University of Texas at Austin for providing me the information for my "Oh Duh" moment (it's in hint#2).