Sign-magnitude, 1's and 2's complement

Why it exists

A bit string has no sign by itself. To store -5 in 8 bits we must agree on a rule that says which patterns stand for negative numbers. Three rules have been used in real machines. Today almost every computer uses 2's complement, because with it the same adder circuit adds signed and unsigned numbers, subtraction is addition of the negated number, and there is exactly one zero. The other two systems still appear in GATE questions, mostly to test whether you know their defects (two zeros, a special end-around carry), and the floating-point format in IEEE 754 uses sign-magnitude for the whole number and a biased (excess) code for the exponent.

Prerequisites

You should be able to convert between decimal and binary and to count bits, as covered in number systems and conversion.

Precise definitions

Fix a word of $n$ bits $b_{n-1}\,b_{n-2}\dots b_0$. The leading bit $b_{n-1}$ is the sign bit in every signed system below: 0 means non-negative, 1 means negative (for the three systems below). As an unsigned number the word has the value $\sum b_i 2^i$, range $0$ to $2^n - 1$.

Sign-magnitude. The sign bit gives the sign and the remaining $n-1$ bits give the magnitude. Value $= (-1)^{b_{n-1}} \cdot \sum_{i<n-1} b_i 2^i$. Range $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$. There are two zeros: $00\dots0$ and $10\dots0$. To negate, flip the sign bit.

1's complement. A negative number is the bitwise complement of the positive one. Value $= -b_{n-1}(2^{n-1} - 1) + \sum_{i<n-1} b_i 2^i$. Range $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$. There are two zeros: $00\dots0$ and $11\dots1$. To negate, flip every bit. Addition needs an end-around carry: a carry out of the top bit is added back into the least significant bit.

2's complement. The value is $-b_{n-1}\,2^{n-1} + \sum_{i<n-1} b_i 2^i$. Equivalently, a pattern with sign bit 1 and unsigned value $u$ stands for $u - 2^n$. Range $-2^{n-1}$ to $+2^{n-1}-1$, which is asymmetric (one more negative number). There is one zero. The pattern $10\dots0$ is $-2^{n-1}$ and has no positive partner.

Negation in 2's complement. The negative of $x$ in $n$ bits is $2^n - x$ (taken modulo $2^n$). Since $2^n - x = (2^n - 1 - x) + 1$, and $2^n - 1 - x$ is just $x$ with every bit flipped, the rule is invert and add 1. A faster hand rule: starting from the right, copy the bits up to and including the first 1, then flip all the bits to the left of it. The only number that is its own negative (apart from 0) is $-2^{n-1}$, so negating it overflows.

Sign extension. To widen an $n$-bit 2's complement number to $m > n$ bits, copy the sign bit into the new high bits. The value is unchanged. (For an unsigned number pad with zeros instead.) Truncation to fewer bits keeps the low bits and may change the value.

Shifts. In 2's complement, shifting left by one bit multiplies by 2 if the result is still representable. An arithmetic shift right copies the sign bit into the vacated position and computes $\lfloor x/2 \rfloor$ (rounding toward minus infinity). A logical shift right fills with 0 and treats the word as unsigned. In C, integer division truncates toward zero, so $-5/2$ is $-2$ while $-5 \gg 1$ is $-3$ on a machine with arithmetic shifts.

Excess-$K$ (biased) representation. The stored unsigned value is the true value plus $K$, so the true value is stored minus $K$. For $n$ bits the common bias is $K = 2^{n-1}$, which gives the same ordering as the signed numbers. Excess-128 in 8 bits equals the 2's complement pattern with the sign bit flipped. The IEEE 754 exponent uses excess-127 (single) and excess-1023 (double).

