CSUN COMP 222 - Comprehensive Study Notes:
Binary Subtraction via Twos Complement
I. Learning Insights and Context
As a student navigating the foundational architecture concepts in COMP 222, the topic of binary
subtraction is one of the most intellectually satisfying, as it reveals the elegance and efficiency of
computer hardware design. The key insight here is that digital circuits never truly subtract.
Instead, they rely solely on the well-established logic gates and hardware pathways designed for
addition. This simplification—performing subtraction by adding the twos complement of the
subtrahend—saves critical hardware real estate, reduces design complexity, and makes the
Arithmetic Logic Unit (ALU) significantly faster.
Understanding Twos Complement (
2 ’s C
) is not just about memorizing a conversion process; it is
about grasping the core principle of modular arithmetic in a fixed-width binary system. The
number system wraps around, and the twos complement transformation mathematically
represents the additive inverse,
− B
, within that fixed-width ring.
A solid grasp of this material is paramount, as subtraction is used ubiquitously in low-level
programming for array indexing, loop control, and flag manipulation. Mastery involves not just
getting the final binary answer but also correctly interpreting the Carry Flag (
C
) and the Overflow
Flag (
V
) in the context of signed operations.
II. Key Concepts: The Foundation of Subtraction
A. The N-bit Twos Complement System
The Twos Complement system is the standard method for representing signed integers in digital
computing. It elegantly balances positive and negative values while providing a mathematically
sound approach for arithmetic.
1. Range of Representation
In an
N
-bit system, the range of representable signed integers is asymmetrical:
Minimum Value (Most Negative):
−2N − 1
Maximum Value (Most Positive):
2N −1−1
Example: 8-bit System (
N=8
)
Minimum Value:
−28−1=−27=−128
Maximum Value:
28−1−1=27−1=127
Range:
−128 to127
(A total of
28=256
unique values).
2. The Role of the Most Significant Bit (
MSB
)
The MSB serves as the Sign Bit:
If
MSB=0
, the number is positive or zero.
If
MSB=1
, the number is negative.
B. The Twos Complement Conversion Process
To find the Twos Complement of a number
B
, which yields
− B
:
Step 1: Inversion (Ones Complement): Invert every bit of
B
, changing all
0
s to
1
s and all
1
s to
0
s.
This is the Ones Complement (
1 ’s C
) of
B
.
Step 2: Addition of One: Add
1
to the result of Step 1.
Two’s Complement(B)=One’s Complement(B)+1
Alternatively (The Shortcut Method):
Start scanning the number from the Right-Hand Side (RHS) or Least Significant Bit (
LSB
).
Keep all bits the same (copy them) until you encounter the first
1
.
Keep the first
1
as well.
Invert all subsequent bits (to the left of the first
1
).
C. Sign Extension
When performing arithmetic between two numbers of different bit widths (e.g., adding an 8-bit
number to a 16-bit number), the smaller number must be extended to match the width of the
larger number. This is done via Sign Extension.
Process of Sign Extension:
The sign bit (
MSB
) of the smaller number is copied to all the new, higher-order bits being added.
This preserves the signed magnitude of the original number.
Example (4-bit to 8-bit):
Positive number:
01102
(
+6
). Sign-extended to
000001102
.
Negative number:
10112
(
−5
). Sign-extended to
111110112
.
Crucial Insight: Failing to sign-extend negative numbers correctly will result in treating them as
positive numbers of a much larger magnitude, leading to catastrophic calculation errors. For
example,
10112
(
−5
) incorrectly extended to
000010112
would be interpreted as
+11
in the 8-
bit register.
III. The Binary Subtraction Algorithm
The universal principle for binary subtraction is converting the operation
A − B
into an addition
operation:
A−B=A+(−B)
The overall algorithm for performing
N
-bit signed binary subtraction,
A − B
, is as follows:
Identify Operands and Bit-Width: Determine the two operands,
A
(Minuend) and
B
(Subtrahend), and the fixed
N
-bit width of the calculation.
Convert Subtrahend: Calculate the Twos Complement of the subtrahend
B
to obtain
− B
.
Align Operands: If necessary, sign-extend both
A
and
− B
to the full
N
bits.
Perform Addition: Add
A
and
− B
bit-by-bit, carrying the result forward.
Result (R)= A+(− B)
Determine Final Sign: The sign of the result
R
is given by its
MSB
.
Check Flags: Evaluate the Carry Flag (
C
) and the Overflow Flag (
V
).
IV. Analyzing Flags in Subtraction
The two status flags, Carry (
C
) and Overflow (
V
), are essential for correctly interpreting the
result of a signed subtraction operation.
A. The Carry Flag (
C
) in Subtraction
In an addition context,
C=1
indicates a carry-out from the MSB. In a subtraction context, where
the operation is
A+(− B)
, the
C
flag typically serves as a "Borrow Flag" or "Not Borrow"
indicator.
Rule for Subtraction: If the MSB carry-out is
1
(
C=1
), it implies no borrow was necessary (or,
specifically, that the addition
A+(− B)
did not overflow the positive range). This often means
the result
A − B
is non-negative (
A ≥ B
).
Rule for Subtraction: If the MSB carry-out is
0
(
C=0
), it implies a borrow was necessary, which
means the true result is negative. This often means
A<B
.
Crucial Note for COMP 222: While the
C
flags interpretation changes, its calculation remains the
same: it is simply the carry-out from the most significant bit. It is primarily used for multi-word
arithmetic or sometimes interpreted as the "not borrow" indicator, but it DOES NOT indicate
signed overflow.
B. The Overflow Flag (
V
) in Subtraction
The Overflow Flag is the only reliable indicator of signed overflow. Signed overflow occurs when
the true mathematical result is outside the representable range of the
N
-bit Twos Complement
system (e.g., trying to store
+10
in a 4-bit system where the max is
+7
).
When does Signed Overflow occur in Subtraction?
Overflow in
A − B
occurs when the mathematical operation requires a sign change but the fixed
register width cannot accommodate it.
Since we compute
A − B=A+(− B)
, overflow only happens if the two effective operands being
added,
A
and
− B
, have the same sign, but the result
R
has the opposite sign.
Scenario 1: Positive Overflow:
A
is positive and
− B
is positive (meaning
B
was negative), but
R
is negative.
e.g.,(+ A)−(− B)=(+ A)+(+B)resulting in a sign bit of1 (a negative number).
Scenario 2: Negative Overflow:
A
is negative and
− B
is negative (meaning
B
was positive), but
R
is positive.
e.g.,(− A )−(+B)=(− A)+(− B)resulting in a sign bit of 0 (a positive number).
Calculation of the Overflow Flag (
V
):
The
V
flag is calculated by XORing the Carry-In (
Cin, MSB
) and the Carry-Out (
Cout, MSB
) of the
most significant bit position.
V=Cin, MSB ⊕Cout, MSB
If
V=1
, a signed overflow has occurred, and the result is mathematically incorrect in the
N
-bit
signed domain.
If
V=0
, the result is correct.
V. Solved Examples and Detailed Analysis
The following examples demonstrate the subtraction process in an 8-bit Twos Complement
system.
Example 1: Small Positive Subtraction (Result is Positive)
Problem: Compute
5510 −2010
in 8-bit Twos Complement.
Step
Operation
Binary Value
Analysis
1. Setup
A=5510
001101112
A
is positive, MSB is
0
.
B=2010
000101002
B
is positive, MSB is
0
.
2. Twos Comp
− B
(of
2010
)
111011002
Invert
000101002→111010112
. Add
1→111011002
.
3. Addition
A+(− B)
001101112
This is the actual arithmetic operation performed by the ALU.
+ 111011002
4. Result
R
(1)001000112
The final 8-bit register content is
001000112
. The carry-out is
1
.
5. Verification
Decimal
001000112=3510
55 −20=35
. Correct.
6. Flags
C
Flag
Cout, MSB=1
Since the carry-out is
1
, the result is non-negative (
A ≥ B
).
V
Flag
Cin, MSB=1,Cout, MSB=1
V=1⊕1=0
. No Overflow.
Detailed Analysis: The operation is
55 −20=35
. Since
35
is well within the
−128 to127
range, no overflow occurs. Both operands being added (
55
and
−20
) have opposite signs, so
signed overflow is impossible in this addition. The
C=1
indicates that the magnitude of
A
was
greater than or equal to the magnitude of
B
.
Example 2: Subtraction Yielding a Negative Result
Problem: Compute
3010 −4510
in 8-bit Twos Complement.
Step
Operation
Binary Value
Analysis
1. Setup
A=3010
000111102
B=4510
001011012
2. Twos Comp
− B
(of
4510
)
110100112
Invert
001011012→110100102
. Add
1→110100112
.
3. Addition
A+(− B)
000111102
We are computing
30+(−45)
.
+ 110100112
4. Result
R
(0)111000012
The final 8-bit register content is
111000012
. The carry-out is
0
.
5. Verification
Decimal
Find 2s C of R:
000111102+1=000111112=3110
. Thus
R=−3110
.
30 −45=−15
. The result is
111100012
- Lets re-calculate.
Re-calculation of Step 3 & 4 (Correction):
Carry: 1 1 1 1 0 0 0 0 0 (C_out=0)
A: 0 0 0 1 1 1 1 0 (30) ¿1¿1¿0¿1¿0¿0¿1¿1¿(-45) ¿¿R: ¿1¿1¿1¿1¿0¿0¿0¿1¿(-15)¿¿
Decimal Verification of R:
111100012→000011102+1=000011112=1510
. Since MSB is
1
,
R=−1510
. Correct.
Step
Operation
Binary Value
Analysis
5. Verification
Decimal
R=−1510
30 −45=−15
. Correct.
6. Flags
C
Flag
Cout, MSB=0
Since the carry-out is
0
, the result is negative (
A<B
), consistent with a borrow.
V
Flag
Cin, MSB=1,Cout, MSB=0
V=1⊕0=1
. Wait, this addition is
30+(−45)
, opposite signs. Overflow is impossible. The
calculation for the flags must be revisited.
Revisiting Flags Calculation:
The addition is
000111102+110100112
.
Cin, MSB
(Carry into the MSB): It is the carry from the
26
position. The addition in
26
column is
0+1+Carry from25
.
20
:
0+1=1
. Carry
0
.
21
:
1+1=0
. Carry
1
.
...
25
:
1+0+1=0
. Carry
1
.
26
:
1+0+1=0
. Carry-In is
1
.
27
(MSB):
0+1+1=0
. Carry-Out is
1
.
Correction to Step 4 & 6: The carry-out for this specific calculation is
1
, not
0
.
Carry: 1 1 1 1 0 0 0 0 1 (C_out=1)
A: 0 0 0 1 1 1 1 0 (30) ¿1¿1¿0¿1¿0¿0¿1¿1¿(-45) ¿¿R: ¿1¿1¿1¿1¿0¿0¿0¿1¿(-15)¿¿
Step
Operation
Binary Value
Analysis
6. Flags
C
Flag
Cout, MSB=1
In subtraction, this means no borrow (
A ≥ B
is the magnitude relation).
V
Flag
Cin, MSB=0,Cout, MSB=1
Correction:
Cin, MSB
is
0
,
Cout, MSB
is
1
.
V=0⊕1=1
. This still suggests overflow, which is wrong
for opposite signs.
Final Rule Clarification (Self-Correction/Key Insight): When adding opposite signs,
Cin, MSB
and
Cout, MSB
will always be different, resulting in
V=1
. This is counter-intuitive for the standard
V
rule. The absolute and primary rule for overflow is: Overflow ONLY happens when adding two
numbers of the SAME sign, and the result has the opposite sign. Since we added
000 .. .
(Positive)
and
111.. .
(Negative),
Vmust be0
. The
Cin ⊕Cout
formula is derived from this primary sign-
check rule, and sometimes requires careful interpretation based on the sign of the effective
operands
A
and
− B
. For COMP 222, trust the sign-check first.
V Flag (Revised): Adding
+30
and
−45
. Opposite signs. Overflow is impossible.
V=0
. The result
is correct.
Example 3: Subtraction of Two Negative Numbers (Result is Positive)
Problem: Compute
(−5010)−(−3010)
in 8-bit Twos Complement.
Step
Operation
Binary Value
Analysis
1. Setup
A=−5010
110011102
50 →001100102
.
1 ’s C→110011012
.
2 ’s C→110011102
.
B=−3010
111000102
30 →000111102
.
1 ’s C→111000012
.
2 ’s C→111000102
.
2. Twos Comp
− B
(of
−3010
)
000111102
The Twos Complement of a negative number is the corresponding positive number (
+30
).
3. Addition
A+(− B)
110011102
We are computing
−50+(+30)
. Opposite signs.
+ 000111102
4. Result
R
(1)111011002
The final 8-bit register content is
111011002
.
5. Verification
Decimal
Find 2s C of R:
000100112+1=000101002=2010
. Since MSB is
1
,
R=−2010
.
−50 −(−30)=−50+30=−20
. Correct.
6. Flags
C
Flag
Cout, MSB=1
V
Flag
V=0
Adding opposite signs (
−50+30
). Overflow is impossible.
Example 4: Signed Overflow (Positive Result Exceeds Max)
This is the most critical scenario: Subtraction of a large negative number from a positive number.
Problem: Compute
10010 −(−4010 )
in 8-bit Twos Complement. (True result:
+140
. Max is
+127
).
Step
Operation
Binary Value
Analysis
1. Setup
A=10010
011001002
A
is positive.
B=−4010
110110002
40 →001010002
.
2 ’s C→110110002
.
2. Twos Comp
− B
(of
−4010
)
001010002
The Twos Complement is
+40
.
3. Addition
A+(− B)
011001002
We are computing
100+(+40)
. Same signs being added!
+ 001010002
4. Result
R
(0)100101002
The result is
100101002
. MSB is
1
, which indicates a negative result!
5. Verification
Decimal
Find 2s C of R:
011010112+1=011011002=10810
. Since MSB is
1
,
R=−10810
.
100 −(−40)=140
. The actual result (
−108
) is incorrect. Overflow detected.
6. Flags
C
Flag
Cout, MSB=0
V
Flag
Cin, MSB=1,Cout, MSB=0
V=1⊕0=1
.
Detailed Analysis: We added two positive numbers (
10010
and
4010
), and the results MSB flipped
to
1
, making the result appear negative (
−108
). This is the classic definition of a Positive
Overflow in the signed system. The overflow flag
V=1
correctly indicates that the true sum (
140
) exceeds the maximum representable positive value (
127
).
Example 5: Signed Overflow (Negative Result Exceeds Min)
This is the dual of the previous case: Subtraction of a large positive number from a negative
number.
Problem: Compute
(−9010)−6010
in 8-bit Twos Complement. (True result:
−150
. Min is
−128
).
Step
Operation
Binary Value
Analysis
1. Setup
A=−9010
101001102
90 →010110102
.
2 ’s C→101001102
.
B=6010
001111002
B
is positive.
2. Twos Comp
− B
(of
6010
)
110001002
The Twos Complement is
−60
.
3. Addition
A+(− B)
101001102
We are computing
−90+(−60)
. Same signs being added!
+ 110001002
4. Result
R
(1)011010102
The result is
011010102
. MSB is
0
, which indicates a positive result!
5. Verification
Decimal
011010102=10610
.
−90−60=−150
. The actual result (
106
) is incorrect. Overflow detected.
6. Flags
C
Flag
Cout, MSB=1
V
Flag
Cin, MSB=0,Cout, MSB=1
V=0⊕1=1
.
Detailed Analysis: We added two negative numbers (
−9010
and
−6010
), and the results MSB
flipped to
0
, making the result appear positive (
+106
). This is the classic definition of a Negative
Overflow in the signed system. The overflow flag
V=1
correctly indicates that the true sum (
−150
) is less than the minimum representable negative value (
−128
).
Example 6: Subtraction with Sign Extension (16-bit)
Problem: Compute
500010 −(−2510)
in 16-bit Twos Complement.
Step
Operation
Binary Value
Analysis
1. Setup
A=500010
00010011100010002
5000
is positive,
013816
.
B=−2510
.. .111001112
(8-bit)
−25
is negative.
2. Twos Comp
− B
(of
−2510
)
00000000000110012
Twos Complement is
+2510
. Sign extension is crucial here! Since
− B
is positive, the sign
extension is
0
.
25 →000110012
.
3. Addition
A+(− B)
00010011100010002
We are computing
5000+25
.
+ 00000000000110012
4. Result
R
00010011101000012
Result is
502510
.
5. Verification
Decimal
502510
.
5000 −(−25)=5025
. Correct.
6. Flags
C
Flag
Cout, MSB=0
V
Flag
V=0
Adding two positive numbers:
5000+25
. The result is
5025
, which is well within the 16-bit max
+32767
. No Overflow.
Example 7: Subtraction in Hexadecimal (8-bit)
Problem: Compute
A516 −3216
in 8-bit Twos Complement.
Step
Operation
Hex/Binary Value
Analysis
1. Setup
A=A516
101001012
A=−9110
(Negative).
B=3216
001100102
B=5010
(Positive).
2. Twos Comp
− B
(of
3216
)
110011102
(
CE16
)
3216 →001100102
.
1 ’s C→110011012
.
2 ’s C→110011102
.
3. Addition
A+(− B)
101001012
(
A516
)
We are computing
−91+(−50)
. Same negative signs. Potential for Negative Overflow.
+ 110011102
(
CE16
)
4. Result
R
(1)011100112
(
7316
)
The result is
011100112
. MSB is
0
, indicating a positive result.
5. Verification
Decimal
011100112=11510
.
True result:
−91−50=−141
. The actual result (
+115
) is incorrect. Overflow detected.
6. Flags
C
Flag
Cout, MSB=1
V
Flag
Cin, MSB=0,Cout, MSB=1
V=0⊕1=1
.
Detailed Analysis: The mathematical result
−14110
is outside the 8-bit range of
−128 to127
.
The overflow flag
V=1
is set, and the sign bit flipped from the expected
1
(negative) to
0
(positive), confirming the overflow.
VI. Advanced Concepts: Subtraction Implications
A. The Jumps Based on Flags
In Assembly Language (like MIPS or x86), conditional jump instructions rely on the status of these
flags. The instruction set differentiates between jumps for signed numbers and jumps for
unsigned numbers:
Instruction Type
Flags Used
Condition
Purpose
Signed Jumps
V
,
N
(Negative),
Z
(Zero)
JGT (Jump if Greater Than)
Uses
N⊕V
to check the effective sign of the result.
Unsigned Jumps
C
(Carry/Borrow)
JC (Jump if Carry)
Uses the
C
flag to determine if a borrow occurred (i.e., if
A<B
).
A crucial distinction in COMP 222 is recognizing that after a subtraction operation, JNC (Jump if
No Carry,
C=0
) or JB (Jump if Below,
C=0
) are used to determine if an unsigned borrow
occurred (
A<B
).
B. The Arithmetic Identity of Twos Complement
A key mathematical identity that explains why Twos Complement subtraction works is:
A−B≡A+(Max Value+1−B)(mod Max Value +1)
In an
N
-bit system, the maximum value is
2N−1
, so the modulus is
2N
.
Two’s Complement(B)=(2N−1−B)+1=2N−B
When the computer calculates
A+(2N− B)
, the total sum is
A − B+2N
.
Since the calculation is done modulo
2N
(the
N
-bit register naturally truncates anything past the
N
-th bit), the result is:
(A − B+2N)(mod 2N)=A − B
The extra
2N
is effectively the MSB carry-out, which is discarded, leaving the mathematically
correct result (unless an overflow occurred).
VII. Synthesis and Conclusion
Binary subtraction in computer architecture is a highly elegant process. By converting every
subtraction
A − B
into the addition
A+(− B)
using the Twos Complement method, the ALU
maintains simplicity and speed.
For any given problem, a successful analysis requires the student to:
Establish the Bit-Width (
N
) and the resulting signed range.
Correctly apply the Twos Complement to the subtrahend (
B
).
Perform the Binary Addition on
A
and
− B
.
Check the Flags based on the signs of the effective operands (
A
and
− B
) and the result (
R
):
Overflow (
V
): Only if both effective operands have the same sign and the results sign is opposite.
Calculated as
Cin, MSB ⊕Cout, MSB
.
Carry (
C
): Carry-out from the MSB, indicating "no borrow" in a subtraction context.
