Representations: Quite a Bit About Bits

00002  =  016
00012  =  116
00102  =  216
00112  =  316
01002  =  416
01012  =  516
01102  =  616
01112  =  716

10002  =  816
10012  =  916
10102  =  A16
10112  =  B16
11002  =  C16
11012  =  D16
11102  =  E16
11112  =  F16
When working with the low-level bits of a computer system, we typically resort to the symbols 0 and 1 to represent all of the values stored and states in the machine. In fact, binary representation was a key to the invention of the earliest computers.

Unfortunately, it is difficult to look at hundreds of zeroes and ones and have them make any sense. They all seem to blend into one another unless we can organize them in some useful way. The most common way to organize bits is by grouping them into "half-bytes," or 4-bit, chunks. Then, each of those 16 possible patterns of 0/1 are represented by a hexadecimal digit in the range of 0-F, as shown in the table.

By using the hexadecimal system, it is easy to write long strings of bits in a compact form. For example,

110101110010101011010010110101100011010111111
simply causes one's eyes to water. But let's break it up into 4-bit chunks, starting from the rightmost bit: 
   110101110010101011010010110101100011010111111
Notice that there are not enough bits for the leftmost group to be complete. We will simply pad it with some extra zeroes: 
000110101110010101011010010110101100011010111111
Next, we determine the hex digit for each of the groups: 
000110101110010101011010010110101100011010111111



 1AE55A5AC6BF
Thus, the binary string 110101110010101011010010110101100011010111111 is equivalent to the hexadecimal string 1AE55A5AC6BF.

But, what does it mean???

Notice that we are referring to the zeroes and ones as a string, rather than as a number; this is not accidental. A group of zeroes and ones (or their equivalent representation in a another system like hexadecimal) have no value associated unless we decide to assign a value to them. The zeroes and ones could represent integers, real numbers, characters, images, sounds, addresses for memory locations in the computer or even instructions to the computer. The meaning of the string is unknown without a context. Below we begin to examine some of the meanings which might be associated with these strings.

ASCII Characters

The ASCII character code is a somewhat arbitrary system which places each typed character on the computer's keyboard into a 7 (or 8) bit sequence. For example, consider the bits:

010000012 = 4116
What character does this represent? It turns out that inspection of an ASCII table shows us that this is the uppercase "A" character. Why isn't it the lowercase "t" character? Well, simply, because it isn't. Someone had to agree on a code and put it into service. This is that standard code. There are some sensible qualities to the code. For example, while it's not clear why "A" should be code 4116, it makes sense that code 4216 is "B" and that code 4316 is "C", etc. Not all standard systems are organized that way. For example the EBCDIC system once used by IBM has gaps between the letters I and J and between R and S. Go figure.

Unsigned Binary Integer

BITS

High order bit is leftmost, low order (least significant) bit is rightmost. The location of each bit determines its value: 

     33222222222211111111110000000000
     10987654321098765432109876543210
     BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
     |                    |         |
     231 place            210        20

EXAMPLE

What is the 32-bit unsigned binary integer representation for the decimal integer 86420?

SOLUTION

1. Succesively divide by 2 until the result is zero. The remainders of these divisions will be the bits used to construct the solution. 

     86420 ÷ 2 = 43210     rem 0    Low order bit
     43210 ÷ 2 = 21605     rem 0
     21605 ÷ 2 = 10802     rem 1 
     10802 ÷ 2 =  5401     rem 0
      5401 ÷ 2 =  2700     rem 1
      2700 ÷ 2 =  1350     rem 0
      1350 ÷ 2 =   675     rem 0
       675 ÷ 2 =   337     rem 1
       337 ÷ 2 =   168     rem 1
       168 ÷ 2 =    84     rem 0
        84 ÷ 2 =    42     rem 0
        42 ÷ 2 =    21     rem 0
        21 ÷ 2 =    10     rem 1
        10 ÷ 2 =     5     rem 0
         5 ÷ 2 =     2     rem 1
         2 ÷ 2 =     1     rem 0
         1 ÷ 2 =     0     rem 1    High order bit

2. Organize the remainder bits into the binary integer:

10101000110010100
3. Pad the bits to the left with zeroes to bring to a total of 32:
000000000000000 10101000110010100
4. Convert to hex:
0000 0000 0000 0001 0101 0001 1001 0100

00015194



Sign-Magnitude Signed Binary Integer

BITS
33222222222211111111110000000000
10987654321098765432109876543210
SBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
 where
S = 1 for negative number, 0 for non-negative
The remaining bits in position n represents 2n place.

EXAMPLE

What is the 32-bit sign-magnitude binary integer representation for the decimal integer -47?


SOLUTION

1. S = 1, for negative number.

