# Get specified bit in addition of two large binary numbers

I am performing an addition operation on two large binary numbers that have an equal number of bits. Both numbers are stored in an array of length $N$, which is rather large.

At first I tried running a loop over them and keeping track of carry bits. This wasted time, because the aim is to get the bit at a specific position in this sum.

So I modified my approach in following way. Starting from the specified index, I am looping until I find a 0 bit in same position on both numbers; I add only those parts to each other and return the bit at the specified position.

This seems okay, but is this the best I can do? Recall that I want to get the value of one specific bit of the sum, given by its position.

Your method will indeed work, but for two $n$-bit numbers it will still take $O(n)$ time. There is a much faster way to solve your problem, with running time $\Theta(\log n)$, known as carry-lookahead addition. The downside is that in my experience teaching this technique, people have a hard time wrapping their heads around it. You can find online sources, here and here, and some algorithm or computer organization texts cover it. It's a really interesting algorithm, well worth taking the time to figure it out.

• Sounds cool... Let me implement it first and examine the performance. For sure it will be fast enough but i am not at all interested in all the bits.
– Ravi Joshi
Sep 20, 2012 at 15:45
• @Ravi Right, and that'll save you some time. Obviously, you don't have to pay any attention to higher-order bits than the one position you're looking at.
– Rick Decker
Sep 20, 2012 at 15:51
• @Ravi. p.s., If you're going to implement this on a real machine, remember that although carry-lookahead addition is a natural candidate for recursion, function calls take a lot of time. It's often best to implement a non-recursive version.
– Rick Decker
Sep 20, 2012 at 16:20

Let $x$ and $y$ denote the two numbers and $x_i$ and $y_i$ the i-th bits in their respective binary representations. You want to determine the $i$-th bit in the binary representation of $x+y$. You are not interested in anything else. If so, proceed as follows.

1. Compute $z = x_i \oplus y_i$.

2. Examine in succession $(x_{i-1},y_{i-1}), (x_{i-2}, y_{i-2}), \ldots$ until you find a pair that is $(0,0)$ or $(1,1)$. If you reach $(x_0, y_0)$ and all pairs have been either $(0,1)$ or $(1,0)$, stop. The answer is $z$.

3. If you find a pair $(x_j, y_j) = (0,0)$, stop. The answer is $z$. If instead $(x_j, y_j) = (1,1)$, stop. The answer is $1-z$ or the bit complement of $z$.

• You will not believe me at all that the same thing i just concluded from binary numbers. Lets me implement it. Thank you for the answer.
– Ravi Joshi
Sep 20, 2012 at 15:49
• Edited??? What is the modification?
– Ravi Joshi
Sep 20, 2012 at 15:56
• (a) I have no reason to disbelieve that you came up with the same idea all by yourself. (b) I deleted a word "if" which made no grammatical sense. If you want to see exactly what change was made, click on the link that says "edited 15 mins ago" or "edited 3 hours ago" or something similar, and it will show you all the changes made since I first posted my answer. Sep 20, 2012 at 16:07

It depends on what language you're using to do this. For instance, if this were C, I wouldn't use arrays. I would use Bitfields. Then I'd have access to Bitfield operations. Simple arithmetic is then done by using a combination of AND, OR, XOR and so on.

As far as I know, your Bitfield length will still be limited to your processor's and/or compiler's capacity, without additional libraries.

Also, this question should have been posted in Stack Overflow.

Each specific bit in the sum of two $n$-bit numbers $A=a_{n}a_{n-1}...a_{1}$ and $B=b_{n}b_{n-1}...b_{1}$ is given by the sum of the corresponding bits in the addends, plus a possible carry of $1$, modulo $2$. The carry is $1$ if the less-significant neighbor bits are $11$, or if they are $01$ or $10$ and subjected to a carry themselves. $$\begin{eqnarray} (A+B)_{k}&=&(A_{k} \oplus B_{k}) \oplus \text{carry}_{k}(A,B) \\ \text{carry}_{k+1}(A,B)&=&(A_{k}\wedge B_{k})\vee((A_{k}\oplus B_{k})\wedge\text{carry}_{k}) \\ \text{carry}_{1}(A,B)&=&0 \end{eqnarray}$$ (Here $\oplus$ means addition modulo $2$.) If the numbers are random, you can expect this to take $O(1)$ time, whereas calculating the sum is certainly $\Theta(n)$. (As a practical matter, though, integer addition is so highly optimized that you will need $n$ to be very large before realizing any speed gain.)