How does the CPU do subtraction?

Question

I have some basic doubts, but every time I sit to try my hands at interview questions, these questions and my doubts pop up.

Say A = 5, B = -2. Assuming that A and B are 4-bytes, how does the CPU do the A + B addition?

I understand that A will have sign bit (MSB) as 0 to signify a positive value and B will have sign bit as 1 to signify a negative integer.

Now when in C++ program, I want to print A + B, does the addition module of the ALU (Arithmetic Logic Unit) first check for sign bit and then decide to do subtraction and then follow the procedure of subtraction. How subtraction is done will be my next question.

A = 5
B = 2

I want to do A - B. The computer will take 2's complement of B and add A + 2's complement of B and return this (after discarding the extra bit on left)?

A = 2
B = 5

to do A - B. How does the computer do in this case?

I understand that any if-then etc kind of conditional logic all will be done in hardware inside ALU. computing 2s complement etc,discarding extra bit all will be done in hardware inside ALU. How does this component of ALU look like?

Gristle

The ALU looks about like this: en.wikipedia.org/wiki/… – Ratite

Negative numbers are the 2's complement of the corresponding positive number - not just a change in the sign bit. – Flivver

Answer 1

The whole reason we use 2's-complement is that addition is the same whether the numbers are positive or negative - there are no special cases to consider, like there are with 1's-complement or signed-magnitude representations.

So to find A-B, we can just negate B and add; that is, we find A + (-B), and because we're using 2's-complement, we don't worry if (-B) is positive or negative, because the addition-algorithm works the same either way.

Illomened

in 1's complement there are no special cases to consider, either. You simply add the 2 numbers and add the carry back. Only sign-magnitude needs to take care of the sign bit – Velasquez

Note that some ISAs (like x86) have a Carry flag output that's set if the real subtraction would have a borrow, not a hypothetical A + (-B) addition. This implementation possibility doesn't change the fact that (-1) - (-2) (i.e. 0xFF - 0xFE) results in CF=0. ARM is the opposite: after subtraction the C flag is a !borrow result, and ARM's sbc instruction behaves accordingly. – Philana

How does the CPU calculate this: -1-1=-2, as the CPU only does Addition? – Quartic

Answer 2

You are a bit wrong in the sign bit part. It's not just a sign bit - every negative number is converted to 2's complement. If you write:

B = -2

The compiler when compiling it to binary will make it:

1111 1111 1111 1111 1111 1111 1111 1110

Now when it wants to add 5, the ALU gets 2 numbers and adds them, a simple addition.

