Exercises

Exercises 3.2 Exercises

1.

How many bits are required to store a single decimal digit?

Hint

Review Table 3.1.3.

Answer

Four bits. Note that six of the bit patterns are unused.

2.

Develop an algorithm for adding fixed-width integers in the binary number system.

Hint

There are only two digits in the binary number system, \(\binary{0}\) and \(\binary{1}\text{.}\)

Solution

\(\displaystyle carry_{0} = 0\)
For \(i = 0, \cdots, (N-1)\)
- sum\(_{i} = (x_{i} + y_{i} + carry_{i})\) % \(2\)
- carry\(_{i+1} = (x_{i} + y_{i} + carry_{i}) / 2\)

3.

Develop an algorithm for adding fixed-width integers in the hexadecimal number system.

Solution

\(\displaystyle carry_{0} = 0\)
For \(i = 0, \cdots, (N-1)\)
- sum\(_{i} = (x_{i} + y_{i} + carry_{i})\) % \(16\)
- carry\(_{i+1} = (x_{i} + y_{i} + carry_{i}) / 16\)

4.

Using the answer from Exercise 3.2.1, invent a code for storing two decimal digits in 32 bits. Using this code, does binary addition produce the correct results?

Solution

Using the bit patterns in Table 3.1.3, we could store one decimal digit in every four bits. That is, the lowest-order digit would be stored in bits 3–0, the next lower-order digit in bits 7–4, etc. For example, let's consider \(48 + 27\text{:}\)

	\(48_{10}\)	\(\rightarrow\)	\(\hex{00000048}_{16}\)
+	\(27_{10}\)	\(\rightarrow\)	\(\hex{00000027}_{16}\)
	\(75_{10}\)	\(\ne\)	\(\hex{0000006f}_{16}\)

Do Exercise 3.2.3 before performing the addition in hexadecimal.

5.

Develop an algorithm for subtracting fixed-width integers in the binary number system.

Hint

Remember that there are 10 digits in the decimal number system and 2 digits in the binary number system.

Solution

Subtracting \(y\) from \(x\text{.}\)

\(\displaystyle borrow = 0\)
For \(i = 0, \cdots, (N-1)\)
- If \(y_{i} \le x_{i}\)
  - difference\(_{i} = x_{i} - y_{i}\)
- Else
  - \(\displaystyle j = i + 1\)
  - While \((x_{j} = 0)\) and \((j \lt N)\)
    - \(\displaystyle j = j + 1\)
  - If \(j = N\)
    - \(\displaystyle borrow = 1\)
    - \(\displaystyle j = j - 1\)
    - \(\displaystyle x_{j} = x_{j} + 2\)
- While \(j \gt i\)
  - \(\displaystyle x_{j} = x_{j} - 1 \)
  - \(\displaystyle j = j - 1\)
  - \(\displaystyle x_{j} = x_{j} + 2\)
- difference\(_{i} = x_{i} - y_{i}\)

6.

Develop an algorithm for subtracting fixed-width integers in the hexadecimal number system.

Solution

Subtracting \(y\) from \(x\text{.}\)

\(\displaystyle borrow = 0\)
For \(i = 0, \cdots, (N-1)\)
- If \(y_{i} \le x_{i}\)
  - difference\(_{i} = x_{i} - y_{i}\)
- Else
  - \(\displaystyle j = i + 1\)
  - While \((x_{j} = 0)\) and \((j \lt N)\)
    - \(\displaystyle j = j + 1\)
  - If \(j = N\)
    - \(\displaystyle borrow = 1\)
    - \(\displaystyle j = j - 1\)
    - \(\displaystyle x_{j} = x_{j} + 16\)
- While \(j \gt i\)
  - \(\displaystyle x_{j} = x_{j} - 1 \)
  - \(\displaystyle j = j - 1\)
  - \(\displaystyle x_{j} = x_{j} + 16\)
- difference\(_{i} = x_{i} - y_{i}\)