Get specified bit in addition of two large binary numbers

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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.

Answer 4

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.)