Lab 4: binary numbers

Comp 150, Dordal, Feb 17, 2006

Goals:

Binary Numbers

Suppose you have a string of digits 101011, representing a binary number, and want to convert to decimal. The positions of the digits correspond to powers of 2: 
    1   0   1   0   1   1
   32  16   8   4   2   1
To find out the number this represents, you multiply each power of 2 by the corresponding digit and add them all up: 
	1*32 + 0*16 + 1*8 + 0*4 + 1*2 + 1*1 = 32 + 8 + 2 + 1 = 43
much like 497 = 4*102+9*10 + 7.

strtonum

Your first part is to write strtonum(s) that takes a string of binary digits s and returns its numeric value as above.

If s is the string above, the indexing is as follows: 

     i:   0   1   2   3   4   5
   s[i]:  1   0   1   0   1   1
Unfortunately strings are indexed starting from the left end, and numbers are represented with the 2i column at position i starting from the right end. So one quick fix is to reverse the string (first converting it to a list because you can't directly reverse strings): 
     t = list(s)
     t.reverse()			# unfortunately these two steps can't be combined
Reversing the list t is the same as still thinking of it in the original order but now indexed right-to-left. 
     i:   5   4   3   2   1   0
   t[i]:  1   0   1   0   1   1
Now we just take the sum of (ith_digit)*(2i) using a for or while loop: 
	sum = 0
	for i in range(0,len(t)):
	    sum = sum + (ith_digit)*(2**i)
There's one last catch: t[i] is a character and not a digit. But this works: 
	if t[i]=='0': digit = 0					# compact form of if/else
	elif t[i]=='1': digit=1
	else: print "bad digit at column", i

What about converting back?

If we want to convert N to a string of digits, we could go left-to-right: finding the highest power of 2 such that 2i≤N. But, as above, it's easier if we go right-to-left. The 1's-column digit is N % 2, and the rest of the digits to the left of the 1's-column represent the number N/2. So, 
    while N > 0:
        digit = N % 2
        N = N/2
        print digit
Replace printing the digit by putting the digit onto a list, and then reversing the list when you're done, and you have numtostr, the inverse of strtonum.

What are we really doing?

You might be wondering why, if computers represent numbers in binary and we're starting with binary, why any conversion is needed at all. This is a reasonable question to ask. However, computers don't store binary numbers as strings, and so at least some conversion is required. There are faster ways to convert a binary string to a number, but the way illustrated here works for other bases too and illustrates the ideas behind doing conversions manually.

Reloading

I think I've got it right now. Initially do both the following:
    import lab4
    from lab4 import *
Then, to reload:
    reload(lab4)
    from lab4 import *

That is, lab4 is initially imported with "import lab4", and reloaded with "reload(lab4)". The "from lab4 import *" is needed after each load or reload; its effect is to tell python that you want to refer to function foo in lab4.py as just foo(), and not lab4.foo().