bit wise addtion in C++

Question

I am looking to following code at following link

https://www.geeksforgeeks.org/divide-and-conquer-set-2-karatsuba-algorithm-for-fast-multiplication/

// The main function that adds two bit sequences and returns the addition
string addBitStrings( string first, string second )
{
    string result;  // To store the sum bits

    // make the lengths same before adding
    int length = makeEqualLength(first, second);
    int carry = 0;  // Initialize carry

    // Add all bits one by one
    for (int i = length-1 ; i >= 0 ; i--)
    {
        int firstBit = first.at(i) - '0';
        int secondBit = second.at(i) - '0';

        // boolean expression for sum of 3 bits
        int sum = (firstBit ^ secondBit ^ carry)+'0';

        result = (char)sum + result;

        // boolean expression for 3-bit addition
        carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);
    }

    // if overflow, then add a leading 1
    if (carry)  result = '1' + result;

    return result;
}

I am having difficulty in understanding following expressions

// boolean expression for sum of 3 bits
int sum = (firstBit ^ secondBit ^ carry)+'0';

and other expression

// boolean expression for 3-bit addition
carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);

What is difference between two? What are they trying to achieve?

Thanks

Answer 1

To understand this, a table with all possible combinations may help. (For our luck, the number of combinations is very limited for bits.)

Starting with AND (&), OR (|), XOR (^):

 a | b | a & b | a | b | a ^ b
---+---+-------+-------+-------
 0 | 0 |   0   |   0   |   0
 0 | 1 |   0   |   1   |   1
 1 | 0 |   0   |   1   |   1
 1 | 1 |   1   |   1   |   0

Putting it together:

 a | b | carry | a + b + carry | a ^ b ^ carry | a & b | b & carry | a & carry | a & b | a & carry | b & carry
---+---+-------+---------------+---------------+-------+-----------+-----------+-------------------------------
 0 | 0 |   0   |      00       |      0        |   0   |    0      |     0     |             0
 0 | 0 |   1   |      01       |      1        |   0   |    0      |     0     |             0
 0 | 1 |   0   |      01       |      1        |   0   |    0      |     0     |             0
 0 | 1 |   1   |      10       |      0        |   0   |    1      |     0     |             1
 1 | 0 |   0   |      01       |      1        |   0   |    0      |     0     |             0
 1 | 0 |   1   |      10       |      0        |   0   |    0      |     1     |             1
 1 | 1 |   0   |      10       |      0        |   1   |    0      |     0     |             1
 1 | 1 |   1   |      11       |      1        |   1   |    1      |     1     |             1

Please, note, how the last digit of a + b resembles exactly the result of a ^ b ^ carry as well as a & b | a & carry | b & carry resembles the first digit of a + b.

The last detail is, adding '0' (ASCII code of digit 0) to the resp. result (0 or 1) translates this to the corresponding ASCII character ('0' or '1') again.