Freitag, 15. Mai 2015

What happens? From decimal to binary...

program WhatHappens(input, output);
var
    a, b, c: Integer;
begin
    b := 0;
    c := 1;
    readln(a);
    while a > 0 do
    begin
        b := b+c*(a mod 2);
        a := a div 2;
        c := c*10;
    end;
    writeln(b)
end.

This little program converts a decimal number to its binary representation.


Let's have a look at the algorithm.

An integer a is read from the command line.
Let's suppose the user entered the number 7.

Every iteration the value of the variable a is divided by two (7, 3, 1, 0) as long as it is greater than 0 and the value of c is incremented by ten.
What about b, the binary representation of the entered decimal number.


Asking Google how to convert a decimal number into its binary representation that's what I found:
"Converting decimal numbers to binaries is nearly as simple: just divide by 2. [...] To do this conversion, I need to divide repeatedly by 2, keeping track of the remainders as I go."
The given example converts decimal 357 into 101100101 binary:

357 / 2 = 178 (Remainder: 1)
178 / 2 = 89 (Remainder: 0)
89 / 2 = 44 (Remainder: 1)
44 / 2 = 22 (Remainder: 0)
22 / 2 = 11 (Remainder: 0)
11 / 2 = 5 (Remainder: 1)
5 / 2 = 2 (Remainder: 1)
2 / 2 = 1 (Remainder: 0)
1 / 2 = (Remainder: 1)

Written from bottom to top...

1 / 2 = (Remainder: 1)
2 / 2 = 1 (Remainder: 0)
5 / 2 = 2 (Remainder: 1)
11 / 2 = 5 (Remainder: 1)
22 / 2 = 11 (Remainder: 0)
44 / 2 = 22 (Remainder: 0)
89 / 2 = 44 (Remainder: 1)
178 / 2 = 89 (Remainder: 0)
357 / 2 = 178 (Remainder: 1)

...the "sum" of the remainders is the binary value 101100101 of 357.

This looks familiar to the given algorithm.

a is divided by two...check.
a mod 2 is the remainder...check.
b keeps track of the remainders...check.
c takes care of the position (1, 10, 100, 1000) within the remainder's "sum"...check.

Back to the conversion of decimal 7 to 111 binary:
First iteration: remainder is 1 (7 mod 2), times 1 (initial value of variable c), plus 0 (initial value of variable b); result 1
Second iteration: remainder is 1 (3 mod 2), times 10 (c got multiplied by 10), plus the remainder from iteration 1, which is 1; result 11
Third iteration: remainder is 1 (1 mod 2), times 100 (c got multiplied by 10 again), plus the remainder from iteration 2, which is 11; result 111

The value of b is therefore built starting with the last digit of the binary representation and then working its way left to the first digit.

Keine Kommentare:

Kommentar veröffentlichen