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


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.

  • 1
    $\begingroup$ @barakmanos I think he means that he wants a linear time addition algorithm using those three operations, given the binary expansion of the two numbers as input. But that's just a guess. $\endgroup$
    – Arthur
    Mar 26, 2015 at 8:28
  • 1
    $\begingroup$ @Arthur: In either case, there is zero effort shown in the question, and of course, no response to either one of the comments here, which makes it futile to put any effort attempting to understand the question at hand (let alone to answer it). $\endgroup$ Mar 26, 2015 at 8:37
  • 1
    $\begingroup$ @paulpaul1076: I apologize, no hostility meant. But you need to put some effort into your question if you're expecting others to put effort in answering it. $\endgroup$ Mar 26, 2015 at 8:49
  • 1
    $\begingroup$ What barak manos wants is for you to have tried a few things on your own, and tell us about them. $\endgroup$
    – Arthur
    Mar 26, 2015 at 8:53
  • 1
    $\begingroup$ First of all, as already noted in the comments above, your description is not clear. If you can clarify it, then please do it within the question, and not in a comment. Second, please share you thoughts, progress and general effort made towards solving this problem on your own. $\endgroup$ Mar 26, 2015 at 8:54

2 Answers 2


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}

  • $\begingroup$ Thanks man, I don't know why I got stuck on this, I thought I couldn't use any iteration whatsoever, but having thought this through, I guess this is what my prof meant, thanks. $\endgroup$
    – Pavel
    Mar 26, 2015 at 11:10
  • $\begingroup$ This should need a constant of ops times the bit length, so $O(N)$. I tried to model what the usual hardware does and this requires only a constant number of gates. So modulo mistakes I hope this works. $\endgroup$
    – mvw
    Mar 26, 2015 at 11:12
  • $\begingroup$ Yep, exactly what I needed, wish I could upvote. $\endgroup$
    – Pavel
    Mar 26, 2015 at 11:20

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.

  • $\begingroup$ >> is not a boolean operation, so this doesn't answer my question $\endgroup$
    – Pavel
    Mar 26, 2015 at 10:26
  • $\begingroup$ Read my first paragraph, there is no algorithm that answers your question as you stated it. $\endgroup$
    – jack
    Mar 26, 2015 at 10:29
  • $\begingroup$ This is one of the questions I got in my complexity analysis class. I don't think I'd purposely get something impossible. I get your point, though. But I'm pretty sure if I asked the same about multiplication when Katsuba hadn't yet discovered this, you'd be saying the same thing. $\endgroup$
    – Pavel
    Mar 26, 2015 at 10:41
  • $\begingroup$ What I said was a proof, not an opinion. The algorithm you are asking for does not exist any more than a proof that 2+2=6. If this was a question from your class, either your professor is mistaken or you have not presented it correctly. Something that goes beyond bitwise operations is necessary, or else a fixed width is necessary so that you can use constants to distinguish each bit. $\endgroup$
    – jack
    Mar 26, 2015 at 10:44
  • $\begingroup$ The input size of both x and y is N bits, so it is a fixed size $\endgroup$
    – Pavel
    Mar 26, 2015 at 10:48

Not the answer you're looking for? Browse other questions tagged .