c++ - C++中的按位加法

我在以下链接中寻找以下代码

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;
}

我很难理解以下表达

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

和其他表达

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

两者之间有什么区别？他们想达到什么目的？

谢谢

最佳答案

为了理解这一点，包含所有可能组合的表格可能会有所帮助。（幸运的是，组合的位数非常有限。）

以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

把它放在一起：

 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

请注意，a + b的最后一位数字与a ^ b ^ carry的结果完全相似，而a & b | a & carry | b & carry类似于a + b的第一位数字。

最后一个细节是，将'0'（数字0的ASCII码）添加到相应的代码中。结果（0或1）将其再次转换为相应的ASCII字符（'0'或'1'）。