CODEWITHSUNDEEP
pythonbinaryboolean
Jakemmarsh
Jakemmarsh

Reputation: 4671

Binary addition of two lists of boolean values

I was given the following prompt:

create a function: BoolAdd(A,B) that performs binary addition on lists A and B (A and B have the same length N) of Boolean values and returns a list of two elements. The first element is an overflow, which means that it is returned with the value FALSE unless the addition does not fit into the same length list as A and B originally. The second element of the output list is a list of Boolean values that corresponds to the vector sum of A and B. Make sure that BOOL_ADD is defined so it works regardless of the value chosen for N.

I'm unsure on how to perform the binary addition, then convert it to boolean. I'm also not sure when overflow would ever be changed to TRUE. Earlier in the question we wrote the following HalfAdder function:

def HalfAdder(A,B):
    S = int((A and not B) or (not A and B))
    C = int(A and B)
    return (S, C)

and the FullAdder function:

def FullAdder(A,B,C):
    AB = int((A and not B) or (not A and B))
    S = int((C and not AB) or (not C and AB))
    CAB = int(C and AB)
    C1 = int((A and B) or (CAB))
    return (S,C1)

Would either of those be incorporated?

Here's what I have so far, but it's not working out:

def BoolAdd(A,B):
    L = []
    overflow = False
    for i in range (0,len(A)):
            x = bin(A[i]+B[i])
            x = bool(x)
            L.append(x)
    if (len(L) > len(A)):
        overflow = True

    return [overflow, L]

Any ideas on what I'm doing wrong, or how to approach this problem?

Upvotes: 1

Views: 1806

Answers (1)

Amber
Amber

Reputation: 527193

You have a half adder, you need to construct a full adder from those and then chain multiple calls to that together for each element in the input lists, plus the carry from the previous items.

The chaining is done by using a ripple-carry technique, taking the "carry" output from the previous set of items and feeding it in as the third input.

Upvotes: 1

Related Questions