Numeric Encoding

Numbers and Numerals

A number is an abstraction of quantity. Humans started with counting numbers like one, two, three, four and so on. Zero came later. Then someone realized that subtracting six from two could be useful and so invented negative numbers. Then integer division led to the creation of rational numbers, and other work resulted in real numbers, imaginary numbers, complex numbers and so on.

A number is represented by a numeral.

Roman Numerals

Well, these aren't much use in modern computers. Enough said.

Hindu-Arabic Numerals

An Arabic Numeral System has an ordered set of digits that includes 0 as its first member. The number of digits is called the base. For example:

• Decimal: digit set = {0,1,2,3,4,5,6,7,8,9}, base = 10.

• Octal: digit set = {0,1,2,3,4,5,6,7}, base = 8.

• Hexadecimal: digit set = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}, base = 16.

• Binary: digit set = {0,1}, base = 2.

You generate Arabic numerals starting at 0 by a really easy algorithm you already know. If you don't know this algorithm, read how a whole class of third graders derived it (plus learned arithmetic).

Conversion

• Hex to and from Binary: This is trivial. Each group of four bits maps exactly to one hex digit. MEMORIZE THIS MAPPING SO YOU CAN DO THE CONVERSION BY SIGHT. Examples:

      48C = 0100 1000 1100
      CAFE54 = 1100 1010 1111 1110 0101 0100
  

• Hex to Decimal: All Arabic numeral systems use place values which you should already be aware of. Examples:

      E2A = 14(162) + 2(161) + 10(160)
          = 14(256) + 2(16) + 10
          = 3626
  

• Decimal to Hex: Keep on dividing by 16, working your way backwards. Example:

             3653
            /    \
          228     5
         /   \
        14    4
       /  \
      0   14
  
      ==> E45
  

Addition

You learned the addition method a long time ago for decimal numerals; the same idea applies to other bases.

Examples in Binary

    11010        101111       001        01
    01101        111101       111        00
   100111       1101100      1000        01

Examples in Hex

   D371        9        37EE        89CA
   26A2        9          F0        CC18
   FA13       12        38DE       155E2

Encoding Integers in Fixed Length Bit Strings

Computers have storage locations with a fixed number of bits. The bits are numbered starting at the right. For example

      3   2   1   0
    +---+---+---+---+
    | 1 | 1 | 0 | 0 |
    +---+---+---+---+

      7   6   5   4   3   2   1   0
    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
    +---+---+---+---+---+---+---+---+

      15  14  13  12  11  10  9   8   7   6   5   4   3   2   1   0
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
    | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Storage locations come in many sizes. Usually we write the values in a storage location out in hex; the contents of our above examples are C, A7, and 39C4, respectively.

An n-bit storage location can store 2ⁿ distinct bit strings so it can encode ("unsigned") integers from 0 through 2ⁿ-1. If we want to include some negative numbers ("signed") we have several encoding options, but by far the most common is called the Two's complement representation, which allocates the bit strings to the numbers -2^n-1 through 2^n-1-1. Please note that a given bit string can be interpreted as either an unsigned number or a signed one.

Here's how things look in a four bit storage location:

For 32-bit locations there are 4294967296 possible bit strings; here are some of them:

Here are the values that can represented in locations of different sizes:

Addition for fixed-length Integers

With adding numbers using fixed length storage locations, our sum might not fit. This is called overflow.

Example: 8-bit location, unsigned numbers. Add C5 + EE. The value should be 1B3, but that won't fit! Why? (Note: in decimal, this is adding 197 + 238 = 435, which is outside the range of 0..255.)

We could

• Clamp the sum at the maximum representable value. This is called saturated arithmetic. In the above example the sum would be FF (or 255 decimal).
• Ignore the carry, making our example's result as B3. This is called modular (or wraparound) arithmetic.

What about signed numbers? Example: Try 6C + 53. You get 6C + 53 = BF. Well, you didn't carry anything out when you added, and the answer still fits in 8 bits, but you added two positive numbers and got a negative result. This too, is overflow. Again we could

• Clamp the sum at the maximum representable value (which in the above example is 7F).
• Leave the result as BF.

