gistfile1.txt

'''
Function Name: positiveBinaryConversion
Number of Parameters: 1
Type of Parameters: list
Return Value: list
Function Description: Increments a binary number by 1
''' 
def incrementBinaryByOne(num):
    num.reverse()
    if num[0] == '0':
        num[0] = '1'
    else:
        num[0] = '0'
        x = 1
        for x in range(1, len(num)):
            if num[x] == '0':
                num[x] = '1'
                break
            else:
                num[x] = '0'
    num.reverse()
    return num

'''
Function Name: positiveBinaryConversion
Number of Parameters: 1
Type of Parameters: int
Return Value: String
Function Description: Converts a positive
number to its binary form
''' 
def positiveBinaryConversion(num):
    '''
    Create a list called stack to simulate one
    and add num to that stack
    Note: a real stack can also be used
    '''
    stack = [num]
    '''
    Create an empty list called binary
    '''
    binary = []
    '''
    Run while number is greater than 1
    '''
    while num > 1:
        '''
        Int values of num are added to the
        stack list after dividing by two
        Example: 5
        List: [5,2,1]
        '''
        num = num/2
        stack.append(num)
    print stack
    '''
    Reverse the stack so that it behaves like an
    actual stack
    '''
    stack.reverse()
    '''
    loop through the stack list
    '''
    for binNum in stack:
        '''
        Append the remainder after dividing by
        two to the list called binary
        '''
        binary.append(str(binNum%2))
    '''
    We want the number of bits to be 8 and
    if they are not we need to make them 8
    we do this cause the we are dealing with
    8 bit binary numbers in the binary representation
    in the booth's algorithm
    '''
    while not len(binary) == 8:
        binary.insert(0,"0")
    return "".join(binary)

'''
Function Name: twoscompliment
Number of Parameters: 1
Type of Parameters: int
Return Value: String
Function Description: Converts a negative number
into its two's compliment form
''' 
def twoscompliment(num):
    '''
    Declare an empty list called binary
    '''
    binary = []
    '''
    Mult the num with -1 to make it positive and pass it into
    the positiveBinaryConversion to get its equivalent positive
    binary form and then loop through and change the 1s to 0s
    and 0s to 1s so as to get its compliment
    '''
    for element in positiveBinaryConversion(num * -1):
        if element == '1':
            binary.append('0')
        elif element == '0':
            binary.append('1')
    '''
    Call the incrementBinaryByOne function and
    pass it the binary list into it
    '''
    binary = incrementBinaryByOne(binary)
    return "".join(binary)

'''
Function Name: twoscompliment
Number of Parameters: 1
Type of Parameters: string
Return Value: String
Function Description: Converts a number
into its two's compliment form for
subtraction purposes
''' 
def twoscomplimentForSub(num):
    '''
    Declare an empty list called binary
    '''
    binary = []
    '''
    Split the string into a list
    '''
    num.split()
    '''
    Loop through the num list and replace
    1 with 0 and 0 with 1
    '''
    for element in num:
        if element == '1':
            binary.append('0')
        elif element == '0':
            binary.append('1')
    '''
    Call the incrementBinaryByOne function and pass
    in the binary list to increment the number by one
    '''
    binary = incrementBinaryByOne(binary)
    return "".join(binary)

'''
Function Name: convertToBinary
Number of Parameters: 1
Type of Parameters: int
Return Value: String
Function Description: A pseudo function which
is used to distinguish between negative and
positive numbers so that we can apply proper
methods on them
'''    
def convertToBinary(num):
    '''
    If num is greater than or equal to zero call
    positiveBinaryConversion and pass in num or
    else call twoscompliment and pass in num
    This is done so that we know which numbers are
    negative and need to be complimented and which
    are positive and don't need to be
    The return value states that we are returning
    the value returned by positiveBinaryConversion
    and twoscompliment to the position from where
    convertToBinary was called
    '''
    if num >= 0:
        return positiveBinaryConversion(num)
    else:
        return twoscompliment(num)
'''
Function Name: convertToBinary
Number of Parameters: 2
Type of Parameters: string, string
Return Value: String
Function Description: A function to add
two binary numbers
'''  
def addBinary(num1,num2):
    '''
    Split the 2 strings into lists
    '''
    num1.split()
    num2.split()
    '''
    Create a new added list to store the added bits
    '''
    added = []
    '''
    carry variable to check if carry occurs
    '''
    carry = 0
    '''
    Loop which goes in reverse from the last element
    to the first
    '''
    for x in xrange(len(num1)-1, -1, -1):
        if num1[x] == '0' and num2[x] == '0':
            if carry == 1:
                added.append('1')
                carry = 0
            else:
                added.append('0')                
        elif (num1[x] == '0' and num2[x] == '1') or (num1[x] == '1' and num2[x] == '0'):
            if carry == 1:
                added.append('0')
            else:
                added.append('1')
        elif num1[x] == '1' and num2[x] == '1':
            if carry == 1:
                added.append('1')
            else:
                added.append('0')
                carry = 1
    added.reverse()
    return "".join(added)

'''
Function Name: rightShift
Number of Parameters: 2
Type of Parameters: string, string
Return Value: String, String
Function Description: A function to shift
the bits by one to the right
''' 
def rightShift(a,q):
    '''
    Concatanate the two strings and store in variable
    called num
    '''
    num = a + q
    num.split()
    '''
    Copy the first bit to the list and then start copying
    from the SAME bit till the end of the list
    '''
    shifted = [num[0]]
    for x in range(0, len(num) - 1):
        shifted.append(num[x])
    '''
    Return the two strings!
    '''
    return "".join(shifted)[:8],"".join(shifted)[8:]

'''
Function Name: multByBooth
Number of Parameters: 2
Type of Parameters: string, string
Return Value: None
Function Description: A function which
performs the actual booth's algorithm
''' 
def multByBooth(m, q):
    a = "00000000"
    qNeg1 = "0"
    qNeg0 = q[len(q)-1]
    print a,
    print q,
    print qNeg1
    for loop in range (0, len(m)):
        '''
        If 00 or 11
            just right shift
        '''
        if qNeg1 == "0" and qNeg0 == "0" or qNeg1 == "1" and qNeg0 == "1":
            qNeg1 = qNeg0            
            a, q = rightShift(a,q)
            qNeg0 = q[len(q)-1]
        '''
        If 10
            sub and right shift
        '''
        elif qNeg0 == "1" and qNeg1 == "0":
            a = addBinary(a, twoscomplimentForSub(m))
            qNeg1 = qNeg0
            a, q = rightShift(a,q)
            qNeg0 = q[len(q)-1]
        '''
        If 01
            add and right shift
        '''
        elif qNeg0 == "0" and qNeg1 == "1":
            a = addBinary(a, m)
            qNeg1 = qNeg0
            a, q = rightShift(a,q)
            qNeg0 = q[len(q)-1]            
        print a,
        print q,
        print qNeg1

def main():
    '''
    Get the first number from the user!
    Get the second number from the user!
    Call the convertToBinary function and pass in the first value
    '''
    binaryNum1 = convertToBinary(int(raw_input("Enter the first number")))
    binaryNum2 = convertToBinary(int(raw_input("Enter the second number")))
    '''
    Print info about the converted binary numbers
    '''    
    print "Binary form is " + binaryNum1
    print "Binary form is " + binaryNum2
    '''
    Call the multByBooth function and pass
    pass in the two numbers which you need
    to add into them
    '''    
    multByBooth(binaryNum1, binaryNum2) 
    
if __name__ == "__main__":
    main()