#!/usr/bin/env python # -*- coding: utf-8 -*- # import sys def bitstoint(b): """ Input: A bit sequence representing an arbitrary-length natural number Output: A Python integer """ result = 0 for bit in reversed(b): result = 2*result + bit return result def bitstostr(b): return ''.join(str(x) for x in reversed(b)) def inttobits(x): """ Input: A Python integer Output: A bit sequence representing the same natural number """ if x < 0: raise ValueError("x < 0: negative integers not supported") b = [] while x: b += [x % 2] x /= 2 return b def add(u, v): """ Input: Two natural numbers represented by bit sequences Output: Their sum, represented as a bit sequence """ b = [] j = 0 carry = 0 while j < len(u) or j < len(v) or carry: if j < len(u): carry += u[j] if j < len(v): carry += v[j] b += [carry % 2] carry /= 2 j += 1 return b def mul_simple(u, v): """ Input: Two integers represented by a bit sequence Output: Their product, obtained by simple multiplication """ result = [] for j in range(len(v)): if v[j]: if len(result) < j: result += [0] * (j - len(result)) result = result[0:j] + add(result[j:], u) return result def mul(u, v): return mul_simple(u, v) if __name__ == "__main__": while True: sys.stdout.write("a = ") a = int(sys.stdin.readline()) sys.stdout.write("b = ") b = int(sys.stdin.readline()) A = inttobits(a) B = inttobits(b) print "a =", a, "(" + bitstostr(A) + ")" print "b =", b, "(" + bitstostr(B) + ")" C = add(A, B) D = mul(A, B) print "a+b =", bitstoint(C), "(" + bitstostr(C) + ")" print "a*b =", bitstoint(D), "(" + bitstostr(D) + ")" if bitstoint(D) != a * b: print "Error in multiplication routine detected!" print