W1031 Positive Integers

From Coder Merlin
Jump to navigation Jump to search
Binary counter

Prerequisites[edit]

Background[edit]

The process of transforming information from one format into another, particularly for storage or transmission, is termed encoding. The opposite process, transforming the stored form to the original format, is termed decoding. Because modern-day 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 may be encoded simply by relying on the binary number system. Given n bits, we can encode any number from zero through .

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. In order to complete our encoding scheme for positive integers, we have two decisions to make:

  • Should the least-significant bit be located in position "0" or position "7" within the byte?
  • Should the least-significant byte be located 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 particular 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, as 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):

Byte-Bit-Order.png

How can we represent the number , recalling that this is equivalent to ? In binary, the integer is represented as:

Byte-Bit-Order-0x49.png

Note that the bit at position zero is least significant, and represents while the bit at position seven is most significant, and represents the value .

Let's consider a larger positive integer, such as , recalling that this is equivalent to . The largest positive integer that we're able to store in a single, eight-bit byte is 255 (), so we'll need at least two bytes to store this integer. Two bytes can contain up to or . 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[edit]

KeyConceptsIcon.png
Key Concepts
  • Encoding is the process of transforming information from one format into another, particularly for storage or transmission
  • Decoding is the process of transforming the stored or transmitted form to the original format
  • Positive integers may be encoded simply by relying on the binary number system
    • Given n bits, we can encode any number from zero through
  • 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[edit]


Designed with pride in Silicon Valley, CA, USA