## CS 1401 Assignment #5

Date Assigned: Monday, September 25, or Tuesday, September 26, 2006.

Due Date: Monday, October 2, or Tuesday, October 3, 2006, before the beginning of your lab section.

Objective: The main objective of this assignment is to practice using loops.

Programming assignment: It is well known that computers use a binary system to represent integers. The following algorithm is used to convert a decimal positive integer n into the binary form: you divide n by 2, keep a remainder. Divide the result by 2, keep a remainder, etc. until we get 0. The remainders, when read bottom to top, form the desired binary number.

Write a program that, given an integer, uses the above algorithm to return a binary representation of this number (as a string).

Example: for n = 13, we have

```13 / 2 = 6 rem 1
6 / 2 = 3 rem 0
3 / 2 = 1 rem 1
1 / 2 = 0 rem 1
```
When we read the remainders from bottom to top, we get 1101, which is exactly the binary representation of 13.

Hint: originally, the division-result is 13, the string-so-far is empty. Within the loop, you divide the division-result by 2, compute the remainder, and depending on whether the remainder is 0 or 1, add the corresponding one-character string '0' or '1' to the left of the string-so-far.

For extra credit: write a program that transforms binary back into decimal. Main idea:

• start with the first (0th, in Java terms) bit of the string, and make value-so-far 0 or 1 depending on whether this bit is 0 or 1; then, delete this bit from the string;
• at any step, if you have on more bit, you double the value-so-far and add 0 or 1 to the resulting value;
• stop when there are no bits left.
Example: for the string 1101,
• the first bit is 1, so the value-so-far is 1 and the remaining string is 101;
• the remaining string is not empty, so we take the first bit of the remaining string, it is 1; we double the value-so-far, it is now 2 * 1 = 2, and add the value (1) corresponding to this bit, we now get 2 + 1 = 3; the remaining string is 01;
• the remaining string is not empty, so we take the first bit of the remaining string, it is 0; we double the value-so-far, it is now 2 * 3 = 6, and add the value (0) corresponding to this bit, we now get 6 + 0 = 6; the remaining string is 1;
• the remaining string is not empty, so we take the first bit of the remaining string, it is 1; we double the value-so-far, it is now 2 * 6 = 12, and add the value (1) corresponding to this bit, we now get 12 + 1 = 13; the remaining string is empty.
Since the remaining string is empty, the value-so-far (13) is returned as the result.

Homework assignment: on a separate sheet of paper, solve Ex. 6, 10, 18, and 24 at the end of Chapter 5.

Deliverables: as instructed by your TA.