Dividing a large number by 2

Question

let's say I have the following implementation of a list:

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

and a list represents a large number written decimally (a list 1 -> 2 -> 3 represents the number 123).

What I want to do is to transform such a number into binary representation. So, the eastiest way to do this required dividing a number by 2

The problem is I'm having a hard time implementing the division by 2 algorithm. I understand the basic algorithms such as this one https://www.mathsisfun.com/long_division.html, but I can't think of a way to translate that into code

I would appreciate some help

Answer 1

You will proceed from left to right, dividing the digits by two. Every time a digit is odd, you will propagate a carry (10) to the next digit.

Example: divide 123

1 divided by 2 is 0, carry = 10

2 + 10 divided by 2 is 6, no carry

3 divided by 2 is 1, carry = 10

The last carry can be ignored.

Result: 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.