algorithms/binary/sum_of_integers.py at main · dichev/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
"""
# Sum of Two Integers
You are given two integers, a and b. Your task is to return their
sum without using the + or - operators.
"""


"""
Half Adder:
 A ----┐
       |---- XOR ---- Sum
       |
       |---- AND ---- Carry
 B ----┘
"""
def sum_integers_ripple_carry(num1, num2):  # loop through a Half Adder (no parallelization)
    total =  num1 ^ num2         # sum (ignoring the carry)
    carry = (num1 & num2) << 1   # the shifted carry

    while carry: # keep repeating until there is no carry left
        total, carry = total ^ carry, (total & carry) << 1

    return total


"""
Full Adder:

A ----┐
      |---XOR----┐
B ----┘          |---XOR------------> Sum
Cin--------------┘


A ----┐
      |---AND--------------┐
B ----┘                    |
A ----┐                    |---OR---> Carry (Cout)
      |---XOR----┐         |
B ----┘          |---AND---┘
Cin--------------┘


"""
def sum_integers_full_adder(num1, num2):
    assert num1 >= 0 and num2 >= 0 # ignoring negative integers

    total = 0b0
    carry = 0b0
    i = 0
    while num1 or num2 or carry:
        # select the last bits
        a, b = num1 & 1, num2 & 1

        # full adder
        bit = a ^ b ^ carry
        carry = (a & b) | (carry & (a ^ b))
        total |= (bit << i)

        # left shift to the next bit
        num1 = num1 >> 1
        num2 = num2 >> 1
        i+=1

    return total


if __name__ == '__main__':
    from utils import test
    test(sum_integers_ripple_carry(3, 5), 8)
    test(sum_integers_ripple_carry(6, 9), 15)
    test(sum_integers_ripple_carry(6, 10), 16)
    test(sum_integers_ripple_carry(111, 89), 200)

    test(sum_integers_full_adder(3, 5), 8)
    test(sum_integers_full_adder(6, 9), 15)
    test(sum_integers_full_adder(6, 10), 16)
    test(sum_integers_full_adder(111, 89), 200)

    from utils import plot_time_complexity
    plot_time_complexity(sum_integers_ripple_carry, lambda k: (1 << k, 1 << k), input_size_descr='(k)')
    plot_time_complexity(sum_integers_full_adder,   lambda k: (1 << k, 1 << k), input_size_descr='(k)')