Difficulties with Two's complement in Assembly

Question

Everything discussed here will refer to Intel 8085 (8-bit architecture).

When using two's complement number "conversion" :

1.) If we take SBI 0F (subtraction) for example; immediate value 0F(hex) or 15 is subtracted from A register, which is loaded with 3C(hex) or 60. How will the microprocessor know whether e.g. 3C is equal to 60 (00111100) or -60 (11000100 --> invert+increment) which is actually 196 (which actually doesn't "fit" in 8-bit system)?

2.) Does the CPU or ALU consider the minus conversion when calculating equation like: -x-(-y)=z which transforms into -x+y=z ? If it does, how does it process the equation?

Answer 1

First, the CPU just does what you tell it. Someone else has to translate an expression into CPU instructions.

Second, -x-(-y)=z and -x+y=z are equations (relation formulas), not assignment statements, at least in most languages I can imagine off hand. An expression like y-x is typically assigned to a variable looking something like var z = y-x;.

Third, what you're talking about, that -x-(-y) can be replaced by the much simpler y-x, is what we call optimization, and the CPU doesn't do that. Optimization comes as part of translation of the assignment or expression to the target CPU. Translation of expressions is rather large job in the general case. The translator has to concern with honoring the rules of the high-level language, while also accommodating the limitations of the underlying processor (for example, large expressions may require more temporary storage than available within the CPU, so memory must be employed). There is also no guaranteed best possible code sequence for the translation, and one translator may do better than another for any given expression.

---

Lastly, for operands of signed types, the processor will interpret operands whose high bit is set as negative, and those not set as positive, but, the fact is that for addition and subtraction, the processor doesn't actually care if the operands are positive or negative, because the logic to add or subtract positive vs. negative (even signed vs. unsigned) is the same. That is, for one, one of the advantages of 2's complement numeric representation of the integers.

If you issue an add instruction it will add regardless of the sign of the operands. The only time the sign is significant is if you want to interpret the overflow results or were doing a comparison. Then you have to know whether you were dealing with unsigned or signed numbers (but this doesn't require dynamic information as to positive vs. negative, instead we use static information as to signed vs. unsigned by the types of the operands). (Further, it only make sense to ask if a number is negative if the value is of a signed type as unsigned types hold values that are always non-negative).

---

You might be interested in studying compiler technology as it deals with these issues. The CPU is a complex piece of hardware, but even still, it gets a lot of support from operating systems, compilers, and standards like the various Application Binary Interfaces.

---

From: http://www.nhn.ou.edu/~baron/num_meths/Unsigned_and_Signed_Integers.pdf

There is an interesting consequence to the fact that in 2's complement arithmetic, one expects to throw away the final carry:

• in unsigned arithmetic a carry out of the most significant digit means that there has been an (unsigned) overflow, but

• in signed arithmetic an overflow is not so easy to detect. In fact, signed arithmetic overflows are detected by checking the consistency of the signs of the operands and the final answer. A signed overflow has occurred in an addition if:

  • the sum (addition) of two positive numbers is negative;
  • the sum (addition) of two negative numbers is positive;

• and a signed overflow has occurred in in subtraction if:

  • subtracting a positive number from a negative one yields a positive result; or
  • subtracting a negative number from a positive one yields a negative result.

---

Wikipedia citation: "In a computer, the amount by which a calculated value is greater in magnitude than that which a given register or storage location can store or represent. Note that the overflow may be placed at another location."

Is this like well defined explanation of arithmetic overflow?

Yes (mostly -- If it was me, I'd omit the "calculated" word from that passage, see more on that further below).

Overflow happens whenever some value doesn't fit in the location it is targeted to be stored, but to be clear, you have to factor in the numeric representation, for example, as to whether signed or unsigned, and the size of target as compared with the size of the sources.

When you add or subtract two 8 bit values together you get a 9-bit answer, but usually, we're putting that 9-bit result back into an 8-bit register, and it is possible that that actual 9-bit value doesn't fit in 8-bits, and that's called an overflow situation. (Taking only the lower 8-order bits when there is overflow, results in a garbage value that might be vastly different in sign and magnitude than the original 9-bit value.)

As the Wikipedia article states, the overflow contents/value, which for add/sub, is just 1-bit, may go somewhere else, and, in many processors, that is the carry bit in the CPU flags status register.

This carry bit can be used in support of extended arithmetic, and for the 8085 this is what ADC is for. To add two 16-bit numbers, we use ADD on the two low order bytes, followed by ADC for the two high order bytes. One bit of overflow is, of course, still possible (e.g. the result is 17-bits), so in addition to the carry flag being read by ADC merely to propagate the carry from the low order, the carry flag is also written regarding the final result.

Now, the interpretation of overflow requires understanding the numeric type. For unsigned 8-bit arithmetic, if that 9th bit is clear, there is no overflow, otherwise there is overflow.

For signed arithmetic, the considerations for overflow are as stated above. Some processors will compute this directly for you, and, it looks like the 8085 does it but it is undocumented!

When doing multiplication of two 8-bit numbers the result is a 16-bit number, so, processors (or repetitive addition algorithms as you'd do on an 8085, which lacks a multiply operation) provide an 8 extra bits of result, e.g. by putting the high order result into a second 8-bit register. Now if your plan is to cut that answer back down to 8 bits, you can check overflow by inspecting the upper 8 bits of the 16 bit result. The interpretation issues for signed vs. unsigned remain, so unsigned overflow is avoided when the upper byte is zero, , and signed overflow is avoided if each bit of the upper byte matches the MSB of the lower byte.

Note that as Wikipedia states, overflow is mostly the result of attempting to place a calculated value n-bits in length into a storage location of n-1 or fewer bits. Note that there is no possibility of overflow for AND, OR, and, ROTATE operations, but there is for ADD, SUB, MULTIPLY, and SHIFT operations.

However, the article states that overflow is the result of calculation, and I'd point out that overflow can also happen without involving calculation just having been performed by the CPU/ALU. Non-arithmetic operations potentially causing overflow would be taking a 16-bit value and storing it in 8-bits. Also, taking an 8-bit unsigned value and storing it in 8-bits yet with the intention of treating it as a signed value later.

---

Ok, so by now you're probably wondering: with so much potential for overflow, how does anything work? And part of the answer lies in a consistency between memory addressing (e.g. pointer) size and the integer size. Many calculations (especially adds and subtracts) are used in locating values in memory (e.g. array indexing, struct field offsets). If the integer size and the memory addressing size are the same, then generally speaking, our programs will run out of memory before having overflow issues (it is important to check memory allocation results for the out-of-memory condition). (Computation that does not involve addressing and indexing needs to be checked carefully for potential overflow, sometimes by limiting input ranges, sometimes after the fact by stopping the program, and sometimes by capping values to max or min as is common in graphics.)