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 irrational numbers, real numbers, transfinite numbers, imaginary numbers, complex numbers and so on.

A number is represented by a numeral.

Egyptian Numerals

Egyptians wrote numerals in hieroglyphs for thousands of years; here are the important symbols and their numeric values:

Notice that these numerals could be written from right-to-left or left-to-right or vertically or a combination of vertical and horizontal. Here is one way to represent twenty-one thousand two hundred thirty-seven:

We don’t use these numerals in computer systems today, but history is important, so please read more about these numerals at Wikipedia or elsewhere.

Roman Numerals

Well, these aren’t much use in modern computers, either. Enough said. Besides, they’re really hard to understand, and they don’t have a zero, or wait...maybe they do?

Positional Numeral Systems

A Positional Numeral System has an ordered set of digits that includes 0 as its first member. The number of digits in the set is called the base. By far the most common of these is the Hindu-Arabic Numeral System, or Arabic Numeral System, which has a base of 10, and whose glyphs are these:

  0  1  2  3  4  5  6  7  8  9

There are other positional systems, too:

• Devanagari (base 10): ० १ २ ३ ४ ५ ६ ७ ८ ९
• Mongolian (base 10): ᠐ ᠑ ᠒ ᠓ ᠔ ᠕ ᠖ ᠗ ᠘ ᠙
• Kannada (base 10): ೦ ೧ ೨ ೩ ೪ ೫ ೬ ೭ ೮ ೯
• Tamil (base 10): ௦ ௧ ௨ ௩ ௪ ௫ ௬ ௭ ௮ ௯
• Maya (base 20)
• Kaktovik Iñupiaq (base 20)

In computing, though, the Hindu-Arabic numerals dominate. We can extend this system to bases other than 10 by adding or removing glyphs. Bases up to 36 are traditionally handled by adding the Latin letters A-Z. The most common systems in computing are:

• 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 positional numerals starting at 0 by a really easy algorithm you already know.

Third Graders, Binary Numbers, and the Socratic Method

For some inspiration, read about a third grade class’s adventures in learning about and using binary numerals.

Conversion

Let’s convert Hex to and from Binary. Wait, 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

For numbers involving only two hex-digits you can do this in your head if you have memorized your multiples of 16: 0→0, 1→16, 2→32, 3→48, 4→64, 5→80, 6→96, 7→112, ... F→240. This gives you the contribution of the first hex digit, so just “add in” the second.

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

       3653
      /    \
    228     5
   /   \
  14    4
 /  \
0   14

==> E45

Binary to Decimal: Read left-to-right, doubling as you go and adding one where necessary. Example:

10110110

This method is, in some circles, known as Dorin’s Way.

What about conversion between arbitrary bases? Well, it’s pretty cool to know how to generic conversions, but our focus today is stricly on binary, hex, and decimal.

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

Subtraction, Multiplication, and Division

You probably learned algorithms for these operations, long ago; the good news is that they are base-independent. Try some of these out in binary: you'll find they're quite simple, though they might take longer since there are so many bits, even for small quantities.

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. Examples:

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 3F25, respectively.

An $n$-bit storage location can store $2^n$ distinct bit strings so it can encode (“unsigned”) integers from 0 through $2^n-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, with signed values using the two’s complement representation:

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:

Fixed-Length Integer Addition

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.)

Saturated vs. Modular Addition

There are two main approaches to dealing the problem of a sum not being able to fit. We could

• Clamp the sum at the maximum representable value. This is called saturated arithmetic. In the previous 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.

Overflow Detection

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 the two’s complement and the name stuck. Finding the additive inverse is easy: just invert every bit and add 1!

Hold on! Before you start doing this, MAKE SURE YOU UNDERSTAND WHY THIS TECHNIQUE IS CORRECT!

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

By the way, if you start “thinking in hex”, you can do this stuff much faster. We’ll see better techniques in class.

Prefix Multipliers for Sizes in Bytes

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

(Everything up to yotta is part of the official SI system of units. The xona, weka, etc. prefixes are being looked at; alternatives for $10^{27}$ and $10^{30}$ are nona and dogga ... because it’s fun to say “doggabyte.”) Possibly even better: There is an online petition you can sign to get the SI to make “hella” the official prefix for 10²⁷.

  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.

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 (called a 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).

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).

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

More Information

Here’s Tom Scott explaining floating point:

If you would like to see a more extensive summary of IEEE 754, see Steve Hollasch’s. It is quite good. Oh, and you should read Goldberg’s classic paper.

If you need to see online IEEE 754 converters, you can use mine (which is pretty good), or the one at City University of New York, which is awesome.