将大数除以2

Question

假设我有以下列表实现:

list=^listelement
listelement=record
    w:integer;
    next:list;
end;

列表表示十进制写的大数(列表1 - > 2 - > 3表示数字123).

我想要做的是将这样的数字转换为二进制表示.因此,最直接的方法是将数字除以2

问题是我很难用2算法实现除法.我理解基本的算法,例如这个 https://www.mathsisfun.com/long_division.html,但我想不出一种方法可以将其转换为代码

我将不胜感激

Answer 1

您将从左到右继续,将数字除以2.每次数字为奇数时,您都会将进位(10)传播到下一个数字.

示例:除以123

1除以2为0,进位= 10

2 + 10除以2是6,没有携带

3除以2是1,carry = 10

最后一次进位可以忽略不计.

结果:061.

carry= 0;
element= head;
WHILE element <> NIL DO
  BEGIN
    element^.w= element^.w + carry;
    IF ODD(element^.w) THEN carry= 10 ELSE carry= 0;
    element^.w= element^.w DIV 2;
    element= element^.next
  END.