2. Solve as for an unsigned integer for the remaining 31 bits.

4710 = 1011112
3. Organize the bits, padding with zeroes between the sign and the magnitude:
1 0000000000000000000000000 101111

4. Convert to hex:
1000 0000 0000 0000 0000 0000 0010 1111

8000002F




Offset Signed Binary Integer

BITS
00000000
76543210
BBBBBBBB
 where the representation is actually the value to be encoded plus some offset value, which depends on the final (fixed) length of the result. For example, for an 8-bit offset integer, the representation is done as follows.
Begin with the number to be encoded.
Add 127 to the number to be encoded.
Note: 127 is chosen because it is 2n-1-1 where n is the number
of bits in the final representation
The representation is now encoded as an 8-bit unsigned integer.
The examples, below, show how this technique would be used to represent -127, -85, 0, +42 and +127 in 8-bit offset: 

                        value       
 value to               after 
 be encoded             offset      encoding
  
   -127     +  127   =      0   =   00000000
    -85     +  127   =     42   =   00101010
      0     +  127   =    127   =   01111111
    +42     +  127   =    169   =   10101001
   +128     +  127   =    255   =   11111111
Both sign-magnitude and offset representations have a significant limitation. They cannot be used reliably for mathematical manipulation. Consider, for example, the 8-bit sign-magnitude representations for +1 and -1. Clearly these two values should add up to zero, but they do not: 
   00000001    =   +1 in sign-magnitude
+  10000001    =   -1 
 ----------
   10000010    =   -2
According to this, +1 plus -1 equals -2. Wrong! Note that binary math works just like decimal math, but with fewer digits. In other words, all we need to remember is 0+0=0, 0+1=1, and 1+1=0, carry the 1.

Likewise, offset representations won't work: 

   10000000    =   +1 in 127-offset
+  01111110    =   -1
 ----------
   11111110    = +127
Again, we get silly answers: +1 plus -1 equals +127. A system of signed binary numbers must allow us to do binary math correctly. The following representation fits that requirement.


2's-Complement Signed Binary Integer

BITS

33222222222211111111110000000000
10987654321098765432109876543210
SBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
where
S = 0 for non-negative numbers

Interpretation:

the remaining 31 bits represent the magnitude of the non-negative number.
S = 1 for negative numbers

Interpretation:

Invert all the bits 2's-complement number.
Add 1.
The resulting 32 bits represent the magnitude of the negative number.

Note: this is the same as subtracting 1 from the 2's-complement number and then inverting the bits. Click here for more background.

EXAMPLE 1

What is the 32-bit 2's-complement signed binary integer representation for the decimal integer -47?


SOLUTION

1. Solve as for an unsigned integer for the magnitude:

4710 = 1011112
2. Pad with zeroes to form a 32-bit number:
00000000000000000000000000 101111
3. If the value was non-negative, the answer is now complete.

4. For a negative number we must next invert all the bits:

11111111111111111111111111010000
5. Add one to the result:
11111111111111111111111111010001
6. Convert to hex:
1111 1111 1111 1111 1111 1111 1101 0001

FFFFFFD1


EXAMPLE 2

What is the value of the 2's-complement number represented by the hexadecimal number FFFFFF99?


SOLUTION

1. Write out the bits:

1111 1111 1111 1111 1111 1111 1001 1001
2. Since the first bit is a 1 this is a negative number. We must continue. Invert all the bits.
0000 0000 0000 0000 0000 0000 0110 0110
3. Add 1.

0000 0000 0000 0000 0000 0000 0110 0111
4. Convert this result to decimal:
11001112 = 10310
5. Since the value is negative, the original binary number was the 2's-complement representation of the decimal number -103.


BINARY ADDITION OF 2'S-COMPLEMENT NUMBERS

Binary addition of a 2's-complement signed integer is very simple. The rules are the same as decimal addition, except that the carry of 1 happens when 1 is added to 1. That is:

0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 0, carry the 1
A carry from the most significant bit position is discarded. The carry out from the most significant bit must be the same as the carry in to that bit (either both 0 or both 1), otherwise an overflow or underflow error has occurred.

For example, using 4-bit 2's-complement signed binary integers:
  0 0 1 1  note: 00112 = 310
+ 0 0 1 1  =  3
---------
  0 1 1 0  =  6; carry in = carry out of sign bit = 0

  1 0 0 1  = -7
+ 0 0 1 1  =  3
---------
  1 1 0 0  = -4; carry in = carry out = 0

  1 0 0 1  = -7
+ 1 0 0 1  = -7
---------
  0 0 1 0  = ERROR; 1 = carry out bit; 0 = carry in to sign bit

  0 1 1 1  =  7
