3
$\begingroup$

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.

$\endgroup$
0

4 Answers 4

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Ravi Joshi
    Sep 20, 2012 at 15:45
  • $\begingroup$ @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. $\endgroup$
    – Rick Decker
    Sep 20, 2012 at 15:51
  • 1
    $\begingroup$ @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. $\endgroup$
    – Rick Decker
    Sep 20, 2012 at 16:20
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Ravi Joshi
    Sep 20, 2012 at 15:49
  • $\begingroup$ Edited??? What is the modification? $\endgroup$
    – Ravi Joshi
    Sep 20, 2012 at 15:56
  • $\begingroup$ (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. $\endgroup$ Sep 20, 2012 at 16:07
0
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.