What is the algorithm to add up 2 binary numbers when the basis is {negation, co

Question

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be assignments involved.

One example of such program would be Karatsuba's algorithm for multiplying 2 numbers. Here's the algorithm:

x = a * 2^(n/2) + b

y = c * 2^(n/2) + d

z = x * y = (a * 2^(n/2) + b) * (c * 2^(n/2) + d) = ac * 2^n + (ad + bc) * 2^(n/2) + bc

u = (a + b) (c + d)

v = a * c

w = w * d

z = v * 2^n + (u - v - w) * 2^(n/2) + w // result

Example: x = 1011, y = 1101

u = (a+b)(c+d) = 101 * 100

v = 10 * 11 = 110

w = b * d = 11 * 01 = 11

z = 110 * 2^4 + (10100 - 110 - 11) * 2^2 + 11 = 10001111 = 143 base 2

Explanation / Answer

If x=(xN?1?x0)2, y=(yN?1?y0)2 then z=x+y=(zp?z0) via

z0c0zk+1ck+1=(x0+y0)mod2=X0??Y0=(X0?

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.