Implementing Binary Arithmetic
Python, 429 chars - 10% bonus = 386.1

Numbers are kept in little endian order, which is stretching the rules a bit but makes for easier processing.  Maximum number size is 32 bits.  Addition is standard, subtraction is implemented by x-y = x+~y+1 (throwing away the carry out of the 32 bits), multiplication is done using the Russian Peasant algorithm, and division is done with repeated subtraction.

z,i='01'
P=z*32
def A(x,y):
 r='';c=z
 for a,b in zip(x+P,y+P):k=(a+b+c).count(i);r+='0101'[k];c='0011'[k]
 return r[:32]
S=lambda x,y:A(A(x,''.join(chr(ord(c)^1)for c in y+P)),i)
def M(x,y):
 r=''
 while y:
  if y[0]==i:r=A(r,x)
  x=z+x;y=y[1:]
 return r
def D(x,y):
 x=(x+P)[:32];y=(y+P)[:32];r=''
 while x[::-1]&gt;=y[::-1]:r=A(r,i);x=S(x,y)
 return r
def B(x,y,o):r=[A,S,M,D][o](x,y).rstrip(z)[:len(x)+len(y)];return[r,z][r=='']


B is the function of interest, here is its result on the test cases:

print B('01010','10101',0)
11111
print B('01111','01010',1)
00101
print B('0100','0001',2)
00001
print B('0101101','1000100',3)
101