4

I elaborate with the following examples. The 4-bit binary representation of decimal 5 is 0101. So decimal -5 is represented in 2's complement as 1011. However, 1011 is also the binary representation of decimal 11. How does one differentiate these two?

If the solution is to restrict 4-bit binary numbers to represent -8 to +7 only, how is an overflow detected? When I add binary 7 to binary 7, I get 1110 which is decimal 13 (overflow), but also binary -2 in 2's complement. How does one detect that binary 7+7 is an overflow, and not -2?

I understand that computers generally use 2's complement to represent negative numbers. I want to know how this problem is dealt with in that context.

user3565552
  • 161
  • 1
  • 1
  • 7

2 Answers2

2

There is no way to differentiate between a positive number and the negative number with the same representation. I have made some programs where I used that ambiguity to get the job done. As you say, the usual procedure is to say that a binary number whose most significant bit (MSB) is 1 to be negative and whose most significant bit is 0 to be positive. For four bits that gives your range -8 through +7.

In addition, one way for the CPU to detect overflow is to compare the carry bit that goes into the MSB and the one that comes out of the MSB. If those bits are the same--both zero or both one--then there was no overflow. If those bits are different--one is zero and the other is one--there was an overflow in the addition.

In your example of 7 plus 7, or 0111 + 0111, note that when you add the 111 to the 111 (the values leaving out the MSBs) you get 1110, so the result is 110 with a 1 carry bit into the MSB. Then when you add the MSBs and the carry you see 0+0+1 which is 1 and has no carry out of the MSB. So the carry in is 1, the carry out is 0, so there was an overflow.

Many CPUs detect those situations. After the addition, one status bit will be the carry bit into the MSB and another will be the carry bit out of the MSB. The overflow condition flag is raised if these bits differ.

Rory Daulton
  • 21,934
  • 6
  • 42
  • 50
2

It it impossible to assign different meanings to the same sequence of bits just looking at those bits. It is impossible to distinguish whether a byte 11111111 represents signed -1 or unsigned 255 the same way it is impossible to distinguish whether a byte 00100001 represents a number 33 or a character 'A'. Those are different interpretations of the same underlying data. The way it is dealt in the real world is the idea of types which is supported in some way in almost any high-level language. The type is the thing that allows choosing one interpretation over the others. In many newer and higher-level languages there is even no simple way to interpret the same data (bytes) in some other way; in some lower-level languages (like C or C++) you actually can do this if you have a good reason to do so. For example you can take a number 5217737203189443684 of a type of 8-bytes integer with a hex representation of 0x48 69 20 57 6F 72 6C 64 and re-interpret it as a sequence of characters "Hi World". There are a few cases when such tricks provide benefits but in most of the cases this is not something you should do (and this is why you can't do it easily in many languages).

So coming back to your example, many languages have different types for "signed integers" and "unsigned integers" and this is what allows distinguishing those cases. And as to overflow one nice property of 2's complement is that on the bits level the logic of addition and subtraction is actually the same for "unsigned integers" and "signed 2's complement integers". So on the hardware level all that is required is to detect an overflow, set the corresponding flags (overflow flag and carry flag) and then left the interpretation of those to the user. Was it -127 + -127 or 129 + 129? The hardware doesn't care. Was that -1 + 2 or 255 + 2? Again the hardware doesn't care. It just sets the flags and lets you (or the compiler) interpret that according to the (logically) assigned type.

P.S. some details on overflow and carry flags are available here

SergGr
  • 23,570
  • 2
  • 30
  • 51