What is Two’s Complement Method?

Two’s Complement is a method for representing signed integers in binary form, allowing both positive and negative numbers to be processed using binary arithmetic. In this system, positive numbers are represented as usual in binary, while negative numbers are represented by taking the complement of the binary number (inverting the bits) and adding 1. Two’s complement simplifies arithmetic operations such as addition and subtraction in digital circuits, because both signed and unsigned numbers can be processed using the same binary addition mechanism. This simplifies hardware design.

In this post, we’ll discuss:

1. What is Two’s Complement method?
2. Why is it used?
3. How it works?
4. And how you can implement it in python?

What is the Two’s Complement Method?

The Two’s Complement method is a mathematical approach for representing signed integers in binary. Unlike unsigned binary numbers, which represent only positive values, two’s complement allows the representation of both positive and negative integers.

As an efficient way to handle subtraction and addition in binary form, it eliminates the need for separate subtraction circuits in hardware, as subtraction can be performed by ‘adding’ the two’s complement of a number (more on this later).

Brief History

The Two’s Complement method originated in the early 20th century but gained popularity with the development of modern digital computers. The concept became widely adopted because it simplifies the design of arithmetic logic units (ALU) in computers and effectively utilizes binary circuitry. John von Neumann is often credited for its use in early computer architecture, as it simplified the design of arithmetic circuits.

How Does It Work?

To find the two’s complement of a binary number:

1. Invert the Digits: Flip all the bits (convert all 0s to 1s and all 1s to 0s) in the fixed-width (like 8 bits, 16 bits etc.) binary representation of the number. This operation is known as taking the one’s complement.
2. Add One: Add 1 to the one’s complement you obtained in the previous step. The result is the two’s complement.

Which Programming Languages Use Two’s Complement for Representing Signed Integers?

Almost all modern programming languages use two’s complement for representing signed integers and performing arithmetic operations. These include:

• C/C++: Two’s Complement is used to represent signed integers in system-level programming.
• Java: In Java, two’s complement is used for all integer types (except for the char type).
• Python: Python abstracts away bit-level details, but it internally uses two’s complement for integer representation.

Why Use Two’s Complement?

Two’s complement encoding is widely used in computer systems due to several advantages:

• Simplified Arithmetic: Using two’s complement, both addition and subtraction can be performed by the same hardware, simplifying the circuit design. Subtracting a number is equivalent to adding its two’s complement. This is crucial because designing and implementing an adder circuit (for addition) is generally simpler and more straightforward than designing a subtractor circuit. By converting subtraction operations into addition operations, we can use the same hardware (adder) for both, which simplifies the design and reduces hardware requirements.
• Handling Negative Numbers: Two’s complement representation of negative numbers helps in processing negative values without needing additional logic to distinguish between positive and negative numbers. In two’s complement system, the most significant bit (MSB) or leftmost bit serves as the sign bit, automatically indicating whether a number is positive (MSB = 0) or negative (MSB = 1). This uniform representation allows operations on positive and negative numbers to be treated identically by the adder circuit.
• Eliminates Ambiguity: There is only one way to represent zero (0000) in two’s complement, eliminating the ambiguity of having a positive and negative zero (0000 and 1111 for 4-bit) which occurs in one’s complement.
• Bitwise Manipulation: Logical operations involving signed integers yield consistent results due to the uniform way that two’s complement represents negative numbers.
• Overflow Detection: Overflow detection is simpler. If the sign bits of the operands are the same, and the sign bit of the result is different, an overflow has occurred. The ‘overflow’ can be checked using a simple logic circuit that examines the carry into and out of the MSB. This is easier and more efficient than having separate mechanisms for overflow detection.

Note: 

The primary purpose of using two's complement is to perform subtraction and handle negative numbers. In this system:

– For an N-bit binary number, the range of values in two's complement is from -2(N-1) to 2(N-1) - 1. For example, with 4 bits, the range is from -8 to 7.
- The most significant bit (MSB) also acts as the sign bit: 0 signifies a positive number, and 1 signifies a negative number.
- Positive numbers are represented as usual in ordinary binary.
- Negative numbers are represented by their two's complements.

Negative Numbers & Subtraction in Two’s Complement

When working with binary numbers, representing and processing negative numbers is a challenge. The Two's Complement method allows negative numbers to be represented and processed in a way that is both simple and efficient.

In a fixed-width two's complement binary system, the MSB serves as the sign indicator as explained above. For example, in a 4-bit Two’s Complement system:

– The binary number 0101 represents the decimal value 5 (positive, as MSB = 0).
– The binary number 1011 represents the decimal value -5 (negative, as MSB = 1).

How does it work? [1]
We already discussed that to find the two's complement of a binary number, invert it and add one. Let's understand why does it work?

