python - 基于使用标准逻辑运算(如 AND、OR、XOR、NOT)将两个整数相加的算法

Question

基于使用标准逻辑运算(如 AND、OR、XOR、NOT)将两个整数相加的算法

有人知道这方面的算法吗？

由于我对 Python 还很陌生，所以我似乎找不到合适的。

我只需要它来帮助我在正确的方向上制作我的二进制加法程序。

Answer 1

是的。事实上，这实际上是一件非常标准的事情 in hardware .我将在这里总结其背后的逻辑。

如果您逐位执行此操作，则只需对位使用 XOR 和 AND。考虑添加 13 和 6。

13 = binary 1101
6 = binary 0110

我们现在一次对一个位进行操作，从右到左:

1 xor 0 = 1, 1 and 0 = 0 (no carry). "Current" result: 1
0 xor 1 = 1, 1 and 0 = 0 (no carry). "Current" result: 11
1 xor 1 = 0, 1 and 1 = 1 (there *is* a carry "out") "Current" result: 011
There's a carry in, so this is 1 xor 1 xor 0, which is 0. The carry out is 1. Current result: 0011
Next, we need to add the carry-out. Thus, the final number is 10011 (19).

维基百科有 complete truth table为了这。在同一篇文章中，数字的逻辑是 (A xor B) xor Cin，其中 Cin 是进位。

执行的逻辑是

((A xor B) and Cin) or (A and B)

您可以看到我正在描述的数字电路图 here , 使用 this符号说明。

从更数学的角度来看，二进制自然数构成一个 Abelian group在加法下，和二进制自然数形成一个field . (其实十进制和二进制自然数的字段都是isomorphic)。

从更具体的意义上讲，这意味着二进制算术的工作方式类似于十进制算术。例如，它仍然是结合的和交换的。要点是，将两个二进制数相加很像将两个十进制数相加。考虑一下，为了与上面的比较，将 904 和 117 相加。同样，我们从右向左相加。

7 + 4 = 13。因此，结果为 3，进位输出为 1。
0 + 1 = 1。还有一个进位，所以结果是2。
9 + 1 = 10。因此，结果数字为 0，进位输出为 1。

最终结果:1021。

注意这与将二进制数相加有多么相似。我建议尝试“手动”添加一些二进制数，只是为了更好地了解它的工作原理 - 实际上它几乎与十进制数的算术完全一样。

这是执行这些操作的 C# 代码，我假设这是家庭作业，所以我将把它留作练习，将其“翻译”成 Python :)。 (希望语法很熟悉 - 它与 Java 非常相似)。

private static string LeftPad(string array, int length)
    {
        var sb = new StringBuilder();

        for (int i = 0; i < (length - array.Length); i++)
        {
            sb.Append(0);
        }

        sb.Append(array);

        return sb.ToString();
    }

    private static int AddBits(int num1, int num2)
    {
        // Convert the numbers to binary (base-2) strings
        string num1Bits = Convert.ToString(num1, 2);
        string num2Bits = Convert.ToString(num2, 2);

        // Track the current carry-in/carry-out
        int carry = 0;

        // If the strings are of differing lengths, left-pad the shorter one with zeros
        string num1ToAdd = (num1Bits.Length >= num2Bits.Length ? num1Bits : LeftPad(num1Bits, num2Bits.Length));
        string num2ToAdd = (num2Bits.Length >= num1Bits.Length ? num2Bits : LeftPad(num2Bits, num1Bits.Length));
        List<int> resultingDigits = new List<int>();

        // Loop through the strings from right to left and perform the operation listed above
        for (int i = num1ToAdd.Length - 1; i >= 0; i--)
        {
            // Digits we are currently operating on
            int A = int.Parse(num1ToAdd[i].ToString());
            int B = int.Parse(num2ToAdd[i].ToString());

            int result = (A ^ B) ^ carry;

            resultingDigits.Add(result);

            carry = ((A ^ B) & carry) | (A & B);
        }

        // If there's a carry, add that as well
        if (carry == 1)
            resultingDigits.Add(1);

        // Change the endianness
        resultingDigits.Reverse();

        var sb = new StringBuilder();

        for (int i = 0; i < resultingDigits.Count; i++)
        {
            sb.Append(resultingDigits[i]);
        }

        // Convert the base-2 (binary) string to a regular int
        return Convert.ToInt32(sb.ToString(), 2);
    }