Implementierung der Schiebe-Addiere-Methode

schiebe.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def niceRepresentation(binaryNumber):
	nice = ''
	for i, bit in enumerate(binaryNumber):
		nice = nice + bit
		if i % 4 == 3:
			nice += ' '
	return nice.strip()

def nicePrint(a, b, between, prefix=''):
	aStr = niceRepresentation(a)
	bStr = niceRepresentation(b)
	print(prefix + '\t' + 'A:' + aStr + ' ' + between + ' Q:' + bStr)

def add(M, Q):
	result = ''
	carry = 0
	for i in list(range(len(Q)))[:0:-1]:
		sum = carry + int(M[i]) + int(Q[i])
		if sum == 0:
			result = '0' + result
			carry = 0
		elif sum == 1:
			result = '1' + result
			carry = 0
		elif sum == 2:
			result = '0' + result
			carry = 1
		elif sum == 3:
			result = '1' + result
			carry = 1
		else:
			print("Error occured!")
			print("Sum: %i" % sum)
			print("M[i]: %s" % M[i])
			print("Q[i]: %s" % Q[i])
			print("carry: %i" % carry)
	result = str(carry) + result
	return result

def schiebe(Q, A):
	return str('0'+Q[0:-1]), str(Q[-1] + A[:-1])

def xor(x, y):
	if x == y:
		return '0'
	else:
		return '1'

""" @param a: binary number as string (first bit is sign, rest is absolute value)
	@param b: binary number as string (first bit is sign, rest is absolute value) 
	@result: a*b (first bit is sign, rest is absolute value) """
def schiebeAddiere(a, b, verbose):
	M = a
	A = '0' * len(a)
	Q = b

	if verbose:
		print("\tM:" + niceRepresentation(M))
		nicePrint(A, Q, 'x')

	for i in range(len(M)-1):
		if Q[-1] == '1':
			A = add(M, A)
			if verbose:
				nicePrint(A, Q, ' ', 'Addiere')

		A, Q = schiebe(A, Q)
		if verbose:
			nicePrint(A, Q, ' ', 'Schiebe')
	# Korrektur
	A = xor(M[0], Q[-1]) + A[1:]
	Q = Q[0:-1] + '0'

	return A+Q

if __name__ == "__main__":
    aufgaben = {'1998' : ['10001001', '01010000', '1000 0101 1010 0000'],
			    '2004' : ['11001001', '11001001', '0000 1011 1111 1010'],
			    '2009' : ['10010101', '11001001', '0000 1011 1111 1010'],
			    '2007' : ['10011011', '10000101', '0000 0001 0000 1110'],
			    '2010' : ['10000101', '10011011', '0000 0001 0000 1110'],
      'Skript, S. 181' : ['01010101', '10110011', '1010 0001 1101 1110'],
                'Tiny0' : ['00', '00', '0000'],
                'Tiny1' : ['00', '01', '0000'],
                'Tiny2' : ['00', '10', '1000'],
                'Tiny3' : ['00', '11', '1000'],
                'Tiny4' : ['01', '00', '0000'],
                'Tiny5' : ['01', '01', '0001'],
                'Tiny6' : ['01', '10', '1000'],
                'Tiny7' : ['01', '11', '1001'],
                'Tiny8' : ['10', '00', '1000'],
                'Tiny9' : ['10', '01', '1000'],
                'Tiny10': ['10', '10', '0000'],
                'Tiny11': ['10', '11', '0001'],
                'Tiny12': ['11', '00', '1000'],
                'Tiny13': ['11', '01', '1001'],
                'Tiny14': ['11', '10', '0000'],
                'Tiny15': ['11', '11', '0001'],
                   '1x3': ['001', '011', '00 0011']}

    nrOfFailedTests = 0
    for key, value in aufgaben.items():
	    a, b, expected = value
	    result = schiebeAddiere(a,b,False)
	    if niceRepresentation(result).strip() != expected.strip():
		    nrOfFailedTests += 1
		    print(key)
		    result = schiebeAddiere(a,b,True)
		    print("Result: \t%s" % (niceRepresentation(result)))
		    print("Expected:\t%s" % expected)
		    print('#'*40)
    print("Failed Tests: %i" % nrOfFailedTests)