Addition of Binary Integers Pseudocode
By James Williams
$\begingroup$
For the additions of two binary expansion algorithm below,
$$ a = (a_{n-1}\cdots a_0)_2, b = (b_{n-1}\cdots b_0)_2$$
Question: For complexity, i found the total number of additions to be $(n-1)\times5$ as we have 2 in $d$ and 3 in $s_j$ as $2d$ amounts for two operations based on my understanding. Is that correct?
Question#2: why $d$, $s_j$ and $c$ are defined as below in the algorithm? Is there an explanation for that please? Addition of binaries is easy with hand with carry, etc. But I don't understand why the formulas for $d$, $s_j$ and $c$ as below?
2 Answers
$\begingroup$What are the possible outcomes of bitwise addition of two single-bit numbers?
$$0 + 0 = 00 = $$
$$1 + 0 = 0 + 1 = 01$$
$$1 + 1 = 10$$
Here, the answer needs two bits to be represented due to carry forward ($c$ in the above algorithm)
Now, when adding multiple bits, what are the various cases possible? The third number is the carryforward from the previous bit addition
$$0 + 0 +0 = 00 \implies s_j = 0, c = 0$$
$$1 + 0 + 0 = 0+ 1 + 0 = 01 \implies s_j = 1, c = 0$$
$$1 + 0 + 1 = 0 + 1 + 1 = 10 \implies s_j = 0, c = 1$$
$$1 + 1 + 0 = 10 \implies s_j = 0, c = 1$$
$$1 + 1 + 1 = 11\implies s_j = 1, c = 1$$
Now the algorithm has just condensed the following into a more elegant form using the floor function and a temporary variable $d$
$\endgroup$ 2 $\begingroup$This code snippet actually add two binary numbers I will explain it to you and how the formula is working.
First of all let me introduce you with the variables and there needs in above algorithm:
c This will be used to store your carry.
$s_j$ This will be used to store the resultant $jth$ bit.
d Intermediate that actually help you to determine value of $jth$ bit as well as it is always equal to carry.
Formulas are quite easy if you ponder over it like imagine you have some carry and you want to add two bits so you add bits and carry together and got result as $r$ now we want next carry which can be simply obtained by dividing $r$ with $2$ as you are dealing with binary addition.
Time complexity is O(n) as loop iterates for n times you need not to count total operations inside a loop you may refer how complexity is calculated if you want.
$\endgroup$