When the ALU gets a command to subtract it is given 2 numbers - it makes a NOT to every bit of the second number and makes a simple addition and adds 1 more (because 2's complement is NOT to every bit +1).

The basic thing here to remember is that 2's complement was selected for exactly the purpose of not having to make 2 separate procedures for 2+3 and for 2+(-3).

Sellma

Answer 3

Think in terms of two or three bits and then understand that these things scale up to 32 or 64 or howevermany bits.

First, lets start with decimal

 99
+22
===

In order to do this we are going to have some "Carry the one's" going on.

11
 99
+22
===
121

9 plus 2 is 1 carry the one, 1 plus 9 plus 2 is 2 carry the one...

The point being though to notice that to add two numbers I actually needed three rows, for at least some of it I might need to be able to add three numbers. Same thing with an adder in an alu, each column or bit lane, single bit adder, needs to be able to add two inputs plus a carry in bit, and the output is a one bit result and a one bit carry.

Since you used 5 and 2 lets do some 4 bit binary math

 0101
+0010
=====
 0111

We didnt need a carry on this one, but you can see the math worked, 5 + 2 = 7.

And if we want to add 5 and -2

11
 0101
+1110
=====
 0011

And the answer is 3 as expected, not really surprising but we had a carry out. And since this was an add with a minus number in twos complement it all worked, there was no if sign bit then, twos complement makes it so we dont care just feed the adder the two operands.

Now if you want to make a subtle difference, what if you want to subtract 2 from 5, you select the subtract instruction not add. Well we all learned that negating in twos complement means invert and add one. And we saw above that a two input adder really needs a third input for carry in so that it can be cascaded to however wide the adder needs to be. So instead of doing two add operations, invert and add 1 being the first add the real add all we have to do is invert and set the carry in:

Understand that there is no subtract logic, it adds the negative of whatever you feed it.

    v this bit is normally zero, for a subtract we set this carry in bit
11 11
 0101 five
+1101 ones complement of 2
=====
 0011

And what do you know we get the same answer...It doesnt matter what the actual values are for either of the operands. if it is an add operation you put a zero on the carry in bit and feed it to the adder. If it is a subtract operation you invert the second operand and put a one on the carry in and feed it to the same adder. Whatever falls out falls out. If your logic has enough bits to hold the result then it all works, if you do not have enough room then you overflow.

There are two kinds of overflow, unsigned, and signed. Unsigned is simple it is the carry bit. Signed overflow has to do with comparing the carry in bit on the msbit column with the carry out bit for that column. For our math above you see that the carry and carry out of that msbit column is the same, both are a one. And we happen to know by inspection that a 4 bit system has enough room to properly represent the numbers +5, -2, and +3. A 4 bit system can represent the numbers +7 down to -8. So if you were to add 5 and 5 or -6 and -3 you would get a signed overflow.

01 1
 0101
+0101
=====
 1010

Understand that the SAME addition logic is used for signed and unsigned math, it is up to your code not the logic to virtually define if those bits were considered twos complement signed or unsigned.

With the 5 + 5 case above you see that the carry in on the msbit column is a 1, but the carry out is a 0 that means the V flag, the signed overflow flag, will be set by the logic. At the same time the carry out of that bit which is the C flag the carry flag, will not be set. When thinking unsigned 4 bits can hold the numbers 0 to 15 so 5 + 5 = 10 does not overflow. But when thinking signed 4 bits can hold +7 to -8 and 5 + 5 = 10 is a signed overflow so the V flag is set.

if/when you have an add with carry instruction they take the SAME adder circuit and instead of feeding the carry in a zero it is fed the carry flag. Likewise a subtract with borrow, instead of feeding the carry in a 1 the carry in is either a 1 or 0 based on the state of the carry flag in the status register.

Multiplication is whole other story, binary makes multiplication much easier than when done with decimal math, but you DO have to have different unsigned and signed multiplication instructions. And division is its own separate beast, which is why most instruction sets do not have a divide. Many do not have a multiply because of the number of gates or clocks it burns.

Krahling

Answer 4

does the addition module of ALU (Arithmetic Logic Unit) first check for sign bit and then decide to do subtraction and then follow the procedure of subtraction

No, in one's and two's complement there's no differentiation between adding/subtracting a positive or negative number. The ALU works the same for any combination of positive and negative values

So the ALU is basically doing A + (-B) for A - B, but it doesn't need a separate negation step. Designers use a clever trick to make adders do both add and sub in the same cycle length by adding only a muxer and a NOT gate along with the new input Binvert in order to conditionally invert the second input. Here's a simple ALU example which can do AND/OR/ADD/SUB

Computer Architecture - Full Adder

The real adder is just a box with the plus sign inside ⊞ which adds a with b or ~b and carry in, producing the sum and carry out. It works by realizing that in two's complement -b = ~b + 1, so a - b = a + ~b + 1. That means we just need to set the carry in to 1 (or negate the carry in for borrow in) and invert the second input (i.e. b). This type of ALU can be found in various computer architecture books like

• Digital Design and Computer Architecture
• Computer Organization and Design MIPS Edition: The Hardware/Software Interface
• Computer Organization and Design RISC-V Edition: The Hardware Software Interface

In one's complement -b = ~b so you don't set the carry in when you want to subtract, otherwise the design is the same. However two's complement has another advantage: operations on signed and unsigned values also work the same, so you don't even need to distinguish between signed and unsigned types. For one's complement you'll need to add the carry bit back to the least significant bit if the type is signed

With some simple simple modification to the above ALU they can now do 6 different operations: ADD, SUB, SLT, AND, OR, NOR

CSE 675.02: Introduction to Computer Architecture

Multiple-bit operations are done by concatenating multiple single-bit ALUs above. In reality ALUs are able to do a lot more operations but they're made to save space with the similar principle

Velasquez

NOT + mux is actually just an XOR gate, as mentioned by en.wikipedia.org/wiki/Adder%E2%80%93subtractor – Philana

Answer 5

In 2's-complement notation: not B = -B -1 or -B = (not B) + 1. It can be checked on a computer or on paper.

So A - B = A + (not B) + 1 which can be performed with:

• 1 bitwise not
• 1 increment
• 1 addition

There's a trick to inefficiently increment and decrement using just nots and negations.

For example if you start with the number 0 in a register and perform:

not, neg, not, neg, not, neg, ... the register will have values:

-1, 1, -2, 2, -3, 3, ...

Or as another 2 formulas:

not(-A) = A - 1
-(not A) = A + 1

Worthen