EPI question on multiplying two integers

Question

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

Answer 1

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.