Skip to main content

Section D.2 Exercise Sheet 2

Exercises Exercises

1. Sign and Zero Extension.

Complete the following table by extending the given bit sequences \(b\) to a sequence \(b'\) such that \(b'\) has length 6. Ensure that the condition on top of the corresponding column holds. \(\\\)

\(b\) \(\quad\buintp{b}=\buintp{b'}\) \(\quad\bsintp{b}=\bsintp{b'}\) \(\quad\buintp{b}=\bsintp{b'}\)
0010
1001
0111
1111
1011
202207281550

202204221400
Solution.
\(b\) \(\quad\buintp{b}=\buintp{b'}\) \(\quad\bsintp{b}=\bsintp{b'}\) \(\quad\buintp{b}=\bsintp{b'}\)
0010 000010 000010 000010
1001 001001 111001 001001
0111 000111 000111 000111
1111 001111 111111 001111
1011 001011 111011 001011

2. Shifts.

As discussed in the lecture you can express the multiplication of a bit sequence with \(2\) using a left shift. Analogously it is possible to express division by \(2\) using shifts.

  1. For any given bit sequence \(b\) state a bit sequence \(b'\) such that \(\buintp{b'}=\buintp{b}\cdot 4\text{.}\)
    \(b\) \(\quad\buintp{b'}=\buintp{b}\cdot 4\) \(\quad\buintp{b'}=\buintp{b}\cdot 8\)
    0001001
    0000011
    0001110
  2. Complete the following table.

    \(b\) \(\quad\buintp{b'}=\lfloor\frac{\buintp{b}}{4}\rfloor\) \(\quad\bsintp{b'}=\lfloor\frac{\bsintp{b}}{4}\rfloor\)
    101101
    010011
    101010
    111111
202207281550

202204221400
Solution.
  1. Shift the bit sequences two times or three times, respectively, to the left:
    \(b\) \(\quad\buintp{b'}=\buintp{b}\cdot 4\) \(\quad\buintp{b'}=\buintp{b}\cdot 8\)
    0001001 0100100 1001000
    0000011 0001100 0011000
    0001110 0111000 1110000
  2. Shift the bit sequence two times to the right. For signed bit sequences the most significant bit stays the same and depending on it the sequence is padded with \(0\) or \(1\text{.}\)

    \(b\) \(\quad\buintp{b'}=\lfloor\frac{\buintp{b}}{4}\rfloor\) \(\quad\bsintp{b'}=\lfloor\frac{\bsintp{b}}{4}\rfloor\)
    101101 001011 111011
    010011 000100 000100
    101010 001010 111010
    111111 001111 111111

3. Signed and Unsigned Arithmetics.

  1. State the decimal representation for the following binary numbers:

    1. \(\displaystyle \langle 1010 \rangle\)

    2. \(\displaystyle [ 1010 ]\)

    3. \(\displaystyle \langle 010 \rangle\)

    4. \(\displaystyle [010]\)

    5. \(\displaystyle \langle 1111 \rangle\)

    6. \(\displaystyle [1111]\)

    7. \(\displaystyle [01111]\)

  2. Compute:

    1. \(\displaystyle \langle 111 \rangle + \langle 1110 \rangle\)

    2. \(\displaystyle \langle 111 + 1110 \rangle\)

    3. \(\displaystyle \langle 111 +_4 1110 \rangle\)

    4. \(\displaystyle [1110] - [1100]\)

    5. \(\displaystyle [1110 - 1100]\)

    6. \(\displaystyle [1110 -_4 1100]\)

    7. \(\displaystyle [100110] + [10000]\)

    8. \(\displaystyle [100110 + 10000]\)

    9. \(\displaystyle [100110 +_5 10000]\)

    10. \(\displaystyle [100110 +_6 10000]\)

  3. Compute

    • \([1101]+[0011]\text{,}\)

    • \([1101 + 0011]\) and

    • \([1101 +_4 0011]\text{.}\)

    What do you notice? How can you explain these results?

202207281550

202204221400
Solution.
    1. \(\displaystyle \langle 1010 \rangle = 10\)

    2. \(\displaystyle [ 1010 ] = -6\)

    3. \(\displaystyle \langle 010 \rangle = 2\)

    4. \(\displaystyle [010] = 2\)

    5. \(\displaystyle \langle 1111 \rangle = 15\)

    6. \(\displaystyle [1111] = -1\)

    7. \(\displaystyle [01111] = 15\)

    1. \(\displaystyle \langle 111 \rangle + \langle 1110 \rangle = 7 + 14 = 21\)

    2. \(\displaystyle \langle 111 + 1110 \rangle = \langle 10101 \rangle = 21\)

    3. \(\displaystyle \langle 111 +_4 1110 \rangle = \langle 0101 \rangle = 5\)

    4. \(\displaystyle [1110] - [1100] = -2 - -4 = 2\)

    5. \(\displaystyle [1110 - 1100] = [1110 + 0100] = [10010] = -14\)

    6. \(\displaystyle [1110 -_4 1100] = [0010] = 2\)

    7. \(\displaystyle [100110] + [10000] = -26 + -16 = -42\)

    8. \(\displaystyle [100110 + 10000] = [110110] = -10\)

    9. \(\displaystyle [100110 +_5 10000] = [10110] = -10\)

    10. \(\displaystyle [100110 +_6 10000] = [110110] = -10\)

    • \(\displaystyle [1101]+[0011] = -3 + 3 = 0\)

    • \(\displaystyle [1101 + 0011] = [10000] = -16\)

    • \(\displaystyle [1101 +_4 0011] = [0000] = 0\)

    The numbers are congruent modulo 16 and we witness an overflow using \(+_4\text{.}\)

4. Compute.

We consider the interpretation bit sequences as unsigned and signed numbers. Complete the following table. \(\\\)

\(\qquad b \in\Bit^8\) \(\qquad\buintpb{b}{16}\) \(\qquad\buintp{b}\) \(\qquad\bsintp{b}\)
\(01101111\)
\(\mathrm{0xab}\)
127
-128
\(11001001\)
\(\mathrm{0xff}\)
64
127
202207281550

202204221400
Solution.
\(\qquad b \in\Bit^8\) \(\qquad \buintpb{b}{16}\) \(\qquad \buintp{b}\) \(\qquad \bsintp{b}\)
\(01101111\) \(\mathrm{0x6f}\) 111 111
\(10101011\) \(\mathrm{0xab}\) 171 -85
\(01111111\) \(\mathrm{0x7f}\) 127 127
\(10000000\) \(\mathrm{0x80}\) 128 -128
\(11001001\) \(\mathrm{0xc9}\) 201 -55
\(11111111\) \(\mathrm{0xff}\) 255 -1
\(01000000\) \(\mathrm{0x40}\) 64 64
\(01111111\) \(\mathrm{0x7f}\) 127 127

5. Shifts.

  1. State an expression of bit operations that produces the bit sequence

    \begin{equation*} 0^{n-(j-i+1)}a_j\ldots a_i \end{equation*}

    given a bit sequence \(a = a_{n-1}\ldots a_0\text{,}\) where \(i \lt j \lt n\text{.}\) In other words, the expression should extract the bit sequence \(a_j\ldots a_i\text{.}\)

  2. State an expression that computes

    \begin{equation*} a_{i-1}\ldots{}a_{0}b_{n-1}\ldots{}b_i \end{equation*}
    given bit sequences \(a = a_{n-1}\ldots{}a_0\text{,}\) \(b = b_{n-1}\ldots{}b_0\) and an index \(i\in[0,n-1]\text{.}\) Use only bit operations on bit sequences of length \(n\text{.}\)

  3. Give an expression that multiplies a bit string \(a\) with \(4\text{,}\) \(5\) and \(31\text{,}\) respectively.

202207281550

202204221400
Solution.
  1. Since we have \(n\gt j \gt i\text{,}\) the bit sequence has the form \(a_{n-1}\ldots{}a_j\ldots{}a_i\ldots{}a_0\text{.}\) To extract \(a_j\ldots{}a_i\) we have to remove the bits left of \(a_j\) and move the sequence to the very right. To remove the bits left of \(a_j\text{,}\) we do a left shift by \(n - 1 - j\text{.}\) Then do a right shift by \(n - 1 - j + i\) (undo the left shift plus the shift by \(i\)). The final expression is:

    \begin{equation*} \underbrace{(a \bsll_n (n-1-j))}_{\text{result of left shift}} \bsrl_n (\underbrace{(n-1-j)}_{\text{undo left shift}} + \underbrace{i}_{\text{shift to the end}}) \end{equation*}
  2. \(a\) is shifted to the left by \(n - i\) and \(b\) is shifted to the right by \(i\text{.}\) Now we can compose \(a\) and \(b\) using \(\bor_n\text{,}\) because both are padded by zeros on right or left, respectively. The expression is:

    \begin{equation*} (a \bsll_n n-i) \bor_n (b \bsrl_n i) \end{equation*}
  3. The idea is to disassemble the desired multiplication into a sum of multiplications by powers of \(2\text{,}\) since these can be computed using bit shifts.

    • \(\displaystyle a\bsll_n 2\)

    • \(5 = 4 + 1 = 2^2 + 1\text{,}\) thus \((a\bsll_n 2) +_n a\)

    • \(31 = 16 + 8 + 4 + 2 + 1 = 2^3 + 2^2 + 2^1 + 2^0\text{,}\) thus

      \begin{equation*} (a \bsll_n 4) +_n (a \bsll_n 3) +_n (a \bsll_n 2) +_n (a \bsll_n 1) +_n a. \end{equation*}

      Alternatively, use \(-_n\) (\(31 = 32-1\)):

      \begin{equation*} (a \bsll_n 5) -_n a \end{equation*}

6. The Signbit.

Proof for all bit strings \(b_{n-1}\ldots b_0\in\Bit^n\text{:}\)

\begin{equation*} b_{n-1} = 1 \text{ if and only if } \bsintp{b} \lt 0. \end{equation*}
202207281550

202204221400
Solution.

Let \(b\in\Bit^n.\)

\(\Rightarrow\)”:
\begin{equation*} \begin{array}{rll} [b] \amp= -\buintp{b_{n-1}} \times 2^{n-1} + \buintp{b_{n-2} \cdots b_0}\amp\\ \amp= -2^{n-1} + \buintp{b_{n-2} \cdots b_0} \amp| b_{n-1} = 1\\ \amp\lt 0 \amp|\buintp{b_{n-2} \cdots b_0} \lt 2^{n-1}\\ \end{array} \end{equation*}
\(\Leftarrow\)”:

If \(\bsintp{b}\lt 0\) then we have \(b{n-1} = 1\) since \(b_{n-1}\) is the only negative summand.

7. ASCII.

The ASCII character set includes the following 95 printable characters:

!"#$%&'()*+,-./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
`abcdefghijklmnopqrstuvwxyz{|}~

and 33 non-printable control characters. In total there are 128 ASCII characters. Usually they are coded using one byte per character. The defining table is in the appendix of the lecture notes.

A text is a sequence of characters. You can express a text as a sequence of bytes where every character is represented by one byte. The end of a character sequence is conventionally marked with a byte of value 0. Such a sequence of bytes is called C string or ASCIIZ character sequence.

  1. Why do we need character encoding?

  2. What character encodings do you know?

  3. Do you need the complete byte to encode ASCII characters or would less bits be sufficient?

  4. Consider the following ASCIIZ character sequence:

    \begin{equation*} \texttt{072 097 108 108 111 032 087 101 108 116 033 013 010 000} \end{equation*}

    Translate the character sequence into a readable format. You can use the ASCII table in the appendix.

  5. We interpret the encoding as a bijection \(\mathbb{A}\rightarrow[0,127]\) between the set of ASCII characters and the interval \([0,127]\text{.}\)

    State an expression that

    1. returns the ASCII code of a number \(d\in[0,9]\text{.}\)

    2. returns the ASCII code of a upper-case letter, given the position \(p\in[0,25]\) of the specific letter in the alphabet (A has position 0).

    3. returns the ASCII code of a lower-case letter, given the the ASCII code of the corresponding upper-case letter.

    4. switches the upper-case/lower-case of a letter. Do not use neither addition nor subtraction nor conditionals.

202207281550

202204221400
Solution.
    • necessity of a representation of human readable characters as a bit string

    • standardized communication

  1. ASCII, UTF-8, Unicode, morse, QR-Code, ...

  2. 7 Bit are sufficient for ASCII characters.

  3. “Hallo Welt!”

    Remark: LF (“line feed”) is used on Unix and Unix-like operating systems (e.g. Linux, FreeBSD, macOS) to mark a line break. DOS and Windows operating systems on the other hand use CR LF (“carriage return”, “line feed”) to encode a line break. This has historic reasons related to typewriters.

    1. The ASCII code of the number \(0\) is 48 and the numbers \(1-9\) are listed consecutively. Thus, we add \(48\) to get the corresponding ASCII code:

      \begin{equation*} d + 48 \text{ where } d\in[0,9] \end{equation*}

    2. The upper-case letters are listed consecutively beginning at ASCII code 65. Thus, we add \(65\) to our positional index:

      \begin{equation*} p + 65 \text{ where } p\in [0,25] \end{equation*}

    3. The lower-case letters are listed consecutively beginning \(32\) positions behind the upper-case letters. Thus, we add 32 to our input:

      \begin{equation*} b + 32 \text{ where } b\in[65,90] \end{equation*}

    4. If you examine the binary representation of the ascii codes of upper-case and lower-case letters, you notice that for any given letter the only difference between the upper-case and lower-case instances is at bit number 5. Let \(b\) be any valid ASCII code of a letter, then we have:

      • \(\displaystyle b\,\&\, 32 = 00000000 \Rightarrow b \text{ is an upper-case letter}\)

      • \(\displaystyle b\,\&\, 32 = 00100000 \Rightarrow b \text{ is a lower-case letter}\)

      To switch between upper-case and lower-case, you can invert bit number \(5\) using \(\bxor\text{:}\)

      \begin{equation*} b\bxor 32 \text{ where } b\in[65,90]\cup[97,122] \end{equation*}

8. Mips - First steps on MARS.

Do your first steps with MARS:

  1. Load the number \(5\) into the register $t0.

  2. Load the number \(11\) into the register $t1.

  3. Store the result of the addition of both numbers in registers $t2.

  4. Subtract the number in register $t0 from the number in register $t1 and store the result in $t3

  5. Subtract the same numbers in reverse order and store the result in $t4.

  6. Print the last result.

  7. Override the registers $t2 - $t4 with the value 0 without using li. Find 2 different possibilities.

202207281550

202204221400
Solution.
  1. li $t0 5

  2. li $t1 11

  3. add $t2 $t1 $t0

  4. sub $t3 $t1 $t0

  5. sub $t4 $t0 $t1

  6. li $v0 1

    move $a0 $t4

    syscall

  7. Three options:

    • move $t2 $zero

    • addiu $t3 $zero 0

    • sub $t4 $t4 $t4

9. Iterative Euclidian Algorithm.

Translate the following function written in pseudo code into a MIPS function:

EUCLID(a,b)
  while b != 0
    h = a mod b
    a = b
    b = h
  return a

202207281550

202204221400
Solution.

How to solve this task:

  1. First, define the function EUCLID. It gets two arguments.

  2. The function uses in total 3 variables. In Mips they will be stored in registers. We assign registers for each variable:

    a $a0
    b $a1
    h $t0
    Since a and b are arguments they have to be in the corresponding registers. h is a local variable, thus it should reside in a register for temporary values.

  3. Since there is a loop in the program we have to write code that ensures that the “body” of the loop is executed repeatedly as long as the condition at the “head” of the loop is satisfied. You can either put the check of the loop condition in front of or behind the body of the loop. In the latter case you have to jump there before the initial execution of the loop.

  4. The body of the loop we have to implement the modulo computation and the re-assignments of a and b. This can be implemented using rem and move.

  5. Finally, it is important to return from the function. It is essential to move the return value to the designated register $v0. Otherwise a function calling “EUCLID” has no way to retrieve the result.

condition at the beginning:

EUCLID:
loop:
  beqz $a1 end
  rem $t0 $a0 $a1
  move $a0 $a1
  move $a1 $t0
  b loop
end:
    move $v0 $a0
  jr $ra

condition at the end:

EUCLID:
  b condition
loop:
  rem $t0 $a0 $a1
  move $a0 $a1
  move $a1 $t0
condition:
  bnez $a1 loop
end:
  move $v0 $a0
  jr $ra

10. Execution Protocols.

Consider the following Mips program:

.text
# 6 in $a0
# 3 in $a1
start:
  beq $a0  $zero a0iszero
loop:
  beq $a1  $zero a1iszero
  bgt $a0 $a1    mid
  sub $a1 $a1    $a0
  b    loop
mid:
  sub $a0 $a0    $a1
  b    loop
a0iszero:
  add $a0 $a0    $a1
a1iszero:
  and $v0 $v0    $zero
  or   $v0 $v0    $a0
Since your Mips interpreter is currently not available and you need to know what this programs computes, you have to write down an execution protocol. The code has been loaded to the address 0x00400000 in memory.

  1. Complete the following execution protocol. State the content for every relevant register for every step until the program terminates.

    Step $v0 $a0 $a1 pc
    1. 6 3 0x00400000
    2. ... ... ... ...

  2. State a mathematical definition

    \begin{equation*} f(a, b) = \begin{cases} \amp \\ \dots \amp \\ \amp \\ \end{cases} \end{equation*}
202207281550

202204221400
Solution.
  1. The complete execution protocol:

    Step $v0 $a0 $a1 pc
    1. 6 3 0x00400000
    2. 6 3 0x00400004
    3. 6 3 0x00400008
    4. 6 3 0x00400014
    5. 3 3 0x00400018
    6. 3 3 0x00400004
    7. 3 3 0x00400008
    8. 3 3 0x0040000c
    9. 3 0 0x00400010
    10. 3 0 0x00400004
    11. 3 0 0x00400020
    12. 0 3 0 0x00400024
    13. 3 3 0 0x00400028

  2. Euclidean algorithm to compute the greatest common divider:

    \begin{equation*} \mathrm{gcd}(a, b) = \begin{cases} a \amp \text{ wenn } b = 0 \\ b \amp \text{ wenn } a = 0 \\ \mathrm{gcd}(a - b, b) \amp \text{ wenn } a > b \\ \mathrm{gcd}(a, b - a) \amp \text{ wenn } b \geq a \end{cases} \end{equation*}