sheng/Binary Arithmetic

Binary Arithmetic

1. Objective

• To be able to do addition, subtraction, multiplication and division in binary
• Understand finite-precision arithmetic
• Know how to represent negative numbers in binary

2. Motivation

• Arithmetic is at the heart of the digital computer and the majority of arithmetic performed by computers is binary arithmetic. Understanding binary arithmetic is also important to building digital logic circuits to perform arithmetic.

3. Pre-questions

• When you use a computer, you may encounter an error message like:

What does this warning mean?

• In ordinary algebra, you may be familiar with the associative law or the distributive law:

a + ( b - c) = (a + b) - c
a x ( b - c) = a x b - a x c

When you perform binary arithmetic, do you think the two laws still hold?

4. Slides

4.1.1. Example

• Use the same "carry" principle used when adding two decimal numbers
• Add the two digits using the rules
• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 10 ... for this case move the 1 to the top of the next column ("carry the one") and keep the zero.
        1
1 0 1 1 1
+ 0 0 1 0 1
_________
0


Because 1+1 = 10 in binary.

4.2. Subtraction

• The order of operands
• the first operand (the number is being diminished)is called the minuend
• the second operand (the amount to be subtracted) is called the subtrahend
• the result is called the difference
• Decimal number subtraction
  65   minuend
- 39   subtrahend
__
26   difference

• Rules for subtraction
• 0 - 0 = 0
• 0 - 1 = 1 (and borrow 1 from the next more significant digit)
• 1 - 0 = 1
• 1 - 1 = 0
    0 1 1 1 1    <- borrows
0 1 0 0 0 0 0 1 =  65
- 0 0 1 0 0 1 1 1 =  39
_______________    __
0 0 0 1 1 0 1 0    26


because 1 0 0 0 0 0 = 0 1 1 1 1 1 + 1

• Subtracting a positive number is equivalent to adding a negative number of equal absolute value; computers typically use two's complement notation to represent negative values.

4.3. Multiplication

• A simplistic way to perform multiplication is by repeated addition.
• Multiplying decimal numbers
  42   multiplicand
X 27   multiplier
___
294   first partial product (42 x 7)
84    second partial product (42 x 2)
____
1134   total product

• Rules for binary multiplication
• 0 x 0 = 0
• 0 x 1 = 0
• 1 x 0 = 0
• 1 x 1 = 1
• Binary number multiplication

1 1 0 1   multiplicand
x 1 0 1 0   multiplier
________
0 0 0 0   first partial product  ( 1 1 0 1 x 0)
1 1 0 1   second partial product ( 1 1 0 1 x 1)
0 0 0 0     third partial product  ( 1 1 0 1 x 0)
1 1 0 1       fourth partial product ( 1 1 0 1 x 1)
_______________
1 0 0 0 0 0 1 0   total product

• An algorithm for binary multiplication for computer implementation
• If the rightmost digit of the multiplier is a one, copy the multiplicand to the product, otherwise set the product zero
• For each successive digit of the multiplier, shift the multiplicand left one bit; then if the multiplier digit is a one, add the shifted multiplicand to the product.
• Q: If two n-bit numbers are multiplied, how many bits are the largest possible products?

4.4. Division

• Binary division is again similar to its decimal counterpart
                          1 0 1 0           quotient
________________
divisor   0 1 0 1 ) 0 1 1 0 1 0 1           dividend
0 1 0 1
_______
1 1 0
0 1 0 1
______________
1 1           remainder



4.5. Represent signed numbers

• Sign-and-magnitude method
• Representing a number's sign by allocating one sign bit to represent the sign: set that bit (often the most significant bit) to 0 for a positive number, and set to 1 for a negative number. The remaining bits in the number indicate the magnitude (or absolute value).
• You can represent numbers from 12710 to + 12710 once you add the sign bit (the eight bit).
• One's complement method
• The ones' complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number (swapping 0's for 1's and vice-versa)
• The "complement" of its positive counterpart. Like sign-and-magnitude representation, ones' complement has two representations of 0: 00000000 (+0) and 11111111 (−0).
• A conventional eight-bit byte is 12710 to + 12710 with zero being either 00000000 (+0) or 11111111 (−0).
• Two's complement method
• the value obtained by subtracting the number from a large power of two (specifically, from 2N for an N-bit two's complement).
• An N-bit two's-complement numeral system can represent every integer in the range − 2N − 1 to + 2N − 1 − 1.
• Excess-N method
• Excess-N, also called biased representation, uses a pre-specified number N as a biasing value. A value is represented by the unsigned number which is N greater than the intended value. Thus 0 is represented by N, and −N is represented by the all-zeros bit pattern.

5. Questions

5.1. Binary Subtraction I

• Complete the following binary subtractions:
  1 1 0 0 1 1 0 1 1 0 1
- 1 0 0 0 0 1 1 0 1 1 1
_____________________


5.2. Binary Multiplication

   1 1 1 0 1 1 0 0
x 0 1 1 0 1 1 0 1
_________________


5.3. Binary Division

                ________________
0 0 1 0 0 1 1 1 )1 0 1 0 0 0 1 0