SIMPLISTIC EXPLANATION OF BINARY NOTATION

 

In the summer of 1962, I was privileged to be among the top 20 (out of 800 applicants) winners of a National Science Foundation grant to learn computer programming (and selected number theory topics from Peano’s Postulates to elementary calculus) at St. Louis University.   But even more notably, we got to meet the head of the mathematics department, who organized and taught the lecture series.   This was our introduction to computers.

 

Most everyone recognizes that for any given string of “n” decimal digits di such as

 

            Dn = { dn-1, dn-2, …, d2, d1, d0 }, where di e { 0,1,2, …, 8, 9 }

                            

then those digits to the left correspond to ever increasing powers of ten.   The value of the string can be represented by the “Vb()” function where “b” is the base;  and for b = 10,  we have

 

            V10(Dn) = dn-1 * 10n-1 + dn-2 * 10n-2 + … + d1 * 101 + d0 * 100

 

or more compactly

 

            V10 (Dn) =

 

Since computers make use of electronic elements having only two possible states, these are best described using the binary number system.  For a string of “n” binary bits such as

 

            Bn = { bn-1, bn-2, …, b2, b1, b0 },  where bi e { 0,1 }

 

and as before the value “V2()” function is

 

            V2 (Bn) = bn-1 * 2n-1 + bn-2 * 2n-2 + … + b1 * 21 + b0 * 20

or

            V2 (Bn) =

Another way of representing a string of binary digits is

 

            Bn = { bn-1, bn-2, …, b2, b1, b0 } = B[n-1:0]

 

where the double subscript represents a range of “n” bits and so for a single subscript B[k] = bk  for (n-1) <= k <= 0.  Note that B[n-1] is called the most significant bit (msb) and B[0] = b0   and is called the least significant bit (lsb).

 

Yet another notation is to simply append the base as a trailing subscript. For example, the following values are equivalent

 

    112              =   (1)*2 + (1)*1          =   310

   1102             =   (1)*4 + (1)*2          =   610

  11112               =   8 + 4 + 2 + 1         = 1510

10 00012        =   32 + 1                    = 3310

 

and so forth.   Alternatively, we could easily expand to any arbitrary base.  For an arbitrary vector

 

Wn = { wn-1, wn-2, …, w2, w1, w0 }, where each 0 <= wi  <= (b – 1), then the value function becomes

 

Vb(Wn) = wn-1 * bn-1 + wn-2 * bn-2 + … + w1 * b + w0 = 

 

INVERTING A BINARY STRING

 

The inverse of a single binary bit “ai”, is simply defined as

 

    āi =1 if ai=0

 

and

 

    āi =0 if ai=1

 

Another way of writing this is

 

    āi = 1 - ai

 

For a string of “n” bits starting from

 

     An = A[n-1:0] = { an-1, an-2, …, a2, a1, a0 },

 

then the notation for the inverse is simply

 

      Ān = Ā[n-1:0] = { ān-1, ān-2, …, ā2, ā1, ā0 }.

 

And the value, V2(Ā), of a string of “n” inverted bits is

 

      V2 (Ān) = = =

 

Also note that the magnitude of a binary string of all ones

 

     

 

and

 

     

 

 

      V2 (Ān) = (2n – 1) – V2(An)

 

or

 

V2(An) = (2n – 1) – V2(Ān)

 

What this means is that inverting a binary string, An, is exactly the same operation as subtracting the string from a series of “n” continuous ones, i.e. 2n – 1.  In this sense An, and its inverse Ān, are the one’s compliment of each other.  For example, if n = 3 we can construct the following table

 

 

 

where the last column on the right duplicates the previous binary operation but in decimal notation for clarity.

 

 

ONE’S COMPLIMENT

 

In “one’s compliment” notation binary bit strings are used to represent both positive and negative numbers.  This is accomplished by arbitrarily assigning exactly half of all the possible patterns to each range.   For increasingly positive numbers, the straightforward values of V2(An) increase starting from zero whereas for increasingly negative numbers, the V2(An) decrease in value.  Consider for example, the table of all possible 3 bit strings, A3, where we have also introduced a one’s compliment function, Ones(A3), which returns the one’s compliment decimal value.

 

 

 

 

This table can be formally expressed in simple equations as shown below:

 

