Computation in a computer using integers is performed using twos complement representation.

Integers can thus take two forms:

  • Unsigned integers
  • Signed integers

Signed integers are useful in representing only positive numbers(No decimal points), including zero.

Unsigned integers are useful for representing both positive and negative numbers including zero.

Within the above classes of integers have variations in bit width also. This can include:

  • 8 bit signed integers
  • 8 bit signed integers
  • 16 bit unsigned integers
  • 16 bit signed integers
  • 32 bit unsigned integers
  • 32 bit signed integers and so on

Relation between bit width and range

The range of an integer type is the values that can be represented between minimum and maximum.

  • For an N bit unsigned integer this is between [0] – [2^(N)-1]
  • For an N bit signed integer this is between [-2^(N-1)] – [2^(N-1)-1]. The upperbound for this is [-2^(N-1)-1] as the value 0 needs representation too thus it is [2^(N-1)-1] and not[2^(N-1)]

Example for an 8 bit integer:

  • UnsignedRange is between 0 and 2^(8)-1 = 256-1=255 therefore the range is [0,+255]
  • SignedRange is between [-2^(8-1)] and [2^(8-1)-1] = -128 to +127 therefore the range is [-128,+127]

Implications of limited integer range(overflow)

Overflow has two forms:

  • Negative overflow-When the result of a computation goes below the minimum number representable in an N integer computation and representation(This is not the same as underflow in floating point computer arithmetic).
  • Positive overflow-When the result of a computation goes above the maximum number representable in an N integer computation and representation.

The difference bewtween real world computation on numbers and computation of integers in computers is that real world numbers/integers can have unlimited range.

Overflow in unsigned integers computation(Example: addition operation)

In a computer an N bit unsigned integer addition is a modulo (2^N) operation as an positive overflow wraps around to the minimum representable number and a negative overflow wraps around to the maximum representable number. This is shown in the surface plot below of the addition of two unsigned integers:

unsigned_integer_addition

As can be seen, it reaches a point when the addition result goes beyond 255 and this wraps back round to zero, The same is true for negative overflow which wraps around to positive. This behavior could seem very weird in programming languages that do not warn of an impending overflow. Example: If Mary is 5 and Susan is 8, what is the difference of Susan’s age from Mary’s age. The result believe it or not in unsigned 8 bit would give you -253. Negative overflow just occurred.

Overflow in signed integer computation(Example: addition operation)

signed_integer_addition

The same case applies for signed integers, only that instead of a positive overflow wrapping around to zero, it wraps back round to the minimum value representable which is negative. Vice versa for positive overflow.

Next episode: Performing binary arithmetic by hand to see why the above results show up and introduction to saturation arithmetic.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s