W1031 Positive Integers

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Binary counter

Prerequisites

• Number Systems (W1011)
• Computer History (W1021)
• Computer Architecture (W1022)

Background

The process of transforming information from one format into another, especially for storage or transmission, is called encoding. The opposite process, transforming the stored form to the original format, is called decoding. Because modern computers are digital and store data as a series of bits, where each bit can possess only the value of one or zero, all data that we store must ultimately be represented in this format.

Positive integers can be encoded simply by relying on the binary number system. Given n bits, we can encode any number from zero through $2^{n}-1$.

An egg

"It is allowed on all hands, that the primitive way of breaking eggs before we eat them, was upon the larger end: but his present Majesty's grandfather, while he was a boy, going to eat an egg, and breaking it according to the ancient practice, happened to cut one of his fingers. Whereupon the Emperor his father published an edict, commanding all his subjects, upon great penalties, to break the smaller end of their eggs." —Jonathan Swift, Gulliver's Travels

Bits are organized into bytes, which are themselves organized into the addressable memory space of the computer. Bytes themselves may further be organized into words. To complete our encoding scheme for positive integers, we have two decisions to make:

• Should the least-significant bit placed be in position "0" or position "7" within the byte?
• Should the least-significant byte be placed in the lowest-address position within a word, or the highest-address position?

These are decisions about Endianness, which describes the starting point of a sequential ordering of elements.

• Little endian indicates that the least-significant element is placed in the lowest-enumerated position
• Big endian indicates that the least-significant element is placed in the largest-enumerated position

Endianness is an issue of design on a platform, and both methods are in use. Because a single byte is accessed as a unit, endianness of the bits within a byte tends to be less important than the transmission of a byte via a network. The ordering of the bytes within memory, however, is extremely important because the proper encoding of data requires that we access the bytes in the proper order.

Big endian

Little endian

Let's consider a single byte, and label the bits from right (least significant bit) to left (most significant bit):

How can we represent the number $73_{10}$, recalling that this is equivalent to $49_{16}$? In binary, the integer is represented as:

Note that the bit at position zero is least significant, and represents $2^{0}$ whereas the bit at position seven is most significant, and represents the value $2^{7}$.

Let's consider a larger positive integer, such as $13,695_{10}$, recalling that this is equivalent to $357F_{16}$. The largest positive integer that we're able to store in a single, 8-bit byte is 255 ($2^{8}-1$), so we'll need at least 2 bytes to store this integer. Two bytes can contain up to $2^{16}-1$ or $65,535_{10}$. At this point, we have two choices: we can either store the least significant byte in a lower address, or we can store it in a higher address. This would appear as one of the following:

Big endian

Little endian

Key Concepts

Key Concepts

• Encoding is the process of transforming information from one format into another, especially for storage or transmission
• Decoding is the process of transforming the stored or transmitted form to the original format
• Positive integers can be encoded simply by relying on the binary number system
  • Given n bits, we can encode any number from zero through $\color {White}2^{n}-1$
• Endianness describes the starting point of a sequential ordering of elements
  • Little endian indicates that the least-significant element is placed in the lowest-enumerated position
  • Big endian indicates that the least-significant element is placed in the largest-enumerated position

References

• Endianness (Wikipedia)
• Bytes (Wikipedia)