Two's complement

Two's complement represents signed integers in binary, where the most significant bit (MSB) serves as the sign bit: 0 for non-negative and 1 for negative. For an N-bit representation, the value of a binary number is computed as -2^(N-1) times the MSB plus the sum of the lower bits. This encoding yields a range from -2^(N-1) to 2^(N-1)-1, with a single representation for zero, unlike sign-magnitude or one's complement which have both +0 and -0.

Arithmetic in two's complement is straightforward: addition and subtraction are performed using the same binary addition circuits, with subtraction implemented as addition of the two's complement (negation). Overflow is detected when the carry into the sign bit differs from the carry out. This property simplifies hardware design, making two's complement the standard in virtually all modern processors.

The concept of two's complement dates back to the early days of computing. The first known use was in the ENIAC (1945), which employed a form of complement arithmetic for subtraction. However, the formalization and widespread adoption came with the rise of binary computers in the 1950s and 1960s. Early machines like the IBM 704 and the PDP-1 used two's complement, and it became the dominant representation in the microprocessor era.

Notably, the Intel 8008 (1972) and subsequent x86 processors adopted two's complement, cementing its status. The representation's efficiency in hardware implementation, particularly for arithmetic logic units (ALUs), drove its universal acceptance. Today, virtually all general-purpose CPUs and DSPs use two's complement for signed integer arithmetic.

Beyond basic arithmetic, two's complement has subtle implications. For example, the asymmetry of the range means that the most negative number (-2^(N-1)) has no positive counterpart; negating it yields itself, which can cause overflow in some operations. This is a common source of bugs in software.

Another niche aspect is the use of two's complement in floating-point representations: the IEEE 754 standard uses a sign-magnitude format for the significand, but two's complement is used in some hardware implementations for internal arithmetic. Additionally, two's complement is used in digital signal processing for efficient filtering and correlation. The representation also enables simple sign extension when widening integers, and it is the basis for the 'two's complement trick' used in algorithms like the lowbit operation (x & -x) in Fenwick trees.

Two's complement is ubiquitous in programming languages: C, Java, and Python (via the '~' operator) all rely on it for signed integer semantics. In C, the standard allows other representations, but virtually all compilers target two's complement hardware. The C++20 standard mandates two's complement for signed integers, reflecting its dominance.

Edge cases include the handling of the most negative value in division and modulo operations, which can lead to hardware exceptions or undefined behavior in some languages. Also, bitwise operations like right shift on negative numbers are implementation-defined in C, but in two's complement, arithmetic shift preserves the sign bit. The representation also enables efficient algorithms for absolute value and sign detection, and it is used in checksum calculations and error detection.

Most significant bit (MSB)

The bit with the highest place value in a binary number; in two's complement, it indicates the sign.

Overflow

A condition where the result of an arithmetic operation exceeds the representable range.

Sign extension

The process of increasing the bit width of a two's complement number by replicating the sign bit.

One's complement

An alternative signed integer representation where negative numbers are the bitwise complement of the positive counterpart.