整数除法算法：关于维基版本的问题

Question

Wiki表示下面这个算法是长除法的一个版本。有谁知道数学上发生了什么 R 被左移，然后 R(0) 的最低有效位被设置为 N(i)？

我知道左移是2R，但是后面有点迷路

if D = 0 then error(DivisionByZeroException) end
Q := 0                  -- Initialize quotient and remainder to zero
R := 0                     
for i := n − 1 .. 0 do  -- Where n is number of bits in N
  R := R << 1           -- Left-shift R by 1 bit
  R(0) := N(i)          -- Set the least-significant bit of R equal to bit i of the numerator
  if R ≥ D then
    R := R − D
    Q(i) := 1
  end
end

Answer 1

本质上和我们在学校学过的“按角划分”的算法是一样的（不同国家有不同的表示法，我展示"Eurasia" one）

_176 |3_
 15   58
---   
 _26
  24
 ---   
   2

我们将被除数 (1) 的最高位放入（临时）余数中，并检查它是否大于除数。 1<3，所以我们实际上将 0 放入商中并使余数为 17 - 这是 1*10 + 7，二进制 R := R << 1; R(0) := N(i)

17>3，所以我们减去除数和商的最大可能位数的乘积。这里3*5，我们把5代入商，在R ≥ D的情况下商的二进制数位是1 (Q(i) := 1)

在第二步，我们将余数 2 乘以 10，然后加上下一个数字 6。在二进制版本中，等效为 R := R << 1; R(0) := N(i) 等等。

整数除法算法：关于维基版本的问题

Integer Division Algorithm: question on Wiki version

algorithm

binary

division

integer-division