Problem 2: Nasturtiums are Nice

For each 4 point problem below, write the letter(s) of table entries that answer the question. Assume that you are using a byte-addressable, Little Endian machine, and objects of size x must be x-byte aligned. All the potential answers are 16 bit words with the MSB on the left and the LSB on the right.

For your convenience, the words are given in both Hexadecimal and Binary. The decimal column is there if you want to use it, but you need not do so. If you don't like any of the answers below, choose ``O'' for Other, and write down a number you like better-no number, no credit.

(Note: A 3 point non-refundable deduction WILL be assessed if you don't follow these instructions.)

Label	Hex	Binary	Decimal Value
A	0009	$0000\;\;0000\;\;0000\;\;1001$
B	7FF9	$0111\;\;1111\;\;1111\;\;1001$
C	8001	$1000\;\;0000\;\;0000\;\;0001$
D	FFFF	$1111\;\;1111\;\;1111\;\;1111$
E	8009	$1000\;\;0000\;\;0000\;\;1001$
F	FFF9	$1111\;\;1111\;\;1111\;\;1001$
O	Other	you choose	or no credit

1. Which item is equivalent to the same base 10 number when it is interpreted as either a sign-magnitude (SM) number or a 2's complement (TC) number.

   Answer: This problem determines whether or not you realize that the msb (most significant bit) is the sign bit when interpreting a bit pattern as either a sign-magnitude number or a 2's complement number.

   Positive numbers are identical using sign-magnitude and 2's complement. So, only A and B are positive numbers.

   And, as always in one of my courses, if you prefer to make your problem a short answer question, an answer of Other, and a correct bit pattern earns full credit as well.

2. Suppose that item E above ($8009_{16}$) is interpreted as a SM number. Which item corresponds to the 2's complement representation of the same number?

   Answer: Item E is the SM version of -9. One way to get the 2's complement version of -9 is to start with a 16 bit +9 in 2's complement, which is what item A is. First take the 1's complement of item A-that gives a 16 bit string with 1's everywhere except the two outer-most bits of the lowest-order nybble, which are zero, shown below. Then, add a 1 to the least significant bit position, to get the final result, FFF7, which is absolutely NOT in the table. So, the correct answer is Other, FFF7.

   Binary	Hex	Comment
   1000 0000 0000 1001	1009	-9 in SM
   0000 0000 0000 1001	0009	+9 in SM, TC, Unsigned Binary
   1111 1111 1111 0110	FFF6	1's complement of +9
   1111 1111 1111 0111	FFF7	-9 in TC (also 2's complement of +9)

   note: The most common (wrong) answer was a result of taking the 2's complement of -9 in SM (1000 0000 0000 1001) to get -9 in TC, instead of starting with +9 (0000 0000 0000 1001) and taking the 2's complement, as shown above. The next most common (wrong) answer was item F, which is -7 in TC, and NOT -9 in TC.

3. Which item is the result when the 16-bit 2's complement representation of $-61_{10}$ is added to the 16-bit 2's complement representation of $52_{10}$?

   Answer: There's an easy way to do this, and a hard way. Who you are depends on which is which.

   The question did not ask you to convert anything to 2's complement and add; merely to produce the answer that you would get if you had done so. The allegedly easy way is to compute the sum of -61 and 52 in base 10. Hopefully, you can get -9. But, if you didn't, we forgive that math error at a cost of 1 point. Then, you have to realize that -9 in 2's complement was the same answer as from the previous problem, and you use the answer from problem 2. Again, another place for error. So, you match your (wrong) part 2 answer, you don't get whacked for those points again. For example, the most common wrong answer for this problem was item E, which is -9 in SM, not -9 in 2's complement (TC). Others gave me F, which is the TC form of -7.

   If you do it the hard way, then you did not read the problem carefully. It did not ask you to convert each number to its 2's complement representation (ick), do the math, and hopefully get the correct bit pattern. However, if you did do the math and get the correct bit pattern, which is NOT in the table, then you are done-just write Other next to it. If you didn't get the right bit pattern, then I had to figure out how you erred, and grade based on that. Typically, a critical mistake is worth 2 of the 4 points off. So, maybe the hard way is the easy way; or not. But these are just two ways to get acceptable answers.

4. Pick two items that result in overflow when one is added to the other. Be sure to include any assumptions necessary to assure that your answer is correct.

   Answer: As nearly the last part of Problem 2, you should expect to have to think a little bit. Fortunately, some of you did. Essentially, the assumption you made was worth half credit for the problem.

   As always, it's legal to write Other, and give me a pair of numbers, such as adding zero to zero . I'd give you credit, but I'd make sure that the next time I asked a question similar to this one, I'd remove Other as an option for this part alone.

   At any rate, even some of you who understood that I could interpret the bit strings in the table as unsigned binary in one part, and then as 2's complement or sign(ed)-magnitude in another, still forgot that the definition of overflow is different for unsigned binary numbers than it is for 2's complement or sign magnitude numbers.

   Here are the rules, the rulings and stuff you must know.

   • In unsigned binary, you have overflow when a '1' is carried out of the most significant bit (msb) position. So, to check your answer, take the two bit strings whose sum you claim produces an overflow condition, and see if that happens. If a '1' (one) is carried out, then you have to write down ``assuming unsigned binary'' as the way the bit strings are interpreted to get full credit.

   • In sign(ed) magnitude, you have overflow when adding two positive numbers when there is a carry of '1' into the msb position-that's the same as adding two positive numbers and getting a negative number. Again, you'd have to write your assumed representation to get full credit.

   • In two's complement, you cannot have overflow when adding numbers of differing signs. But, you can have overflow when the numbers have the same sign-meaning adding a positive to a positive; adding a negative and negative; subtracting a negative from a positive; or subtracting a positive from a negative. But, overflow in 2's complement is not characterized by a carry out of 1 from the msb position. Many correct computations cause a carry out of 1 to occur from the msb because of the manner in which bit-strings are assigned a numerical value in 2's complement. The bit-strings corresponding to the largest numbers when unsigned binary is used have the same bit pattern as the negative numbers of least magnitude (size).

     For example, adding -1 and -1 in 2's complement (two bit patterns consisting of all 1's) causes a carry of 1 to come out of the msb (most significant bit) position, but the resulting bit string is -2 in 2's complement (a bit pattern with 1's in all positions except that corresponding to the lsb position. If you don't understand this, please write it down, and try to follow the text. If you still don't get it, ask for help...from a fellow student..from a TA......from anyone whom I appear to know from another course or from outside of school.

     Okay, now how can you tell that a sum has overflowed in 2's complement? Why it's simple: if you XOR (exclusive-or) the sign of numbers being added together (they match, remember?) with the the sign bit of the sum, and the answer is '1', then you have overflow. For example, take the biggest positive number in two's complement-a zero in the msb, and the remaining bits all 1 (one). Add two of them together. There is no carry out from the msb position, but the sum has a 1 (one) in the msb, meaning we just added two positive numbers and produce a negative one. Furthermore, the sign bit of a positive (well, non-negative) number, 0 XOR 1, where the 1 is the sign bit of the alleged sum, is also 1, showing that our overflow test works. The sum of those two numbers is too big to fit into a 2's complement word with the same number of bits as the two summands (fancy word for numbers added to make the sum).

5. Suppose that the words LITTLE ENDIAN in the description of Problem 2 were replaced with BIG ENDIAN. What effect, if any, would that have on your answers to the questions in this section? Explain.

   Answer: This is kind of a sneaky question. The statement of the problem mentioned that the 16 bit strings in the table came from a Little Endian machine, but told you explicitly that the MSB, and therefore the sign bit, was on the left. Had I replaced ``Little Endian,'' with ``Big Endian,'' your answers would not have changed. Why?

   No, it's not merely because I told you where the MSB and the LSB were-although that's a partially correct answer. The main reason is because the bit strings were NOT in memory. They were in a table.

   So, if we were to examine those strings in a memory organized using a Little Endian organization, the LSB would have been stored at the lowest (byte) address in memory associated with the string. If the memory were organized using a Big Endian organization, then the MSB would have been stored at that lowest (byte) address in memory associated with the 2-byte word.

   Since I gave you a table of bit-strings, and not a section of memory with the addresses shown, the issue of endian-ness was absolutely irrelevant.

   Unfortunately, some folks number bits based on the position of the bits in memory. That is, in Big Endian, some people call the most significant bit (msb) 'bit 0' and the least significant bit (lsb) 'bit 15' or 'bit 31' (for a 32 bit word). Conversely, in Little Endian, they reverse the labeling and call the lsb 'bit 0' and the msb 'bit 15' or 'bit 31'.

   That's why I have set the convention for the class that unless I tell you differently, I will always write my bit strings with the lsb on the right and the msb on the left. Why? Because that's the way our number system works in base 10: 2394 is $(2 \times 10^3)+ (3 \times 10^2)+ (9 \times 10^1)+ (4 \times 10^0)$, and it's natural for me.