sheng/Binary Arithmetic
From CDS 130
Binary Arithmetic
Contents 
1. Objective
 To be able to do addition, subtraction, multiplication and division in binary
 Understand finiteprecision 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. Prequestions
 When you use a computer, you may encounter an error message like:
What does this warning mean?
Answer 

When we perform binary arithmetic, the number of bits is fixed by computer's architecture. Common sizes for integer arithmetic are 8, 16, 32 and recently 64 bits. Working with unsigned (explained later) binary integers, the largest number is 2^{16} − 1 = 65,535. If the number is too large to fit in 16 digits, such a condition is called overflow. This is the limitation of finiteprecision computation. 
 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?
Answer 

The associative law and the distributive law don't hold in finiteprecision arithmetic.

4. Slides
4.1. Addition
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 nbit 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
 Signandmagnitude 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 127_{10} to + 127_{10} 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 viceversa)
 The "complement" of its positive counterpart. Like signandmagnitude representation, ones' complement has two representations of 0: 00000000 (+0) and 11111111 (−0).
 A conventional eightbit byte is 127_{10} to + 127_{10} 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 2^{N} for an Nbit two's complement).
 An Nbit two'scomplement numeral system can represent every integer in the range − 2^{N − 1} to + 2^{N − 1} − 1.
 ExcessN method
 ExcessN, also called biased representation, uses a prespecified 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 allzeros 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