|
|
|
|
|
|
|
The answer is the sequence of remainders from last to first. Therefore, the decimal number 42 is 101010 in binary. |
|
|
|
|
|
|
|
|
It looks as though the problem can be implemented with a straightforward iterative algorithm. Each remainder is obtained from the MOD operation (% in C++), and each quotient is the result of the / operation. |
|
|
|
|
|
|
|
|
WHILE number > 0
Set remainder = number MOD 2
Print remainder
Set number = number / 2 |
|
|
|
|
|
|
|
|
|
Let's do a walk-through to test this algorithm. |
|
|
|
|
|
|
|
|
|
Answer:
(remainder from step |
|
|
|
| |
|
|
|
|
|
|
The answer is backwards! An iterative solution (using only simple variables) doesn't work. We need to print the last remainder first. The first remainder should be printed only after the rest of the remainders have been calculated and printed. |
|
|
|
|
|
|
|
|
In our example, we should print 42 MOD 2 after (42 / 2) MOD 2 has been printed. But this, in turn, means that we should print (42 / 2) MOD 2 after ((42 / 2) / 2) MOD 2 has been printed. Now this begins to look like a recursive definition. We can summarize by saying that, for any given number, we should print number MOD 2 after (number / 2) MOD 2 has been printed. This becomes the following algorithm: |
|
|
|
|
|
