1

I know how to convert to two's complement. You have binary number, invert it and then add 1 on it.

But what does the computer do?

Let's say we want do D = A-B

A and B are both in two's complement.

Will the computer now add both values? So actually it does A + B?

I hope I didn't describe my question too bad / complicated. Please do tell me this is confusing me!

klbrtree
  • 11
  • 2
  • 1
    Does this help? http://stackoverflow.com/questions/5793740/how-does-cpu-do-subtraction – Bathsheba Oct 10 '16 at 15:58
  • @Bathsheba thank you for link! I make my own example: A and B are BOTH in 2-complement. A=0110 and B=1010. We are asked to do A-B, so then we will have: 0110 - 0101 = 0001 ? So basically we take A and subtract it with negation of B? Correct? – klbrtree Oct 10 '16 at 16:06
  • Hmm or we rather take 0110 + 1010? Because both is already in two complement. Ok this is getting more confusing... – klbrtree Oct 10 '16 at 16:11
  • 1
    2-complement is only a representation. It can represent both positive and negative numbers. The process you described above (invert a number, then add 1) is actually the process of negating a number (it is not the conversion of a number to its 2-complement).. So in order to calculate A-B, you negate B with the aforementioned process and add that to A. – Nico Schertler Oct 10 '16 at 18:18

2 Answers2

0

The comment by Nico already sums this up nicely.

Two's complement is a definition of how you translate integers (in a given range) to bit patterns. It applies to both positive numbers (where the translation is straight-forward binary number system, so it's the same as for unsigned or one's complement representations) and negative numbers (where the specific interpretation of two's complement becomes relevant).

So if you know that A and B are in two's complement, that doesn't tell you anything about whether one of them is negative or not. But you don't have to care, since the addition operation works the same without regard for the sign. Computing A + B at the machine level does the right thing without doing case distinctions.

If you want to do A - B, then you may want to compute A + (-B). Which means you would have to perform negation on a two's complement number. To negate such a number, you subtract one then flip all the bits, or you flip all bits then add 1: -B = ~(B - 1) = (~B) + 1 (using ~ to denote bitwise not).

Note that hardware doesn't have to do subtraction as negation then addition. It may have a separate instruction for subtraction, and that separate instruction may reuse some of the circuits also used for addition, but might as well have circuits dedicated purely to subtraction.

MvG
  • 57,380
  • 22
  • 148
  • 276
0

The straightforward way to add binary numbers is with a series of full adders. Each adder adds two bits, takes in a carry bit, and puts out a carry bit along with the sum bit. This is old, well-established digital design for binary numbers interpreted as positive integers.

In real life, adding binary numbers with full adders is a dumb idea. It takes time, what the engineers call "propagation time", for the carry bit from the least-significant bits (LSBs) to influence the next bit up, and that carry bit to influence the next, and so on for all 20 or 32 or 64 bits or however many. Clever ways exist to circumvent this delay. Ignorance is bliss; we will happily ignore this engineering detail for the rest of this answer. If you're curious, see the wikipedia article on look-ahead carry.

How to represent negative numbers as binary? The lazy way (for engineers) is to think about what would work with the same circuitry of full adders. The interpretation of binary as 2's complement signed numbers works perfectly. If we think that way, then our old positive-only arithmetic logic units can be dusted off, nothing at all changed, and used as signed integer units.

That this works is easy to see, with a bit of thinking. Think of a three-bit adder. 001 + 010 => 011, and 101 + 001 => 110. For a positive-only interpretation of binary, this is fine. For signed, how is 101 like negative three? Add three, and keep all the bits. 1000 is the answer. But we're using only three bits, so it's 000, zero. Think of the "negative" values as being relative to 1000, and know that the 4th bit is only imagined.

After a bit of toying around with this, we see that we can add negative numbers just fine with 2's complement, found by complementing and incrementing.

The question is: how to subtract A-B? We do not wire up specific circuitry to complement B, increment B, then add A+B. Too slow, too much silicon real estate. Turns out that there's a way to tweak the design of a full adder to do subraction instead. Note:

A - B = A + (-B) = A + (~B) + 1

The "tweak" to the full adder design is to do nothing at all, but add an inverter to each bit of B. We push in an always-on carry bit to the LSB's full adder. Done! Life is easy. For digital engineers, anyway.

Most CPU have a NEG opcode, exactly to perform 2's complement negation. It is implemented as a subtraction, but the 'A' input is gated off so it appears as all zeros to the ALU.

The old 7400 series TTL logic chips had a 4-bit ALU, the 74181. It could add, subtract, AND, OR, XOR, shift, or complement any one or two 4-bit binary numbers. Interpret them as positive or signed 2's complement as you wish. Wikipedia has an article on this chip, with a logic diagram for your enjoyment.

To add to the confusion, while normally a low voltage, typically anything less than one volt or so, is boolean ZERO, and high voltage, anything above 3V or whatever depending on the exact technology and chip design, is boolean ONE, it is possible and frequently done to switch that around. An engineer might choose 0.5V might be ONE while 4V is ZERO. What used to be an AND gate now can be though of as an OR gate. Sometimes this allowed faster chips to be used. It's related to the fact that NPN transistors switch slightly faster than PNP, and that open collector outputs with pullup resistors, and inputs that were naturally high when open, were so common. Adding a pushbutton to the input of a logic circuit usually meant a pullup resistor (or no resistor) and the button wired to ground a circuit node. No push = "off" to the human = high voltage; press button = "on" or "active" to the Human = zero voltage. We want to take these as logical ZERO and ONE, respectively. So you may find some ALU designs were made to work in this crazy upside-down world.

DarenW
  • 16,549
  • 7
  • 63
  • 102