CS274: Computer Architecture - Computer Arithmetic: Addition and Subtraction
Activity Goals
The goals of this activity are:
- To add binary numbers including carry
- To identify overflow
- To use two's complement to negate and subtract values
The Activity
Directions
Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.
Model 1: Addition in Binary
| Carry |
0 |
0 |
1 |
0 |
0 |
|
| A = 5 |
|
0 |
0 |
1 |
0 |
1 |
| B = 6 |
|
0 |
0 |
1 |
1 |
0 |
| Sum = 11 |
X |
0 |
1 |
0 |
1 |
1 |
Questions
- What is 0 + 0 in binary? How about 0 + 1, 1 + 0, and 1 + 1?
- What should happen if you encounter 1 + 1 in terms of the carry bit? What should be done with the carry bit?
- What is 1 + 1 + 1?
- With a partner, choose two arbitrary values and ask the other to add them together in binary. Check your partner's work.
Model 2: Two's Complement of Binary Numbers and Subtraction
| A = 2 |
0 |
0 |
0 |
0 |
1 |
0 |
| One's Complement of A |
1 |
1 |
1 |
1 |
0 |
1 |
| B = Two's Complement of A |
1 |
1 |
1 |
1 |
1 |
0 |
| One's Complement of B |
0 |
0 |
0 |
0 |
0 |
1 |
| A = Two's Complement of B |
0 |
0 |
0 |
0 |
1 |
0 |
Questions
- The two's complement of a value is the inverse of the value's bits, plus one. Why not use the one's complement to negate a value? That is, what if we simply flipped the bits and did not add one to the result?
- What is the most significant bit of a negative number using this system? A positive number?
- Why not simply set the most significant bit to 1 for negative numbers, and not bother flipping the bits?
- Subtract
6 - 4 by converting 4 to its two's complement value, and then adding them together.
Model 3: Overflow
| Carry |
0 |
1 |
1 |
0 |
0 |
|
| A = 5 |
|
0 |
0 |
1 |
0 |
1 |
| B = 14 |
|
0 |
1 |
1 |
1 |
0 |
| Sum = |
X |
1 |
0 |
0 |
1 |
1 |
Questions
- Given that the most significant bit of the sum is 1, this is a negative number. Using two's complement, determine this value's magnitude. Is it correct?
- Why is the result negative when we added two positive numbers together?
- In your own words, how can you tell that overflow occurred?
- How can you obtain overflow when subtracting two values? Provide an example.
- What is the largest 4 bit signed positive value that you can represent, and what is the smallest?
- What is the largest 32 bit signed positive value that you can represent, and what is the smallest?
Model 4: Key Formulas and Concepts Recap
A quick-reference recap of the key rules from this activity. Try to reproduce each one from memory before peeking!
Key Rules and Formulas
- Single-bit addition facts:
0+0=0; 0+1=1+0=1; 1+1=0 carry 1; 1+1+1=1 carry 1.
- Two's complement negation = invert the bits, then add 1. Micro-example (4 bits):
2 = 0010; invert to get 1101; add 1 to get 1110 = -2. Negating again: invert 1110 to 0001, add 1 to get 0010 = 2.
- Subtraction is addition:
A - B = A + (~B + 1). Micro-example (4 bits): 6 - 4 = 0110 + 1100 = (1)0010 = 2, discarding the carry out of the top bit.
- Sign bit: the most significant bit is 1 for negative values, 0 for non-negative values.
- Range of an n-bit signed value:
-2^(n-1) to 2^(n-1) - 1. Micro-example: 4 bits hold -8..7; 32 bits hold -2147483648..2147483647. The range is asymmetric because zero uses one of the "positive" patterns.
- Overflow detection rules: adding two positives that yields a "negative" sum, or adding two negatives that yields a "positive" sum, is overflow. Adding values of opposite signs can never overflow. Micro-example (4 bits):
5 + 6 = 0101 + 0110 = 1011, which reads as -5: overflow!
- Overflow in subtraction:
A - B overflows exactly when A + (-B) overflows, e.g. (4 bits) 7 - (-2) = 7 + 2 = 9 > 7: overflow.
Carry: 0 1 1 0 0
A = 5: 0 1 0 1
B = 6: 0 1 1 0
=========
Sum: 1 0 1 1 <-- sign bit is 1 but we added two positives: overflow!
Glossary
| Term | Meaning |
|---|
| Carry (in/out) | The extra 1 passed to the next column when a column's sum exceeds 1 |
| One's complement | The value with every bit inverted |
| Two's complement | One's complement plus 1; the standard encoding of negative integers |
| Sign bit (MSB) | The most significant bit; 1 means negative in two's complement |
| Overflow | A result too large or too small to fit in the available bits, indicated by an impossible sign |
| Magnitude | The absolute value of a number; for a negative two's complement value, take the two's complement to read it |
| Signed vs. unsigned | Whether the bit pattern is interpreted with a sign (range -2^(n-1)..2^(n-1)-1) or without (0..2^n - 1) |
Questions
- Without looking, negate 5 in 4-bit two's complement, then compute 3 - 5 by addition and verify the answer is -2.
Submission
I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.