Lecture 4:BinaryCS105: Great Insights in Computer ScienceMichael L. Littman, Fall 20065 0 0901• How do we count?• Start at the bottom digit.• If it’s less than 9, add one to it.• If it’s equal to nine, make it zero and proceed to the digit to the left.8Counting (Decimal)2 4 9 910 0• Counting in binary is the same idea.• Start at the bottom (rightmost) bit.• If it’s less than 1, add one to it.• If it’s equal to 1, make it zero and proceed to the bit to the left.01011 10110 0Counting (Binary)0Place Values• Because of the way counting works, we expand the representation by another bit for each power of 2.• So, 11001001 is:• 128+64+8+1=201765432102726252423222120128643216842111001001Number Magic• How does this trick work?• http://www.brainbashers.com/games/number.aspWhich Have Your Number?• Think of a number from 0 to 31.• Add the upper left number from each card your number appears on.• It is...8910111213141524252627282930311617181920212223242526272829303123671011141518192223262730314567121314152021222328293031135791113151719212325272931Conversion• To go from decimal to binary, start with the biggest power of 2 no bigger than your number.• Write down a 1. Subtract the power of 2 from your number.• Cut the power of 2 in half.• If your remaining number is larger than the power of 2, write down a 1 and subtract the power of 2.• If not, write down 0.• Repeat by cutting the power of 2 in half (until you get to 1).It’s a bit like making change.Example: Convert 651• Bigger than: 29 = 512.• 651-512=139.• Next power of 2 = 256.• Next power of 2 = 128.• 139-128=11.• Next power of 2 = 64.• Next power of 2 = 32.• Next power of 2 = 16.• Next power of 2 = 8.• 11-8=3• Next power of 2 = 4.• Next power of 2 = 2.• 3-2=1• Last power of 2 = 1.10100010111010001011=651100100101Binary Addition01110011+ 10110010111001__• Just like in school: work right to left, carry when needed.• 0+0+0=0, 0+0+1 = 1, 0+1+1=10, 1+1+1=11• Can check via conversion.115+178293Other Operations• Can also define subtraction (with borrowing), multiplication (simpler since there are only 3 facts: 0x0=0 0x1=0 1x1=1, look familiar?), and long division.• Can do bitwise logic operations (and, or, not).• All are quite useful...Other Number Schemes• Can represent negative numbers, often via twos complements. -1 = 256-1 = 255.• Fixed-width fractions (for dollar amounts).• Floating point representations via exponential notation: a x 10b.• Complex numbers: real and imaginary parts.They are just bits: you can use them as you see fit.Implementing Addition• Half adder: Takes two bits and a carry and outputs a bit and a carry (addc).• Adder: Adds two 8-bit numbers (discards last carry) (addbyte).def addc(a,b,c): bit = (a and not b and not c) or (not a and b and not c) or (not a and not b and c) or (a and b and c) carry = (a and b and not c) or (a and not b and c) or (not a and b and c) or (a and b and c) return([carry, bit])def addbyte(x,y): z = [0]*8 sum7 = addc(x[7],y[7],0) z[7] = sum7[1] sum6 = addc(x[6],y[6],sum7[0]) z[6] = sum6[1] sum5 = addc(x[5],y[5],sum6[0]) z[5] = sum5[1] sum4 = addc(x[4],y[4],sum5[0]) z[4] = sum4[1] sum3 = addc(x[3],y[3],sum4[0]) z[3] = sum3[1] sum2 = addc(x[2],y[2],sum3[0]) z[2] = sum2[1] sum1 = addc(x[1],y[1],sum2[0]) z[1] = sum1[1] sum0 = addc(x[0],y[0],sum1[0]) z[0] = sum0[1] return zNext Time• We now have all the pieces to build a simple, working computer...• Each cycle, inputs propagate to outputs, which are copied back to inputs to begin again.• We need a language to talk to it in, though.• Read Hillis Chapter 2 Section 3, Chapter 3 Sections