What is the algorithm to add binary numbers with boolean operations?

Question

What is the algorithm to add up two binary numbers using only boolean operations (negation, conjunction, disjunction) in linear time? Also the program flow needs to be "linear" as well, meaning there can only be assignments involved (no branching).

---

One example of such program would be Karatsuba's algorithm for multiplying two 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 

Converting to base ten we would have $z = 143$, which agrees with $x\cdot y = 11\cdot 13$.

---

With addition we can just XOR everything but I have no idea what to do with the carry, because the 1's won't be contiguously going one after another.

As an example:

x = 101, y = 111

z = (x & ~y) OR (~x & y) = 101 XOR 111 = 010 

We can try to get the carry by doing x & y. Then we would get 101 but need to get 11.

Answer 1

That sounds like a simple adder with carry.

If $x = (x_{N-1} \cdots x_0)_2$, $y = (y_{N-1} \cdots y_0)_2$ then $z = x + y = (z_p \cdots z_0)$ via

\begin{align} z_0 &= (x_0 + y_0) \bmod 2 \\ &= X_0 \dot{\vee} Y_0 = (X_0 \wedge \neg Y_0) \vee (\neg X_0 \wedge Y_0) \\ c_0 &= X_0 \wedge Y_0 \\ z_{k+1} &= (x_k + y_k + c_k) \bmod 2 \\ &= (X_k \wedge \neg Y_k \wedge \neg C_k) \vee (\neg X_k \wedge Y_k \wedge \neg C_k) \vee (\neg X_k \wedge \neg Y_k \wedge C_k) \vee (X_k \wedge Y_k \wedge C_k) \\ c_{k+1} &= (X_k \wedge Y_k \wedge \neg C_k) \vee (X_k \wedge \neg Y_k \wedge C_k) \vee (\neg X_k \wedge Y_k \wedge C_k) \vee (X_k \wedge Y_k \wedge C_k) \end{align}

Answer 2

Your objective, clarified through reasonable assumptions, is not possible. Any algorithm that uses only bitwise operations (I am assuming negation is meant to be bitwise negation), will act the same on corresponding bits regardless of their values. So, if both leading bits are zero and need to end up being one, while both lowest bits are zero, the algorithm will either send (0,0) to 1 and incorrectly set the low bit to one, or it will send (0,0) to 0 and incorrectly set the high bit to zero. This can be mitigated with constants, but any fixed algorithm uses constants of a limited size, and the same argument applies to inputs which have zeros in all bits which are set in any constant.

In real computers, a major method of taking into account bit values is to shift the bits left or right by a certain amount. So, I will add a left or right shift of one to your available base operations. After a left shift of one, the bit with value $2^{k+1}$ is set iff the bit with value $2^k$ was set before the shift, and the low bit is zero. Likewise, after a right shift of one, the bit with value $2^{k-1}$ is set iff the bit with value $2^k$ is representable in the width being used and it was set before the shift.

Also, without any loops or recursion, you will have a constant time algorithm which of course cannot handle arbitrarily large integers. I will use a single conditional recursive step for clarity, but this could easily be replaced with a loop. One way or another, you need control operations for arbitrary addition to be possible.

For your question to make sense, there needs to be a set width representation of the numbers being used. Otherwise, negation will have an infinite or ill defined output. If the width is set absolutely, then any algorithm will be constant time and incapable of arbitrary addition, so assume the width $k$ is set to one greater than the width of the largest input, so as to ensure the output is representable. The following is a possible algorithm under these assumptions, where $x<<1$ means "$x$ left shifted by one" and $x>>1$ means "$x$ right shifted by one", and $k$ and $m$ are the inputs. $x\wedge y$ and $x\vee y$ represent conjunction and disjunction, respectively.

Write the sum discarding carry-overs to $x$ and the carry-overs rightshifted by 1 to $y$:
$x = -k$
$y = -m$
$x = x\wedge y$
$y = k\wedge m$
$x = x\vee y$
$x = -x$

Add in the carry-overs:
if (y!=0){
$z = x>>1$
$y =$ ADD($z,y$)
$y = y<<1$
$x = x\wedge 1$
$x = x\wedge y$
}

A couple notes are in order. $x\vee y=-(-x\wedge -y)$ and $x\wedge y=-(-x\vee-y)$, so conjunction and disjunction are redundant with regard to your apparent objective of a minimal base. Also, the requirement of only assignments is superficial. Any operation can be written out that way using intermediate variables. For example, $x=f(g(y),h(z))$ can be sequenced as $v=g(y)$, $w=h(z)$, and $x=f(v,w)$.

This is not meant to be the most efficient algorithm, it is only intended to demonstrate the kind of things that can be done to build an algorithm like this out of simpler operations. It is, however, easy to verify that the algorithm uses base operations with number bound by a multiple of the input width.