patternMinor
How does this unsigned subtraction work?
Viewed 0 times
thissubtractionunsignedworkdoeshow
Problem
Modern computers don't have circuits dedicated for subtraction. They do it by using the method of complements.
All is well when the 2 operands are signed 2's complement numbers. The result of addition will be another 2's complement which, when interpreted as a 2's complement number, will give the correct result provided that there's no overflow.
Now consider a 4 bit number. The unsigned range is 0 15. Signed range is -8 7.
What happens when I do 15u - 14u? The first thought which comes is "Do the 2's complement of 14 and do 15 + (-14)". But then, -14 is not in the range of a 4 bit number.
But if I do it anyway (Flip all bits and add 1):
It works. But 0010 is not even a negative 2's complement number. It is just 2. However, 0010 is the additive inverse of 14 for 4 bits. Is it a coincidence?
Question: Why does it work? And is this even the actual way it's happening?
All is well when the 2 operands are signed 2's complement numbers. The result of addition will be another 2's complement which, when interpreted as a 2's complement number, will give the correct result provided that there's no overflow.
Now consider a 4 bit number. The unsigned range is 0 15. Signed range is -8 7.
What happens when I do 15u - 14u? The first thought which comes is "Do the 2's complement of 14 and do 15 + (-14)". But then, -14 is not in the range of a 4 bit number.
But if I do it anyway (Flip all bits and add 1):
1111
+ 0010
------------
1 0001 = 0001 (4 bits)It works. But 0010 is not even a negative 2's complement number. It is just 2. However, 0010 is the additive inverse of 14 for 4 bits. Is it a coincidence?
Question: Why does it work? And is this even the actual way it's happening?
Solution
In your example, what you are really doing is
$$
15 - 14 \equiv 15 + (16 - 14) \pmod{16}.
$$
To compute $16 - 14$, you first compute $15-14$ (flipping all bits), and then add $1$ to get $16 - 14$.
$$
15 - 14 \equiv 15 + (16 - 14) \pmod{16}.
$$
To compute $16 - 14$, you first compute $15-14$ (flipping all bits), and then add $1$ to get $16 - 14$.
Context
StackExchange Computer Science Q#62563, answer score: 3
Revisions (0)
No revisions yet.