Addition With Bit Operations

This adds integers using bit-wise operations. I tried to provide a lot of print statements so that you could see what’s going on with each step.

def decbin(x):
    # printing helper
    return x, bin(x)

def add(a, b):
    running_sum = 0
    carry = 0
    k = 1
    temp_a = a
    temp_b = b
    while temp_a or temp_b:
        print("                temp_a {:2d} {}".format(*decbin(temp_a)))
        print("                temp_b {:2d} {}".format(*decbin(temp_b)))
        print("                     k {:2d} {}".format(*decbin(k)))
        # k masks a and b, returning the digits from right to left
        ak = a & k
        bk = b & k
        print("                    ak {:2d} {}".format(*decbin(ak)))
        print("                    bk {:2d} {}".format(*decbin(bk)))
        print("               ak & bk {:2d} {}".format(*decbin(ak & bk)))
        print("               ak ^ bk {:2d} {}".format(*decbin(ak ^ bk)))
        running_sum |= ak ^ bk ^ carry
        carry = (ak & bk) | (ak & carry) | (bk & carry)
        print("                 carry {:2d} {:12}  (ak & bk) | (ak & carry) | (bk & carry)".format(*decbin(carry)))
        print("       ak ^ bk ^ carry {:2d} {}".format(*decbin(ak ^ bk ^ carry)))
        print("           running_sum {:2d} {:12}  |= ak ^ bk ^ carry".format(*decbin(running_sum)))
        # carry_in and k are shifted up each iteration
        carry <<= 1
        k <<= 1
        # temp_a and temp_b are shifted down each iteration
        temp_a >>= 1
        temp_b >>= 1
        print()
    print("                 carry {:2d} {:12}".format(*decbin(carry)))
    print("   running_sum | carry {:2d} {}".format(*decbin(running_sum | carry)))
    return running_sum | carry

For example,

add(2,3)
                temp_a  2 0b10
                temp_b  3 0b11
                     k  1 0b1
                    ak  0 0b0
                    bk  1 0b1
               ak & bk  0 0b0
               ak ^ bk  1 0b1
                 carry  0 0b0           (ak & bk) | (ak & carry) | (bk & carry)
       ak ^ bk ^ carry  1 0b1
           running_sum  1 0b1           |= ak ^ bk ^ carry

                temp_a  1 0b1
                temp_b  1 0b1
                     k  2 0b10
                    ak  2 0b10
                    bk  2 0b10
               ak & bk  2 0b10
               ak ^ bk  0 0b0
                 carry  2 0b10          (ak & bk) | (ak & carry) | (bk & carry)
       ak ^ bk ^ carry  2 0b10
           running_sum  1 0b1           |= ak ^ bk ^ carry

                 carry  4 0b100       
   running_sum | carry  5 0b101

Leave a Reply

Your email address will not be published. Required fields are marked *