+ 0 1 1 1  =  7
---------
  1 1 1 0  = ERROR, 0 = carry out; 1 = carry in

  1 1 0 1  = -3
+ 1 1 0 1  = -3
---------
  1 0 1 0  = -6; carry out = carry in = 1; carry out bit is discarded.

  1 1 0 1  = -3
+ 0 0 1 1  =  3
---------
  0 0 0 0  = 0; carry out = carry in = 1; carry out bit is discarded.

Homework


IEEE 32-Bit Floating Point Format

BITS
33222222222211111111110000000000
10987654321098765432109876543210
SEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFF

= (-1)s2e-1271.f

where
s = S
e = EEEEEEEE, e > 0, e < 255
f = FFFFFFFFFFFFFFFFFFFFFFF

Denormals: e = 0; Specials: (NaN, Inf, -Inf) e = 255


EXAMPLE 1

What is the IEEE 32-bit floating point representation for the decimal number -11.5?


SOLUTION

1. Convert to binary. To the left of the binary point, represent the magnitude of the number to the left of the decimal point. To the right of the binary point, represent the fraction to the right of the decimal point (note: this may require a loss of accuracy). The first position after the binary point is the 2-1 position (0.5 decimal), then 2-2 (0.25), 2-3 (0.125), etc.

-11.510 = -1011.12
2. Convert to normalized binary scientific notation (i.e. move binary point to the left or right as far necessary until a single one is to left of the binary point, e.g. 1.f):
-1011.12 = -1.0111 x 23
Note: in the special case of 0.0, all 32 bits are 0. This is a denormal since there is no 1 to the left of the binary point.

3. Determine s, e and f:

s = 1 for negative, 0 for positive.

true exponent = 310 = e - 127, thus
e = 3 + 127 = 13010 = 100000102

1.f = 1.0111, thus f = 0111
4. Assemble the 32 bits, padding f to the right with zeroes:
s   e+127     1.fffffffffffffffffffffff
1   10000010    01110000000000000000000

11000001001110000000000000000000

 5. Convert to hex:
1100 0001 0011 1000 0000 0000 0000 0000

C1380000
Note special cases:

s = 0, e=255, f = all zeroes: +Infinity
s = 1, e=255, f = all zeroes: -Infinity
s = 0 or 1, e=255, f = anything but all zeroes: Not A Number

EXAMPLE 2

The previous example was a little simplistic because the fractional portion of the number was a sum of powers of 1/2. This means that the binary representation will be an exact representation of the decimal value. Often, though, this is not possible. Consider, for example, the decimal value 42.42 expressed in IEEE Float.

1. Convert to binary:

First convert the integer portion to an unsigned binary integer:

4210 = 1010102
Next convert the fractional portion. This involves a technique which is the inverse of that for the integer portion. Begin with the value to be represented:
0.42
then successively multiply by 2. The integer portion of each result is used to create the binary fraction, the fractional portion of each result is used in the next step. Repeat until the result is 0 or the number of bits allowed is exceeded. Example: 
	0.42 x 2 = 0.84
	0.84 x 2 = 1.68
	0.68 x 2 = 1.36
	0.36 x 2 = 0.72
	0.72 x 2 = 1.44
	0.44 x 2 = 0.88
	0.88 x 2 = 1.76
	0.76 x 2 = 1.52
	0.52 x 2 = 1.04
	0.04 x 2 = 0.08
	0.08 x 2 = 0.16
	0.16 x 2 = 0.32
	0.32 x 2 = 0.64
	0.64 x 2 = 1.28
	0.28 x 2 = 0.56
	0.56 x 2 = 1.12
	0.12 x 2 = 0.24
	0.24 x 2 = 0.48
	0.48 x 2 = 0.96
	0.96 x 2 = 1.92
	0.92 x 2 = 1.84 <--- repeats here
	0.84 x 2 = 1.68  
	0.68 x 2 = 1.36
Assembling the bits we have:
0.4210 = 0.01101011100001010001111
Note that the first few 1's are most significant:
0.25 + 0.125 + 0.03125 + 0.0078125 = 0.414065
Now we have:
42.4210 = 101010.011010111000010100011112
2. Convert to normalized binary scientific notation:
1.01010011010111000010100011112 x 25
3. Determine s, e and f: 
	s = 0
	e = 5
	e+127  = 5 + 127 = 132 = 100001002
	f = 010100110101110000101002  (note that some bits are dropped off
the right)
4. Assemble the 32 bits: 
	s     e+127       1.fffffffffffffffffffffff 
	0     10000100      01010011010111000010100

	01000010001010011010111000010100
5. Convert to hex: 
	0100 0010 0010 1001 1010 1110 0001 0100

	4229AE14

Homework