Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 67 ยท Data Representation

Signed Integers and Two's Complement

Learn sign-magnitude, ones' complement and two's complement, value ranges, overflow and sign extension, with Python code that simulates fixed-width integers.

A fixed number of bits can hold only a fixed number of patterns. An 8-bit register has 256 of them. If all 256 are used for non-negative numbers you get 0 to 255 (an unsigned integer). To also store negative numbers, the patterns must be shared out in some way. Over the years designers tried several schemes, and one of them, two's complement, won so completely that almost every computer today uses it.

This lesson shows three ways to encode signed integers, explains why two's complement makes the hardware simple, and gives you tools to work with fixed-width integers in Python, whose own integers have no limit. It builds on Number Systems and Conversions.

Unsigned integers

With n bits, an unsigned integer ranges from 0 to 2^n - 1.

Bits Unsigned range
8 0 to 255
16 0 to 65,535
32 0 to 4,294,967,295
64 0 to 18,446,744,073,709,551,615

Unsigned integers are right for counts, sizes and memory addresses, which cannot be negative.

Sign-magnitude

The most obvious idea: reserve the leftmost bit as a sign (0 = positive, 1 = negative) and use the other bits for the size (magnitude). In 8 bits, +5 is 0000 0101 and -5 is 1000 0101.

It is easy for people to read, but it has two problems:

  • There are two zeros: 0000 0000 (+0) and 1000 0000 (-0). Comparing numbers needs special cases.
  • Addition needs different logic depending on the signs: to add +5 and -3 the hardware must decide to subtract magnitudes and pick the right sign.

Ones' complement

To negate a number in ones' complement, flip every bit. So -5 is the flipped pattern of 0000 0101, which is 1111 1010. Addition works with a small trick (an "end-around carry"), but there are still two zeros: 0000 0000 and 1111 1111. Some historical machines used it; none that you will meet today do.

Two's complement

Two's complement fixes both problems. To negate a number: flip all the bits, then add 1.

  • +5 = 0000 0101
  • flip: 1111 1010
  • add 1: 1111 1011 = -5

Another way to see it: in an n-bit two's complement system the leftmost bit has a negative weight of -2^(n-1). For 8 bits the weights are -128, 64, 32, 16, 8, 4, 2, 1. The pattern 1111 1011 is -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5. Check it against the flip-and-add rule: they agree.

flowchart LR
  A["+5<br/>0000 0101"] -->|"flip all bits"| B["1111 1010"]
  B -->|"add 1"| C["-5<br/>1111 1011"]
  C -->|"flip all bits"| D["0000 0100"]
  D -->|"add 1"| A

Negating twice returns the original number.

Why is this the winner?

  1. One zero: only 0000 0000.
  2. Addition and subtraction use the same adder for signed and unsigned numbers. The adder just adds bit patterns and discards any carry out of the top; the result is correct either way. Subtraction a - b is a + (-b): flip b, add 1.
  3. The sign is still the leftmost bit, so checking "is it negative?" looks at one bit.
  4. The range has one more negative value than positive ones.

Range

For n bits, two's complement covers -2^(n-1) to 2^(n-1) - 1:

Bits Smallest Largest
8 -128 127
16 -32,768 32,767
32 -2,147,483,648 2,147,483,647
64 -9,223,372,036,854,775,808 9,223,372,036,854,775,807

The range is lopsided because zero takes one of the non-negative patterns. The most negative value (-128 in 8 bits) has no positive partner: negating it gives itself, since flip-and-add returns 1000 0000. Many real bugs hide here, such as abs(INT_MIN) still being negative.

Fixed-width integers in Python

Python integers grow without limit, so to see what hardware does we must simulate a fixed width. The trick is to mask with (1 << bits) - 1, which keeps only the lowest bits bits. See Bitwise Operators for the operators used here.

Python Encode and decode two's complement

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table shows -1 as all ones. That is a useful fact: in two's complement, all ones always means -1, whatever the width. The same bit pattern is 255 if you read it as unsigned. The bits do not know whether they are signed; the interpretation lives in the instructions and types that use them.

Negating with flip and add one

Python Negate by flipping bits and adding 1

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the last two rows. Negating 0 gives 0 (one zero only), and negating the pattern 1000 0000 (which means -128 as signed) gives the same pattern back: the lopsided range in action.

Overflow

When a result does not fit in the available bits, the stored value is wrong; this is called overflow. In two's complement the arithmetic simply wraps around modulo 2^n. Adding 1 to the largest positive number gives the most negative one: 127 + 1 in 8 bits becomes -128.

Python Wrap-around in 8 bits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first line crosses from 127 to -128. Real programs suffer from the same wrap-around when a counter or a size calculation exceeds its type. The detection rules, and the carry and overflow flags a CPU keeps, are the topic of Binary Arithmetic and Overflow.

