I am performing an addition operation on two large binary numbers that have an e

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.

Explanation / Answer

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 ?(logn), 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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.