Borrowing and Subtraction
When you learned subtraction in elementary school, you likely encountered the concept of borrowing. For example, when subtracting two decimal numbers, you start from the least significant digit (rightmost) and borrow from the next column when you cannot subtract a larger digit from a smaller one. This borrowing continues until the subtraction is complete.

In binary, the subtraction process works in a similar fashion, except it operates with only 1s and 0s. For instance, subtracting a binary number from zero would involve borrowing continuously from higher bits, resulting in a value where all higher bits are 1.

Negative Numbers in Binary
When you want to find the negative of a number, you take the number, and subtract it from zero. Let's do the same computation to find the negative of a binary number:

Let the number be 0101 (5 in decimal),
   
 111111 (carry)
  000000
- 000101
  ------
  111011

It could go further but it's of no use. Inside of a computer the result of this computation would be assigned to a fixed-width variable (4-bit here), so any bits beyond the fourth would be discarded.

With the fact that extra digits will simply be discarded, we'll get the same result if we'll subtract 0101 from 10000 (1 followed by four 0s).
   
  1111 (carry)
  10000
-  0101
  -----
  01011

Now, we have understood that to find the negative representation of a number in binary, subtract the number from 0 or from 2n. So, in the case of 4-bit numbers, it'll work fine if we subtract the number from (1 + 1111) or 10000.

How is this similar to taking the two's complement of a number?

Continuing with the above example, 

10000 - 0101 could be written as:

1 + 1111 - 0101 ≡ 1 + (1111 - 0101)

Also, in binary, when we subtract a number `num` from a binary number with all 1 bits, what we are essentially doing is inverting the bits of `num`. Let's understand this with an example:

  1111
- 0101 (num)
  ----
  1010 (~num)

So, taking the negative of a number, that is, subtracting the number from 0, is equivalent to inverting the bits of the number and adding one, which is nothing but the Two's Complement of the number.

Understanding Arithmetic of Signed-Integers (Optional) [2]

Consider an 8-bit binary system. How will you subtract 3 from a number?
Well, by the above logic, this is the same as adding 256−3 = 253 to the number.

Now, in the context of arithmetic with signed integers, we don't think of 11111101 as being 253 in our 8-bit system, we instead consider it to represent the number -3.

Rather than having numbers go from 0 to 255 in an 8-bit system, we have them go from −128 to 127, where -x occupies the same spot that 256 - x would occupy for values of x from 1 to 128.

Ambiguity of Negative Zero in One’s Complement

In one's complement representation, negative numbers are formed by inverting all bits of the positive value (changing 0 to 1 and 1 to 0). However, if you invert all bits of 00000000 (representing 0), you get 11111111, which represents negative zero, and it is invalid in integer math. It results in complications and inconsistencies, making one's complement less practical for arithmetic operations.

This problem is solved by using two’s complement to represent negative values. When using two’s complement, 1 is added to the one’s complement, producing 100000000. This produces an extra 1 bit overflowing to the left, resulting in the expected behavior, where –0 is the same as 0, and 11111111 is the encoding for –1.

Overflow Detection in Two’s Complement Method

In Two’s Complement arithmetic, overflow occurs when the result of an arithmetic operation exceeds the range that can be represented by the available number of bits. This typically happens when:

1) Adding two positive numbers results in a number that exceeds the maximum positive value.
2) Adding two negative numbers results in a number that is smaller (more negative) than the minimum negative value.

Overflow cannot occur when adding a positive and a negative number. This is because the result always lies between the two operands, meaning it can’t exceed the representable range.

Overflow Detection Logic: Overflow occurs when sign bit of the operands is different from the sign bit of the result.

Consider this example:

Positive Overflow (in an 8-bit system)
Let’s add 100 (binary 01100100) and 50 (binary 00110010):

  01100100  (100 in decimal)
+ 00110010  (50 in decimal)
  --------
  10010110  (-106 in Two's Complement)

The result should be 150, but due to the 8-bit system, it overflows and results in -106.

Here, both operands have MSB = 0 (positive), but the result has MSB = 1 (negative). This indicates positive overflow.

Similarly, you can work out the negative overflow.

When a result exceeds the maximum or minimum value in Two’s Complement, the binary representation wraps around due to the modular nature of binary arithmetic. This leads to the wrong sign in the result. 

This mismatch is easy to detect in two's complement by comparing the sign bits.

Two’s Complement Method in Detail: Step-by-Step

In binary arithmetic, subtraction can be complex when directly implemented with hardware. However, by using two’s complement, subtraction can be converted into addition. Let’s walk through an example of converting a binary number to its two’s complement:

Step-by-Step Process

Let’s say we want to find the Two’s Complement of 5. Its binary representation is 0101.

1) Invert the Digits (One’s Complement)
Flip all the bits of 0101 to get 1010.

2) Add One
Add 1 to 1010 to get 1011.

Thus -5 in Two’s Complement is 1011.

Binary Subtraction (4-bit): With and Without Two’s Complement