Signed overflow is a classic bug source. In C, signed overflow is undefined behavior, so the compiler may assume it never happens. Unsigned arithmetic wraps by definition. Check your language rules before relying on wrap-around.

Sign extension

A value often has to move from a narrow register to a wide one, for example from 8 to 32 bits. The number must keep its value. For unsigned numbers, fill the new upper bits with zeros (zero extension). For two's complement, copy the sign bit into all the new bits (sign extension).

  • 8-bit +5 0000 0101 becomes 32-bit 0000...0000 0101.
  • 8-bit -5 1111 1011 becomes 32-bit 1111...1111 1011, which is still -5.

Zero-extending a negative number would turn -5 into 251. Processors provide separate instructions for both kinds of widening, and you will see sign extension again for immediate fields in Instruction Formats and Encoding.

Python Sign extension and truncation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Narrowing a value ("truncation") just drops the high bits, so the value changes unless it already fit. That is why converting a large long to a short can produce surprising results.

Ones' complement and two's complement compared

Both schemes negate a number with a simple bit operation, but they behave differently in the places that matter to hardware: how many zeros exist, what the range is, and how addition works.

Negation. Ones' complement: flip every bit. Two's complement: flip every bit, then add 1. Equivalently, the two's complement of x is 2^n - x, and the ones' complement is 2^n - 1 - x.

Two zeros. In ones' complement, 0000 0000 (+0) and 1111 1111 (-0) are both zero, which means a comparison must treat two patterns as equal. In two's complement there is one zero, and the extra pattern 1000 0000 extends the range to -128.

Addition and the end-around carry. In two's complement, the carry out of the top bit is simply dropped. In ones' complement, the carry out must be added back into the lowest bit (the end-around carry) to get the right answer. Example in 8 bits, 5 + (-3):

Text
   0000 0101     (+5)
 + 1111 1100     (-3 in ones' complement)
 -----------
 1 0000 0001     carry out = 1
   0000 0001
 +         1     end-around carry
 -----------
   0000 0010     = +2, correct

The end-around carry costs an extra addition step (or a second pass through the adder), which is why two's complement won.

Ones' complement Two's complement
Negate Flip bits Flip bits, add 1
Zeros Two (+0 and -0) One
Range (n bits) -(2^(n-1) - 1) to 2^(n-1) - 1 -2^(n-1) to 2^(n-1) - 1
Carry out of top bit Add back to the lowest bit Ignore (discard)
Subtraction A + flipped B, with end-around carry A + flipped B + 1, no extra step
Used today Internet checksums (a ones' complement sum) Almost every CPU
Python End-around carry versus plain two's complement

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice 7 + (-7): the ones' complement result is 1111 1111, which is -0, while the two's complement result is 0000 0000. Both mean zero, but only two's complement gives the single canonical pattern.

Choosing a representation

Scheme Zeros Range (8 bits) Hardware cost
Sign-magnitude Two -127 to +127 Needs sign logic
Ones' complement Two -127 to +127 End-around carry
Two's complement One -128 to +127 Same adder as unsigned

Floating-point formats still use a sign bit plus magnitude, see Floating-Point Numbers and IEEE 754. A related scheme called excess-K (bias) is used for the exponent field there.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the 8-bit two's complement representation of -3?

    +3 is 0000 0011. Flip to 1111 1100 and add 1 to get 1111 1101.
  2. 2. What range does a 16-bit two's complement integer cover?

    The range is -2^15 to 2^15 - 1, which is -32,768 to 32,767.
  3. 3. Why do computers prefer two's complement over sign-magnitude?

    Two's complement needs no special sign handling in the adder and has a unique zero. The number of patterns is the same in all schemes.
  4. 4. In 8-bit two's complement, what is 127 + 1?

    0111 1111 plus 1 is 1000 0000, which is -128 in two's complement (overflow).
  5. 5. An 8-bit pattern 1111 1011 is widened to 16 bits while keeping the value -5. What do you do?

    Sign extension replicates the sign bit, producing 1111 1111 1111 1011, which is still -5.

Summary

  • n unsigned bits cover 0 to 2^n - 1; n two's complement bits cover -2^(n-1) to 2^(n-1) - 1.
  • Sign-magnitude and ones' complement have two zeros; two's complement has one.
  • Negate a two's complement number by flipping the bits and adding 1; the top bit has weight -2^(n-1).
  • Arithmetic wraps modulo 2^n, so overflow silently flips 127 + 1 to -128 in 8 bits.
  • Widen signed values with sign extension, unsigned values with zero extension; narrowing truncates.
  • Bits carry no sign by themselves; the instruction or type decides how to interpret them.

Continue with Binary Arithmetic and Overflow.