Radix complements (for arithmetic by hand). For $n$ digits in base $r$, the $(r-1)$'s complement of $N$ is $r^n - 1 - N$ (flip every digit to $r-1-d$) and the $r$'s complement is $r^n - N$. For $r = 2$ these are the 1's and 2's complements; for $r = 10$ they are the 9's and 10's complements. Subtraction $A - B$ is done as $A + (r\text{'s complement of } B)$: a carry out of the top digit is dropped and means the result is non-negative; no carry means the result is negative and equals minus the $r$'s complement of the sum.

How it works

Step through the animation. Each pattern is computed by a script and decoded again by each system's own rule in the tests. The sign bit is ringed.

+5: sign bit 0, magnitude 101

Why 2's complement works: modulo $2^n$ arithmetic is a closed system, and in it $-x$ and $2^n - x$ are the same number. A circuit that adds modulo $2^n$ therefore adds signed numbers correctly, with no knowledge of the signs, as long as the true result is representable. That is what you see in fixed-point arithmetic and in the adder and subtractor circuits.

Worked examples

#include <stdio.h>
#include <stdint.h>
 
int main(void) {
    int8_t a = -37;
    uint8_t u = (uint8_t)a;
    printf("%d as unsigned byte %u, hex %02X\n", a, u, u);
    int8_t m = -128;
    int8_t neg = (int8_t)(-m);
    printf("-(-128) in 8 bits: %d\n", neg);
    printf("%d %d\n", -5 >> 1, -5 / 2);
    int wide = 255;
    int8_t narrow = (int8_t)wide;
    printf("%d\n", narrow);
    int8_t s = (int8_t)0xA5;
    int16_t e = s;
    printf("%d %d %04X\n", s, e, (uint16_t)e);
    return 0;
}

-37 as unsigned byte 219, hex DB
-(-128) in 8 bits: -128
-3 -2
-1
-91 -91 FFA5

Cheat box

Traps and GATE patterns

Connections

The addition of 2's complement numbers and the meaning of the carry and overflow flags is the topic of fixed-point arithmetic. The hardware that subtracts by adding the complement is in adders and subtractors. C's int, short and char use these rules, which is why integer promotion and conversions behave as they do. The exponent field in IEEE 754 is excess-127.

PYQs

Consider the 8-bit signed integers X, Y and Z
represented using the sign-magnitude form. The
binary representations of X and Y are as follows:

X: 10110100
Y: 01001100

Which of the following operations to compute Z
result(s) in an arithmetic overflow?

In a system, numbers are represented using 4-
bit two's complement form. Consider four
numbers
N1 = 1011, N2 = 1101, N3 = 1010 and N4 =
1001 in the system.

Which of the following operations will result in
arithmetic overflow?

The number  6 can be represented as 1010 in 4-
bit 2's complement representation.
Which of the following is/are CORRECT 2's
complement representation(s) of -6?

Consider a system that uses 5 bits for representing
signed integers in 2's complement format. In this
system, two integers A and B are represented as A
= 01010 and B = 11010. Which one of the
following operations will result in either an
arithmetic overflow or an arithmetic underflow?

Let R1 and R2 be two 4-bit registers that store
numbers in 2's complement form. For the operation
R1 + R2, which one of the

following values of R1 and R2 gives an arithmetic
overflow?

Consider Z = X - Y where X, Y and Z are all in sign-
magnitude form. X and Y are each represented in n
bits. To avoid overflow, the representation of Z would
require a minimum of:

DIGITAL LOGIC

In 16-bit 2's complement representation, the
decimal number  28 is:

Let X be the number of distinct 16-bit integers in 2's
complement representation. Let Y be the number of
distinct
16-bit
integers
in
sign
magnitude
representation. Then X - Y is _____

The 16-bit 2's complement representation of an
integer is 1111 1111 1111 0101; its decimal
representation is __________.

The smallest integer that can be represented by an
8-bit number in 2's complement form is

P is a 16-bit signed integer. The 2's complement
representation of P is (F87B)16. The 2's
complement representation of 8 × P is

We consider the addition of two 2's complement
numbers bn-1 bn-2 ... b0 and an-1 an-2 ... a0. A binary
adder for adding unsigned binary numbers is used to
add the two numbers. The sum is denoted by cn-1 cn-2
... c0 and the carry-out by cout. Which one of the
following options correctly identifies the overflow
condition?

The range of integers that can be represented by an
n-bit 2's complement number system is:

Self-check

Revision card

References