Skip to main content
\(\newcommand{\doubler}[1]{2#1} \newcommand{\binary}{\mathtt} \newcommand{\hex}{\mathtt} \newcommand{\octal}{\mathtt} \newcommand{\prog}{\mathtt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section3.2Exercises

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

  • \(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

  • \(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{0000007f}_{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{.}\)

  • \(borrow = 0\)

  • For \(i = 0, \cdots, (N-1)\)

    • If \(y_{i} \le x_{i}\)

      • difference\(_{i} = x_{i} - y_{i}\)

    • Else

      • \(j = i + 1\)

      • While \((x_{j} = 0)\) and \((j \lt N)\)

        • \(j = j + 1\)

      • If \(j = N\)

        • \(borrow = 1\)

        • \(j = j - 1\)

        • \(x_{j} = x_{j} + 2\)

    • While \(j \gt i\)

      • \(x_{j} = x_{j} - 1 \)

      • \(j = j - 1\)

      • \(x_{j} = x_{j} + 2\)

    • difference\(_{i} = x_{i} - y_{i}\)

6

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

Solution

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

  • \(borrow = 0\)

  • For \(i = 0, \cdots, (N-1)\)

    • If \(y_{i} \le x_{i}\)

      • difference\(_{i} = x_{i} - y_{i}\)

    • Else

      • \(j = i + 1\)

      • While \((x_{j} = 0)\) and \((j \lt N)\)

        • \(j = j + 1\)

      • If \(j = N\)

        • \(borrow = 1\)

        • \(j = j - 1\)

        • \(x_{j} = x_{j} + 16\)

    • While \(j \gt i\)

      • \(x_{j} = x_{j} - 1 \)

      • \(j = j - 1\)

      • \(x_{j} = x_{j} + 16\)

    • difference\(_{i} = x_{i} - y_{i}\)