Let’s subtract 0010₂​ (2 in decimal) from 0101₂ (5 in decimal):

Method 1: Direct Binary Subtraction
In direct binary subtraction, you subtract bit-by-bit, borrowing when needed.

  0101    (5)
- 0010    (2)
  ----
  0011    (3)

Method 2: Subtraction Using Two’s Complement
To subtract using Two’s Complement, you first find the two’s complement of the number to be subtracted and then add it to the minuend.

1. Find Two’s Complement of 0010:

Invert the digits: 1101
Add 1: 1101 + 1 = 1110

2. Add this to 0101 (5)

  0101    (5)
+ 1110    (-2)
  ----
  0011    (3)

Answer is 0011 (3 in decimal). Bits beyond the 4th are discarded.

So, that’s how we perform subtraction using two’s complement.

Understanding Most Significant Bit (MSB) or the Sign Bit

Let’s analyze the binary number 1000₂ to determine how it represents -8 in the two’s complement system.

1) Determine the Bit Length: 1000
This binary number is 4 bits long.

2) Check the Most Significant Bit (MSB):
In a 4-bit two's complement binary system, if the MSB (the leftmost or 4th bit) is 1, the number is negative.

3) Convert to Decimal:
To find the decimal value of a negative two's complement number, we need to convert it back to its positive equivalent first by inverting the bits and adding 1.

Invert the Bits:
 - Inverting `1000` gives `0111`.

Add 1 to the Inverted Bits:
 - Adding `1` to `0111` results in `1000`.

Convert to Decimal:
 - The binary number `1000` (after inversion and adding 1) corresponds to `8` in decimal.

4) Negate the Result:
Since we started with a negative number (as indicated by the MSB being `1`), the result is `-8`.

Therefore, `1000` represents `-8` in a 4-bit two's complement binary system.

Code Implementation for Two’s Complement

Let’s implement and test subtraction using two’s complement in Python, including overflow detection.

Python Implementation

def to_twos_complement(value, bit_width):
    """Compute two's complement for a given bit width."""
    if value >= 0:
        # Mask the positive value to fit within the specified bit width (including MSB)
        return value & ((1 << bit_width) - 1)
    else:
        # For negative value, invert the bits and add 1 to get two's complement
        return (~(-value) + 1) & ((1 << bit_width) - 1)  # Mask to fit bit width


def twos_complement_subtraction(minuend, subtrahend, bit_width):
    """Subtract two numbers using Two's Complement and check for overflow."""

    # Convert both numbers to Two's Complement
    minuend_tc = to_twos_complement(minuend, bit_width)
    subtrahend_tc = to_twos_complement(-subtrahend, bit_width)

    # Perform addition (since subtraction is adding the Two's Complement)
    result = minuend_tc + subtrahend_tc

    # Mask the result to the bit width
    result = result & ((1 << bit_width) - 1)

    # Check for overflow: In Two's Complement, overflow occurs if the result sign is incorrect
    sign_mask = 1 << (bit_width - 1)  # The sign bit mask (100..00)
    minuend_sign = minuend_tc & sign_mask
    subtrahend_sign = subtrahend_tc & sign_mask
    result_sign = result & sign_mask

    # Overflow occurs if minuend and subtrahend have the same sign but result has a different sign
    if (minuend_sign == subtrahend_sign) and (minuend_sign != result_sign):
        print("Overflow detected")
    else:
        print("No overflow")

    # Convert result back to decimal if the MSB (sign bit) is set
    if result_sign:
        result = -(~result + 1 & ((1 << bit_width) - 1))  # Convert result to negative

    return result


# Testing subtraction using Two's Complement
bit_width = 5

# Test cases
minuend = 10
subtrahend = 2

print(f"{minuend} - ({subtrahend}) using Two's Complement: "
      f"{twos_complement_subtraction(minuend, subtrahend, bit_width)}")

minuend = -15
subtrahend = 1

print(f"{minuend} - ({subtrahend}) using Two's Complement:"
      f" {twos_complement_subtraction(minuend, subtrahend, bit_width)}")

minuend = 15
subtrahend = -1

print(f"{minuend} - ({subtrahend}) using Two's Complement:"
      f" {twos_complement_subtraction(minuend, subtrahend, bit_width)}")

Output

No overflow
10 - (2) using Two's Complement: 8
No overflow
-15 - (1) using Two's Complement: -16
Overflow detected
15 - (-1) using Two's Complement: -16

Two’s complement method simplifies arithmetic operations and hardware design in digital systems by allowing subtraction to be handled as addition. By allowing both addition and subtraction to be performed using the same circuitry, two’s complement improves computational efficiency and reduces hardware complexity.

Due to its simplicity and effectiveness, two’s complement has become the standard method for representing signed integers in computer systems.

References:
1. Two’s Complement – Thomas Finley
2. Stackexchange  – Why Two’s Complement works