Almost all computers do modular arithmetic. Some do modular and saturated arithmetic (e.g. In the Intel x86 family modular addition is done with the add or padd instructions, and saturated addition is done with padds or paddus instructions.

You have to know how to detect overflow! For unsigned numbers this occurs precisely when you carry out of the highest order bit. For signed numbers this occurs precisely when you've added two positive numbers and got a negative result, or added two negative numbers and got a positive result.

Examples of signed modular addition in 8-bit storage locations

    2C       78       42       E0       87       FF
    38       6A       FC       75       DA       C1
    64       E2       3E       55       61       C0

    cry:no   cry:no   cry:yes  cry:yes  cry:yes  cry:yes
    ovf:no   ovf:yes  ovf:no   ovf:no   ovf:yes  ovf:no

Subtraction for fixed-length Integers

Because of the cool way the two's complement representation works, you can subtract a-b by computing a+(-b). So just find the "additive inverse" of b and add it to a. By the way someone with a really sick sense of humor called the additive inverse a "two's complement" and the name stuck. Finding the additive inverse is easy: just invert every bit and add 1!

Example in 8 bits: 44 decimal is 2C in hex or 00101100 in binary. So -44 decimal is found like this

  00101100   =====invert bits=====>   11010011
                                             1
                     add 1            --------
                                      11010100   ==> D4.

So this says that 2C and D4 are inverses. To do a sanity check, add them together and make sure you get zero. Check: 2C+D4=00.

A Subtraction Example in 8 bits:

    E2-83 = E2+(-83) = E2+7D = 5F

Prefix Multipliers for Sizes in Bytes

When numbers get really large you can use some special values:

(The last two aren't officially standardized as of late 2005.)

Examples

  4 Ki   = 22210 = 212 = 4096
  64 Ki  = 26210 = 216 = 65536
  256 Ki = 28210 = 218 = 262144
  16 Mi  = 24220 = 224 = 16777216
  4 Gi   = 22230 = 232 = 4294967296
  32 Ti  = 25240 = 245 = 35184372088832
  2 Pi   = 21250 = 251 = 2251799813685248

  1 EiB is 1024 PiB.

"The total amount of printed material in the world is estimated to be around a fifth of an exabyte." (from Wikipedia, so who knows if it is right)

Real Numbers

A real number is, well, I leave it to you to look up its formal mathematical definition because it isn't really trivial. But you should have some idea. The important thing here is how can we represent them in fixed-length storage locations? We could use integer pairs for numbers we know to be rational, or take a long string and assume the decimal point is always in a certain place (fixed-point representation), or use a "floating-point" representation.

Encoding Floating Point Numbers in Fixed Length Bit Strings

Most modern general purpose computers use an encoding scheme for floating point values called IEEE 754. There are (at least) two representations. One uses 32-bits and the other uses 64-bits.

IEEE 754 Single-Precision (32 bits) Representation

The thirty-two bits are broken into three sections, the sign (s), the fraction (f), and the exponent (e).

  31  30      23  22                             0
+---+-----------+---------------------------------+
| s |     e     |               f                 |
+---+-----------+---------------------------------+

Taking s, f, and e as unsigned values, the value of the number, in decimal, is

Example: What does C28A8000 represent? In binary, it is

    1 10000101 00010101000000000000000

So, s = 1, e = 133. Our value is then -(1.00010101)₂ × 2⁶ = -(1000101.01)₂ which is clearly -69.25 in decimal.

IEEE 754 Double-Precision (64 bits) Representation

The sixty-four bits are broken into three sections, the sign (s), the fraction (f), and the exponent (e).

  63  62           52  51                                      0
+---+----------------+-------------------------------------------+
| s |        e       |                     f                     |
+---+----------------+-------------------------------------------+

Taking s, f, and e as unsigned values, the value of the number, in decimal, is

Special Floating Point Values

NaN means "not a number." Quiet NaNs (QNaNs) propagate happily through computations. Signaling NaNs (SNaNs) can be used to signal serious problems. You can use them to indicate uninitialized variables, for example.

• Overflowing addition, subtraction, multiplication gives the expected infinity
• Adding two positive infinities gives positive infinity
• Adding two negative infinities gives negative infinity
• But infinity minus infinity = NaN
• A finite value divided by an infinity = 0
• Any nonzero value divided by 0 = infinity
• But 0 / 0 = NaN
• infinity × 0 = NaN
• infinity × infinity = infinity
• infinity / infinity = NaN
• Any arithmetic operation on a NaN results in NaN
• A NaN never compares equal to anything, not even another NaN

If you would like to see a more extensive summary of IEEE 754, see Steve Hollasch's. It is quite good.