# EPI question on multiplying two integers

The Elements of Programming Interviews book has a question on "computing x*y without arithmetical operators" (question 5.5). The solution is here: https://github.com/epibook/epibook.github.io/blob/master/solutions/cpp/MultiplyShiftAdd.cc

I am confused about the Add() function in the solution. For example, if I want to add a=1110 and b=1, the while loop will execute only once (because temp_b will decrease from 1 to 0). The iteration goes as follows:

ak = 1110 & 1 = 0, bk = 1 & 1 = 1,
carryout = (0 & 1) | 0 | 0 = 0,
sum = sum | (ak ^ bk ^ carryin) = 0 | 1 = 1,
carryin = carryout << 1 = 0,
k = 10,
temp_a = 111,
temp_b = 0


Then we return:

sum | carryin = 1


But the sum of 1110 and 1 should be 1111

EDIT: I realised that the while loop would not stop after the first iteration

• sorry, I just realised that the while loop condition was || and not &&.. Nov 21, 2015 at 15:02
– Raphael
Nov 21, 2015 at 20:01
• If this is a question about understanding C source code, it's offtopic here. Community votes, please!
– Raphael
Nov 21, 2015 at 20:01
• I encourage you to proof-read your question and edit it to fix the formatting. It'd be better to use Markdown and a code block to make it readable, with one statement per line.
– D.W.
Nov 21, 2015 at 22:31

Judging from your comment, it looks like you might see what the issue with your explanation was, but it might be fruitful for someone to see this example worked out, so I'll post this anyway.

We can see that this works by stepping through the execution of this function. Let's use your examples of values for a and b:

a = 0b1110;
b = 0b0001;


We can now step through the function. Here are the initial variable assignments:

sum     = 0;
carryin = 0;
k       = 1;
temp_a  = a; // = 0b1110
temp_b  = b; // = 0b0001


We can now look at the first while loop iteration:

// (temp_a || temp_b) == (0b1110 || 0b0001), so we loop
ak = a & k; // = (0b1110 & 0b0001) = 0
bk = b & k; // = (0b0001 & 0b0001) = 1
carryout =  (ak & bk);      // =      (0 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (1 & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0 | (0 ^ 1 ^ 0)) = (0 | 1) = 1
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 1      << 1 = 0b10
temp_a >>= 1; // = 0b1110 >> 1 = 0b111
temp_b >>= 1; // = 0b0001 >> 1 = 0b000


Thus, after this loop, we have the following variable assignments:

sum     = 1;
carryin = 0;
k       = 0b10;
temp_a  = 0b111;
temp_b  = 0b000;


We then check the condition ((temp_a || temp_b) == (0b111 || 0b000)), and see that it is true, so we loop again:

ak = a & k; // = (0b1110 & 0b010) = 0b10
bk = b & k; // = (0b0001 & 0b010) = 0
carryout =  (ak & bk);      // =      (0b10 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b10 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0    & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (1 | (0b10 ^ 0 ^ 0)) = (1 | 0b10) = 0b11
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b10  << 1 = 0b100
temp_a >>= 1; // = 0b111 >> 1 = 0b11
temp_b >>= 1; // = 0b000 >> 1 = 0b00


Thus, after this loop, we have the following variable assignments:

sum     = 0b11;
carryin = 0;
k       = 0b100;
temp_a  = 0b11;
temp_b  = 0b00;


Checking our condition again, we loop again (there are two loops left, so I will just go ahead and put both of them):

ak = a & k; // = (0b1110 & 0b100) = 0b100
bk = b & k; // = (0b0001 & 0b100) = 0
carryout =  (ak & bk);      // =      (0b100 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b100 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0     & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0b11 | (0b100 ^ 0 ^ 0))
//   = (0b11 | 0b100) = 0b111
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b100 << 1 = 0b1000
temp_a >>= 1; // = 0b11  >> 1 = 0b1
temp_b >>= 1; // = 0b00  >> 1 = 0b0
// Variable assignments:
/* sum     = 0b111;
carryin = 0;
k       = 0b1000;
temp_a  = 0b1;
temp_b  = 0b0; */
// Loop again ((1 || 0) is true)
ak = a & k; // = (0b1110 & 0b1000) = 0b1000
bk = b & k; // = (0b0001 & 0b1000) = 0
carryout =  (ak & bk);      // =      (0b1000 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b1000 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0      & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0b111 | (0b1000 ^ 0 ^ 0))
//   = (0b111 | 0b1000) = 0b1111
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b1000 << 1 = 0b10000
temp_a >>= 1; // = 0b1    >> 1 = 0b0
temp_b >>= 1; // = 0b0    >> 1 = 0b0
// (temp_a || temp_b) == false, so we are done.
// Final variable assignments:
/* sum     = 0b1111;
carryin = 0;
k       = 0b10000;
temp_a  = 0b0;
temp_b  = 0b0;*/


Lastly, we calculate sum | carryin and return:

return sum | carryin; // = 0b1111 | 0 = 0b1111


This returns the result 0b1110 + 0b0001 = 0b1111, which we expect.