Nhân 2 số có dấu ( Booth)

import math
def dec2bin(n):
    k = []
    while n<>0:
        k.insert(0,int(math.fmod(n,2)))
        n = int(n/2)
    return k

def bin2dec(k):
    result = 0
    for i in range(len(k)):
        result = result + k.pop() * pow(2,i)
    return result

def add(a,b):
    k = []
    nho = 0
    for i in range(len(a)):
        tmp = a[len(a)-i-1] + b[len(b) - i - 1] + nho
        k.insert(0,int(math.fmod(tmp,2)))
        nho = tmp / 2
    return k

def edit(a,b):
    for i in range(len(a)):
        if a[i] == 0:
            a[i] = 1
        else:
            a[i] = 0
    b[len(a)-1] = 1
    return add(a,b)

def shr(a,q,q1):
    a.insert(0,a[0])
    q.insert(0,a.pop())
    q1 = q.pop()
    return a,q,q1

def main():
    m, q, a, am_m = [], [], [], []
    so1 = int(raw_input('Nhap so bi nhan = '))
    so2 = int(raw_input('Nhap so nhan = '))

    #Chuyen sang so nhi phan
    m = dec2bin(math.fabs(so1))
    q = dec2bin(math.fabs(so2))

    #Can bang so bit:
    if len(m) > len(q):
        for i in range(len(m) - len(q) +1 ):
            q.insert(0,0)
        m.insert(0,0)
    elif len(m) < len(q):
        for i in range(len(q) - len(m) +1 ):
            m.insert(0,0)
        q.insert(0,0)
    else:
        m.insert(0,0)
        q.insert(0,0)

    #A <- 0
    for i in range(len(m)):
        a.insert(0,0)
    n = len(m)
    dem = n
    #Hieu chinh thanh 2 so duong, tim -M
    if so1 >=0 :
        am_m = list(m)
        am_m = edit(am_m,list(a))
    else:
        am_m = list(m)
        m = edit(m,list(a))
    if so2 < 0:
        q = edit(q,list(a))
    q1 = 0
    #============================================#
    print "*"*55
    print "*"," "*51,"*"
    print "*"," "*20,"AT9B - KMA"," "*19,"*"
    print "*"," "*16,"Thuat toan Booth"," "*17,"*"
    print "*"," "*51,"*"
    print "*"*55
    print "\nM = %s\t-M = %s\nQ = %s\n" % (m,am_m,q)
    print "\n    A             Q      Q-1"
    print "%s %s %s    n = %d" % (a,q,q1,n)
    while True:
        if(q[dem-1]==1) and (q1 == 0):
            a = add(a,am_m)
            raw_input()
            print a,q,q1, "   A <- A - M"
        elif (q[dem-1]==0) and (q1==1):
            a = add(a,m)
            raw_input()
            print a,q,q1, "   A <- A + M"
        raw_input
        a,q,q1 = shr(a,q,q1)
        print a, q, q1, "   Dich phai, n=",n-1
        n = n - 1
        if n == 0:
            break

    #Hieu chinh ket qua
    k = []
    for i in range(len(a)):
        k.append(a[i])
    for i in range(len(q)):
        k.append(q[i])
    if so1*so2 >0:
        result = bin2dec(k)
        print "====> %d * %d = %d" % (so1,so2,result)
    else:
        tmp = []
        for i in range(2*len(a)):
            tmp.append(0)
        k = edit(k,tmp)
        result = bin2dec(k)
        print "====> %d * %d = -%d" % (so1,so2,result)
    raw_input()
main()