~ Data Representation: Binary Arithmetic


Binary Arithmetic - Addition, Subtraction

PowerPoint loading ....

History

Binary is literally the very foundation of modern computers and you'll be interested to know that it was being used and applied way way back in time. In fact there are records of the ancient egyptians using binary in their calculations.

The modern binary number system was first fully documented by Gottfried Leibniz in the 17th century in his article Explication de l'Arithmétique Binaire. Leibniz's uses 0 and 1, like the modern binary numeral system.

In 1854British mathematician George Boole published a landmark paper detailing a system of logic that would become known as Boolean algebra. His logical system proved instrumental in the development of the binary system, particularly in its implementation in electronic circuitry.

In 1937Claude Shannon produced his master's thesis at MIT that implemented Boolean algebra and binary arithmetic using electronic relays and switches for the first time in history. Entitled A Symbolic Analysis of Relay and Switching Circuits, Shannon's thesis essentially founded practical digital circuit design.

In November of 1937George Stibitz, then working at Bell Labs, completed a relay-based computer he dubbed the "Model K" (for "kitchen", where he had assembled it), which calculated using binary addition. Bell Labs thus authorized a full research program in late 1938 with Stibitz at the helm. Their Complex Number Computer, completed January 81940, was able to calculate complex numbers. In a demonstration to the American Mathematical Society conference at Dartmouth College on September 111940, Stibitz was able to send the Complex Number Calculator remote commands over telephone lines by a teletype. It was the first computing machine ever used remotely over a phone line. Some participants of the conference who witnessed the demonstration were John Von NeumannJohn Mauchly, and Norbert Wiener, who wrote about it in his memoirs.

Representation

A binary number can be represented by any sequence of bits (binary digits), which in turn may be represented by any mechanism capable of being in two mutually exclusive states. The following sequences of symbols could all be interpreted as different binary numeric values:

1 0 1 0 0 1 1
- | | - -
x x x o x o o
n y y n
A binary clock might use LEDs to express binary values. In this clock, each column of LEDs shows a binary-coded decimal numeral of the traditional sexagesimal time.
 
binary clock might use LEDs to express binary values. In this clock, each column of LEDs shows a binary-coded decimal numeral of the traditional sexagesimal time.
 
Source: Wikipedia

Video: Did the ancient egyptians use binary?

Video:Adding in Binary

Arithmetic in binary is much like arithmetic in other numeral systems. Addition, subtraction, multiplication, and division can be performed on binary numerals.

Addition

The circuit diagram for a binary half adder, which adds two bits together, producing sum and carry bits.
 
The circuit diagram for a binary half adder, which adds two bits together, producing sum and carry bits.

The simplest arithmetic operation in binary is addition. Adding two single-digit binary numbers is relatively simple:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 (the 1 is carried)

Adding two "1" values produces the value "10", equivalent to the decimal value 2. This is similar to what happens in decimal when certain single-digit numbers are added together; if the result exceeds the value of the radix (10), the digit to the left is incremented:

5 + 5 = 10
7 + 9 = 16

This is known as carrying in most numeral systems. When the result of an addition exceeds the value of the radix, the procedure is to "carry the one" to the left, adding it to the next positional value. Carrying works the same way in binary:

  1 1 1 1 1     (carry)
    0 1 1 0 1
+   1 0 1 1 1
-------------
= 1 0 0 1 0 0

In this example, two numerals are being added together: 01101 (13 decimal) and 10111 (23 decimal). The top row shows the carry bits used. Starting in the rightmost column, 1 + 1 = 10. The 1 is carried to the left, and the 0 is written at the bottom of the rightmost column. The second column from the right is added: 1 + 0 + 1 = 10 again; the 1 is carried, and 0 is written at the bottom. The third column: 1 + 1 + 1 = 11. This time, a 1 is carried, and a 1 is written in the bottom row. Proceeding like this gives the final answer 100100.

Adding Binary Fractions

Adding binary fractions

Binary fractions can be added just like ordinary binary numbers. For example, using an eight bit system 0110.1010 (6.625) and 0011.1000 (3.5) added together equals 1010.0010 (6.125).

Decimal value    8  4  2  1  .  0.5  0.25  0.125  0.0625  
carry  0  1  1  1  1            decimal value
    0  1  1  0  .  1  0  1  0  6.625
    0  0  1  1  .  1  0  0  0  3.5
result   1
 0  1  0  .  0  0  1  0  6.125

Subtracting in Binary

Subtraction works in much the same way as addition:

0 - 0 = 0
0 - 1 = 1 (with borrow)
1 - 0 = 1
1 - 1 = 0

One binary numeral can be subtracted from another as follows:

    *   * * *   (starred columns are borrowed from)
  1 1 0 1 1 1 0
-     1 0 1 1 1
----------------
= 1 0 1 0 1 1 1

Subtracting a positive number is equivalent to adding a negative number of equal absolute value; computers typically use the two's complement notation to represent negative values. This notation eliminates the need for a separate "subtract" operation. For further details, see two's complement.

Recap video on Adding and Subtracting

Source: Wikipedia

Multiplying and Dividing in Binary

Multiplication in binary is similar to its decimal counterpart. Two numbers A and B can be multiplied by partial products: for each digit in B, the product of that digit in A is calculated and written on a new line, shifted leftward so that its rightmost digit lines up with the digit in B that was used. The sum of all these partial products gives the final result.

Since there are only two digits in binary, there are only two possible outcomes of each partial multiplication:

  • If the digit in B is 0, the partial product is also 0
  • If the digit in B is 1, the partial product is equal to A

For example, the binary numbers 1011 and 1010 are multiplied as follows:

           1 0 1 1   (A)
         × 1 0 1 0   (B)
         ---------
           0 0 0 0   ← Corresponds to a zero in B
         1 0 1 1     ← Corresponds to a one in B
       0 0 0 0
   + 1 0 1 1
   ---------------
   = 1 1 0 1 1 1 0

See also Booth's multiplication algorithm.

Division

Binary division is again similar to its decimal counterpart:

        __________
1 0 1  | 1 1 0 1 1

Here, the divisor is 101, or 5 decimal, while the dividend is 11011, or 27 decimal. The procedure is the same as that of decimal long division; here, the divisor 101 goes into the first three digits 110 of the dividend one time, so a "1" is written on the top line. This result is multiplied by the divisor, and subtracted from the first three digits of the dividend; the next digit (a "1") is included to obtain a new three-digit sequence:

             1
        __________
1 0 1  | 1 1 0 1 1
       - 1 0 1
         -----
           0 1 1

The procedure is then repeated with the new sequence, continuing until the digits in the dividend have been exhausted:

             1 0 1
        __________
1 0 1  | 1 1 0 1 1
       - 1 0 1
         -----
           0 1 1
         - 0 0 0
           -----
             1 1 1
           - 1 0 1
             -----
               1 0

Thus, the quotient of 11011 divided by 101 is 1012, as shown on the top line, while the remainder, shown on the bottom line, is 102. In decimal, 27 divided by 5 is 5, with a remainder of 2.

Source: Wikipedia


Topic 6