Nhân - Chia số nguyên

import math
import os

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 addbit(m,q):
    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)
    return m,q

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 shl(a,q):
    q.insert(len(q),0)
    a.insert(len(a),q.pop(0))
    a.pop(0)
    return a,q

def mul():
    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))

    m,q = addbit(m,q)

    #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
    os.system('cls')
    #============================================#
    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()
    raw_input()
    main()

def div():
    m, q, a, am_m = [], [], [], []
    so1 = math.fabs(int(raw_input('Nhap so bi chia = ')))
    so2 = math.fabs(int(raw_input('Nhap so chia = ')))
    if(so1<so2):
        print "***[ERROR] Try again!***"
        div()
    #Chuyen sang so nhi phan
    q = dec2bin(so1)
    m = dec2bin(so2)

    #A <- 0
    for i in range(len(m)):
        a.insert(0,0)
    n = len(m)
    dem = n
    am_m = edit(list(m),list(a))
    os.system('cls')
    #============================================#
    print "*"*55
    print "*"," "*51,"*"
    print "*"," "*20,"AT9B - KMA"," "*19,"*"
    print "*"," "*13,"Chia so nguyen khong dau"," "*12,"*"
    print "*"," "*51,"*"
    print "*"*55
    print "\nM = %s\t-M = %s\nQ = %s\n" % (m,am_m,q)
    print "\n    A             Q"
    print "%s %s    n = %d" % (a,q,n)

    while True:
        raw_input()
        a, q = shl(a,q)
        print a, q, "Dich trai"
        raw_input()
        a = add(a,am_m)
        print a, q, "A = A - M"
        if a[0] == 1:
            q[dem-1] == 0
            a = add(a,m)
            raw_input()
            print a, q, "q[0] = 0, A = A + M, n = ", n-1
        elif a[0] == 0:
            q[dem-1] = 1
            raw_input()
            print a, q, "q[0] = 1, n = ", n-1
        n = n-1
        if n == 0:
            break
    #Hien ket qua
    thuong = bin2dec(q)
    du = bin2dec(a)
    print "===> %d = %d * %d + %d" % (so1,thuong,so2,du)
    raw_input()
    raw_input()
    main()

def main():
    os.system('cls')
    os.system('color a')
    print "*"*55
    print "*"," "*51,"*"
    print "*"," "*20,"AT9B - KMA"," "*19,"*"
    print "*"," "*13,"Chia so nguyen khong dau"," "*12,"*"
    print "*"," "*51,"*"
    print "*"*55
    print "\n  1. Nhan so nguyen co dau ( Booth)."
    print "  2. Chia so nguyen khong dau."
    print "  3. Thoat.\n"
    key = int(raw_input('  Ban chon: '))
    if key ==1:
        mul()
    elif key == 2:
        div()
    elif key == 3:
        return
    else:
        main()
main()