The 2's complement binary multiplication does not have same procedure as unsigned if the both operands do not have the same sign. What is the logic behind that?
Does special consideration apply to division also when we carry out division with 2's complement numbers?
The 2's complement binary multiplication does not have same procedure as unsigned
In modulo 2n arithmetic -1 and 2n-1 are equivilent. It follows that if the output is the same size as the input then we can used a modulo 2n multiplier for both signed and unsigned operations.
However if the output is larger than the inputs this property no longer holds. Consider for example multipying the 8 bit number 11111111 (255 if interpreted as straight binary, -1 if interpreted as 2's complement) with itself to produce a 16 bit result. For signed numbers the correct result is 0000000000000001. However for unsigned numbers the correct result is 1111111000000001 (65025 in decimal)
If you want to think of this in modular arithmetic terms you can note that -1 and 255 are the same modulo 256 but different modulo 65536.
This is why when you look at (for example) the arm instruction set you see only one 32*32->32 multiply instruction but two different 32*32->64 multiply instructions.
Does special consideration apply to division also when we carry out division with 2's complement numbers?
Division (in the sense we think of it on computers) is not a modular arithmetic operation. So there is no reason to expect an equivilence between signed and unsigned division and indeed there isn't one.
Again to give an example consider 11111110 / 00000010 . In unsigned arithmetic this would result in 01111111 (127) in signed arithmetic it would result in 11111111 (-1)
When doing addition for example if you start with n bits plus n bits you can get all the answers with n+1 bits. We have a carry/borrow bit for that. The beauty of twos complement is that a - b = a + (-b) = a + ~b + 1. so you invert the second operand and the carry in bit for subtraction and then feed it into an adder, no extra clocks needed. Some architectures invert the carry out of the msbit to be a borrow bit some leave it as a carry bit (not borrow bit). The number of overflows possible is not huge by not having an n+1 bit answer.
But for proper multiplication n bits times n bits = 2*n bits to store the result and that is why you will see what you see in many instruction sets (result is twice the size of the operands, two registers in two registers out).
abcd
* 1111
=======
...abcd
..abcd
.abcd
+abcd
=========
The problem is in the dots if this is unsigned those are zeros, but what about signed, smells funny, and it certainly doesnt work.
Note, if you limit yourself to n bits times n bits = n bits then there is no difference between signed and unsigned...
abcd
bcd
cd
+d
======
You just have a ton of overflow possibilities.
One solution is to just sign extend everything for signed multiply:
1111 x 1111 signed = 0001 (-1 * -1 = 1) so try sign extending the operands to twice their size, then we know that n bit * n bit = n bit will just work right.
11111111
* 11111111
============
to do the 4 bit multiply 1111 * 1111
Which turns into this addition
11111111
11111111.
11111111..
11111111...
11111111....
11111111.....
11111111......
11111111.......
======================
and when you add it up (the carries are managed above for visibility)
.....100.......
......100......
........11.....
.........10....
..........10...
............1..
.............0.
.......11111111
......11111111.
.....11111111..
....11111111...
...11111111....
..11111111.....
.11111111......
11111111.......
======================
00000001
But if you think about how we did it in grade school we ignored the signs and did positive numbers for the operation then dealt with the signs at the end. -5 times 6 we would multiply 5*6 = 30 then if we had mismatched signs we would then tack the minus sign on the result -30.
So for 1111 * 1111 signed multiply both are negative so make them positive first (invert and add one) giving this for the first stage:
0001
* 0001
=========
0001
0000
0000
0000
==========
0000001
And then we had - times a - so that is a + the result is +1.
So if an operand is negative then negate it for each operand then do the multiply as unsigned then apply the signs again because in math a * b * c * d = b * c * a * d or whatever order you want
-5 * 6 = (-1*5)*6 = -1 * 5 * 6 = -1 * (5 * 6)
but 1111 * 1111 unsigned you dont invert the operands
1111
* 1111
=========
1111
1111
1111
1111
=========
and that gives you your 0xE1. Just looking at 1111 * 1111 unsigned and signed you can clearly see that you cant do the same work on them to get the right answer 15 * 15 vs -1 * -1
Division is the same deal 1111/0011 vs 1111/0011. 15/3 is 5 but -1/3 = 0 in integer math or -1/3 in floating point. Clearly we cannot do that division with ones in the numerator for signed, so, same as multiply
-a/b = (-1*a)/b = (-1)*(a/b) Likewise -a/-b = a/b and so on.
So -1/3
1111 / 0011 = -((0000+1)/0011) = -(0001/0011)
0000
0011)0001
0000
====
1
-(zero remainder one), then you negate zero 1111+1 = 0000.
What about 6/-3 0110/1101 = (0110/0011)/-1
______
0011)0110
if you are paying close attention you see we need to pad the numerator with zeros just to do the division properly (zeros is okay we are using only positive numbers in this stage of the operation)
00010
0011)00000110
0000
====
0000
0000
====
0001
0000
====
0011
0011
====
0000
0000
====
0
The 6/3 = 2 remainder zero or 2, so we are at 2/-1 and anything times 1 is itself so 2/-1 * -1/-1 = (-12)/(-1-1) = -2. So 6/-3 = -2.
Obviously you cannot just take the bits as is and do the multiply or divide. For signed operands you have to do something first for the result to come out correctly.
You clearly have to mess with something to get signed multiply and divide to work, if you think through subtraction and understand twos complement you see the beauty there to use less logic by using addition to do subtraction and you can invert the carry in to do the add one part of invert and add one. There is probably a way to stick that in there for multiply and divide as well but I do not see it as obvious.
Early processors burned enough clocks to imply that long multiply and log division were happening (multiply for binary is just shift and add for N clocks). You can write equations for each bit to get a single clock solution but the logic grows exponentially as you shave clocks 8 or 9 clocks for 8 bit operands but 4 clocks, 2 clocks and 1 clock it grows dramatically. This is why you see some processors do not offer a divide at all (more complicated than multiply) and some in IP form will offer a compile time option of more clocks smaller logic vs fewer/one clock more logic. These two operations can consume a significant portion of your processor logic. You can probably bury some of this in the pipe and have a few clocks but still appear to average one per instruction.
So in short 15*15 vs -1 times -1 if you simply do this with the bits you have:
1111
* 1111
=========
1111
1111
1111
1111
=========
If I fill that in I get
1.......
.1......
.10.....
..10....
...10...
.....1..
......0.
....1111
...1111.
..1111..
.1111...
=========
11100001
0xF * 0xF = 0xE1
15 * 15 = 225
Obviously that can never equal 0x01 = 1 when the operands are considered signed
0xF * 0xF = 0x01
-1 * -1 = 1
So some manipulation is required. And you can see the same thing with division the same operation with the same bits cannot result in two different numbers. 1111/0011 = both 3 and 0 at the same time depending on unsigned vs signed.
So, yes, for both signed multiply and divide, a different "procedure" is required compared to unsigned.
In grade school we did all of our math (add, subtract, multiply and divide) using positive numbers with a mark to indicate negative. We did not have -5 being 9996 (invert and add one) in grade school we had -5 likewise here a minus three we want to see -0011 and not 1101 and then it becomes easy. But you need to do the extra work sometimes to make all the numbers positive, thus a different procedure.
