CS 208 s21 — Learning Block #5

Table of Contents

1 Warmup

What base-10 integers do these 8-bit quantities represent using two's complement?1

  • 0b11111111
  • 0b00001111

2 Two's Complement Arithmetic Practice

Verify that binary addition produces the correct two's complement result for these expressions:2

  • \(-2 + -3\)
  • \(2 + -3\)

2.1 Additive inverse

Important that for all \(x\), the bit representation of \(x\) and the bit representation of \(-x\) sum to 0 (\(mod\ 2^w\)). That is, it had better be the case that \(x + (-x) = 0\) (throwing away any bits that carry out off the left side) Find the 8-bit negative encodings for these three bit vectors and verify that the sum of the two is 0:3

  • 0b00000001
  • 0b00000010
  • 0b11000011

Additive inverses are well behaved for two's complement. We'll see how to quickly find the additive inverse in binary in Friday's topic.

3 Sign Extension

Which of the following 8-bit numbers has the same signed (2's complement) value as the 4-bit number 0b1100?4 (spaces added for readability)

  • 0b 0000 1100
  • 0b 1000 1100
  • 0b 1111 1100
  • 0b 1100 1100

4 Practice

  1. CSPP practice problems 2.25 and 2.26
    • These highlight the practical application of understanding integer representations
  2. CSPP practice problem 2.29 (p. 93)
    • They use \(+\) to mean "normal" addition (not modular) and \(+_5^t\) to mean 5-bit two's complement addition
    • The case refers to the for possibilities in Figure 2.24
      1. \(x + y\) is negative and \(x +_5^t y\) overflows to a positive result
      2. \(x + y\) is negative and \(x +_5^t y\) does not overflow (also negative)
      3. \(x + y\) is positive and \(x +_5^t y\) does not overflow (also positive)
      4. \(x + y\) is positive and \(x +_5^t y\) overflows to a negative result

Footnotes:

1

Convert these bit vectors to decimal integers using two's complement

  • 0b11111111 = -1
  • 0b00001111 = 15
2

Verify binary addition produces the correct result:

  • \(-2 + -3 =\) 0b1110 + 0b1101
  1 1 1 0
+ 1 1 0 1
1 1 0 1 1
_ 1 0 1 1

final result: 0b1011 = \(-5\)

  • \(2 + -3 =\) 0b0010 + 0b1101
  0 0 1 0
+ 1 1 0 1
  1 1 1 1

final result: 0b1111 = \(-1\)

3

Find the additive inverses, verify the sum is 0:

  • 0b00000001 = 1, inverse is \(-1\) = 0b11111111
  1 1 1 1 1 1 1 1
+ 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
_ 0 0 0 0 0 0 0 0
  • 0b00000010 = 2, inverse is \(-2\) = 0b11111110
  1 1 1 1 1 1 1 0
+ 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0
_ 0 0 0 0 0 0 0 0
  • 0b11000011 = \(-61\), inverse is \(61\) = 0b00111101
  1 1 0 0 0 0 1 1
+ 0 0 1 1 1 1 0 1
1 0 0 0 0 0 0 0 0
_ 0 0 0 0 0 0 0 0
4

What is the 8-bit equivalent of 0b1100 (\(-4\))

  • 0b 0000 1100 is 12
  • 0b 1000 1100 is \(-116\)
  • 0b 1111 1100 is \(-4\) (correct answer)
  • 0b 1100 1100 is \(-52\)