Why Does The Division Alorithim Need [Register Size] + 1 Iterations Following this flow diagram for division hardware I made a program to "simulate" division on $N^+$.

# 4 bit version
def div(dividend, divisor)
  quotient = 0
  remainder = dividend
  divisor &lt;&lt;= 4

  for i in 1..5
    remainder -= divisor
    if remainder &gt;= 0
      quotient &lt;&lt;= 1
      quotient |= 1
    else
      remainder += divisor
      quotient &lt;&lt;= 1
    end
    divisor &gt;&gt;= 1
  end

  return quotient
end


What I don't understand is why there needs to be an "extra" iteration of the loop. If the divisor is being shifted down the register by 1, and the register is say 64 bits, then it would take 64 iterations to clear the register. Or in my case 4. However without that extra step the algorithm does not produce the correct result. Why is that?
"Why is that?"

Because divisor &lt;&lt;= 4 means original_divisor * (2**4), where I use original_divisor to denote the value of divisor when you began computing div(dividend, divisor). 

Every time you do divisor &gt;&gt;= 1, you divide that divisor by 2. So you will get original_divisor * (2**3), original_divisor * (2**2), original_divisor * (2**1), original_divisor * (2**0). 

Notice there are 5 of them, corresponding to original_divisor times $2^4, 2^3, 2^2, 2^1, 2^0$ respectively or 16,8,4,2,1 respectively. You should have noticed how 4 is changed to 5 by now. There are 4 possible shifts to the left, by 4 bits, by 3 bits, by 2 bits and by 1 bit. There is also a non-shift, or shift by 0 bit.

What you have experienced is the most famous/infamous error in computer programming, off-by-one error or off-by-one errors. I must have made this error hundreds if not thousands of times. 

Just in case you have not heard of the most famous joke in computer programming, here it is. "There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors." Or a shorter version, "There are two kinds of errors, off by one errors".