Division

Integer division is slightly more complicated than multiplication, one of the differences is that most numbers will not give an exact result.

The simplest of all division algorithms is just counting how many times the divisor can be subtracted from the dividend, (result * divisor) + remainder should always give us the original dividend:

result = 0
do
  dividend = dividend - divisor
  result = result + 1
while (dividend >= 0)
remainder = dividend + divisor

The problem with this algorithm is that it is extremely slow when the dividend is a lot larger than the divisor.

The efficiency can be increased by subtracting some multiple of the divisor, by using 2ⁿ as the multiple we can use simple shifts to generate the required multiples.

divisorM = divisor

//Find the largest multiple that makes sense
do while ((dividend >> 1) > divisorM)
  divisorM = divisorM << 1
loop

//Do division
result = 0
do
  result = result << 1
  if (dividend - divisorM) >= 0 then 
    dividend = dividend - divisorM  
    result = result + 1 
  endif
  divisorM = divisorM >> 1
while (divisorM >= divisor)

remainder = dividend