a)    Zero is represented by two separate strings {0,0,0} and {1,1,1} corresponding to something like +0 and -0.  This is inefficient.

 

b)    All 1’s compliment strings with positive decimal values start with a zero,

 

Ones(An) = V(An)

                  or

Ones(An) = (2n – 1) - V(Ān)

 

                 when the msb an-1 = A[n-1] = 0.

 

 

c)    All 1’s compliment strings with negative decimal values start with one,

 

Ones(An) = V(An) - (2n – 1)

     or

Ones(An) = -V(Ān)

 

                 when the msb an-1= A[n-1] = 1.

 

The negative values run backwards in that the largest V2(An) gives the smallest decimal value in Ones(An).

 

d)    The full range of values is (1- 2n-1) <= Ones(An) <= (2n-1– 1)

 

 

In support of the above equations for the inverted bit string Ā3, the following table lists the operations for all 3-bit strings as shown below:

 

 

 

 

An interesting features of one’s compliment from the above table is that if a given binary string, An, has a positive value, then the inverted binary string, Ān seems to represent the corresponding negative value.  But more formally,

 

When ān-1 = 0, Ones(Ān) = V(Ān).  And since an-1 = 1, Ones(An) = - V(Ān).  Then

 

Ones(Ān) = -Ones(An).

 

Likewise, if ān-1 = 1, Ones(Ān) = -V(An).  And since an-1 = 0, Ones(An) =  V(An).  And so again, and for all values,

 

Ones(Ān) = -Ones(An).

 

Basically, inverting the bit string always multiplies the 1’s compliment value by minus one.

 

EXAMPLE

 

To summarize, to get the 1’s compliment value of the 6-bit string A6 = 1101012 ,  we calculate

 

            Ones(1101012) = V10(1101012) – (26-1) = (32+16+4+1) – (64-1) = 53 – 63 = -1010

 

To convert from a negative number to a positive number, we simply invert the bit string so that Ā6 = 0010102 and

 

            Ones(īī ōī ōī2) = Ones(0010102) = (1)*8 + (1)*2 = +1010

 

 

TWO’S COMPLIMENT

 

The purpose of two’s complement notation is also to reassign bit patterns to represent negative numbers but in a slightly more efficient manner than for one’s compliment.  In particular, the double assignment of zero is eliminated and the range for negative numbers is increased by one.

 

Towards this end, we can rewrite the previous bit string inversion equations as:

 

 V10(Ān) = 2n – [V10(An) + 1]  and

 

 V10(An) = 2n – [V10(Ān) + 1]

 

The point is that to get the other member of a 2’s compliment pair, we must always invert the bit string and then add one. Note we can use the asterisk superscript, “*”, to indicate this computing the 2’s compliment pair.  The inversion equations can then be more compactly displayed as follows:

 

 V10(Ān) = 2n – V10(An*)  for  V(An*) = V(Ān) + 1, and

 

 V10(An) = 2n – V10(Ān*)  for  V(Ān*) = V(An) + 1

 

 

 

Mechanically, the way to get the other member of a 2’s compliment pair is to start from the right and invert every bit to the LEFT of the FIRST bit whose value is one.

 

In 2’s compliment notation, a bit string representing a positive number is replaced by its 2’s compliment partner to give the corresponding negative number.  Consider the table of all possible 3-bit strings A3 and a 2’s compliment function, Twos(A3) which returns a decimal value:

 

 

Some interesting features of two’s compliment include

 

a)    Zero is only represented once in the table and the range of negative values has been expanded by one.

 

b)    Positive 2’s compliment strings always start with zero, i.e. the msb an-1=0 and

 

Twos(An) = V(An) = 2n – [ V(Ān) + 1 ]  >= 0

 

c)    Negative 2’s compliment strings always start with one, i.e. the msb an-1=1 and

 

Twos(An) = V(An) - 2n  = [ V(Ān) + 1 ]  < 0

 

The negative values run backwards in that the largest V(An) gives the smallest Ones(An).

 

d)    The full range of values is - 2n-1 <= Twos(An) <= (2n-1– 1).

 

e)    The smallest negative number is -2n-1 and there is NO positive analog.  Inverting this value and adding one, returns only the value from which we started. The difficulty is that the desired positive value is not expressible given the constraint of “n” bits.

 

