Binadd.py

Binadd.py

# coding: utf-8
"""
Exercise solution: given two string representations of binary numbers, return their sum as a string representation of a binary number.

This solution assumes that a much simpler solution like... 

   def badd(a,b):
   	 return bin(int(a,2) + int(b,2))[2:]

...wouldn't be accepted. ;)
"""

debug = False
def dbg(m):
	if debug:
		print m

def badd(a,b):
	l = max(len(a),len(b))
	a = a.rjust(l,'0') ; a = map(int,a) ; a.reverse()
	b = b.rjust(l,'0') ; b = map(int,b) ; b.reverse()
	dbg('  %s\n+ %s' % (''.join(map(str,a)), ''.join(map(str,b))))
	r = []
	carry = 0
	for i in xrange(0,len(a)):
		x = a[i]
		y = b[i]
		carry_next = 0
		if x & y == 1:
			val = 0 | carry
			carry_next = 1
		elif x | y == 1:
			if carry:
				val = 0
				carry_next = 1
			else:
				val = 1 
		else:
			val = 0 | carry
		dbg(('    %s + %s carry %s = %s' % (x,y,carry,val)))
		r.append(val)
		carry = carry_next
	if carry == 1:
		dbg('    ...and one last carry')
		r.append(carry)
	r.reverse()
	r = ''.join(map(str,r))
	dbg('  %s\n  %s' % ('-'*l,r))
	return r
	
if __name__ == '__main__':
	# enable to show work
	debug = True
	
	# values for testing
	b1 = "1"
	b2 = "10"
	b5 = "101"
	b9 = "1001"
	b12 = "1100" 
	b15 = "1111"
	
	for a,b,ab in (
		(b1,b5,'110'),
		(b9,b12,'10101'),
		(b2,b15,'10001'),
		(b9,b15,'11000'),
	):
		s = badd(a,b)
		if s != ab:
			print '* FAILURE: %s + %s expected %s, but got %s' % (a,b,ab,s)
		else:
			print 'SUCCESS: %s + %s = %s' % (a,b,s)
		if debug:
			print ''