f)     The value for zero presents another problem. Inverting zero and adding one returns the value 2n.  This requires “n+1” bits to express and only gives the desired string, i.e. of zero, if the final result is truncated to the original “n” bits.

 

As a consistency check, consider operations on the 2’s compliment of A3, i.e. A3* = (Ā3+1), for all 3-bit strings as shown in the next table:

 

 

Note that we somewhat arbitrarily choose values for the column, Twos( V(Ā3)+1 ), to correspond to the same bit pattern in the argument, i.e. [ V(Ā3)+1 ], as in the previous table.  But more formally,

 

When (an-1)* = 0, Twos(An*) = V(An*) = V(Ān) +1 = 2n - V(An).  And since an-1 = 1, Twos(An) = V(An) - 2n.

Then

 Twos(An*) = -Twos(An).

 

Likewise, if (an-1)* = 1, Twos(An*) = V(An*) - 2n = V(Ān) +1 - 2n  = -V(An).  And since an-1 = 0, Twos(An) =  V(An).

And so again, and for all values,

 

Twos(Ān*) = -Twos(An).

 

Basically, inverting the bit string and adding one, i.e. to get the 2’s compliment pair, multiplies the original 2’s compliment value by minus one.

 

 

ARITHMETIC IN 2’s COMPLIMENT

 

1.    Addition

 

The addition of two “n-bit” numbers potentially results in an “n+1” bit quantity and thus requires the sign extension of both numbers.   Sign extension is really only visible when the number is negative, i.e. the msb is one.   Formally, to add An and Bn we get

 

            C[n:0] = an-1 * 2n + V(An) + bn-1 * 2n + V(Bn)

 

C[n:0] = V( { an-1, an-1, an-2, …, a1, a0 } } + V( { bn-1, bn-1, bn-2, …, b1, b0 } }

 

where the final result, C[n:0], is truncated to the smaller “n+1” bits, i.e. the “n+1” lsb-s.

 

            Fast Look Ahead

Conditional MSB Pipes

 

2.    Subtraction

 

The subtraction of two n-bit numbers potentially results in an “n+1” bit quantity and thus requires sign extension.  Basically to subtract An from Bn, the exercise is to change the sign of An and then add.  Formerly to compute Bn minus An , we get,

 

            C[n:0] = bn-1 (2n) + V(Bn) - an-1 (2n) - V(An)

 

            C[n:0] = bn-1 (2n) + V(Bn) + ān-1(2n) + V(An*),  where the asterisk “*” indicates a 2’s compliment pair

 

C[n:0] = bn-1 (2n) + V(Bn) + ān-1(2n) + V(Ān) + 1

 

C[n:0] = V2( { bn-1, bn-1, bn-2, …, b1, b0 } ) + V2( { ān-1, ān-1, ān-2, …, ā2, ā1, ā0 } ) + 1

 

 

3.    Multiplication

 

The multiplication of two n-bit numbers potentially results in an “n+n = 2*n” bit quantity.  Since multiplication is repeated addition, it is required that one of the numbers be positive.  To multiply two negative numbers, one must be “effectively” changed to a positive number and thefinal result corrected at the end.

 

            To multiply by a power of two, simply shift the 2’s compliment number to the left.

 

            Booth Algorithm

            Higher Radix Structures

            Wallace Trees

 

4.    Division

 

To divide by a power of two, simply shift the 2’s compliment number to the right while sign extending in the msb-s.   The main problem is how to round especially for negative numbers.   Please note the basic operation of division truncates to a smaller number, rather than rounding towards zero. This consistency is always to be preferred unless there is some unique frame of reference for the origin which is not generally the case in practice.  If this reasonable advice is not heeded, then it is only necessary to add a (+1) to negative results to round towards zero.

 

EXAMPLE

 

Considering all possible 4 bit 2’s compliment numbers, division by four and two is easily accomplished by shifting to the right by two and by one respectively.  Of course, negative numbers need to be sign-extended.  The fraction that is discarded without rounding is indicated in parentheses.

 

 

Restoring and Non-Restoring Methods

High Radix Structures

 

5.    Hardware Exponentiation

 

Successive Approximation

 

 

RECOMMENDED READING