用于基于标准逻辑运算（例如AND，OR，XOR，NOT）的两个整数相加的算法 [英] Algorithm for adding two integers based on the use of standard logical operations like AND, OR, XOR, NOT

问题描述

用于基于标准逻辑运算（例如AND，OR，XOR，NOT）的两个整数相加的算法

有人知道吗

我似乎找不到适合我的算法，因为我是Python的新手。

I can't seem to find one that works as I am very new to Python.

我只是需要它来帮助我正确地制作二进制加法程序。

I just need to it to help me in the right direction to make my binary addition program.

推荐答案

是的。实际上，这实际上是在硬件中 的相当标准的事情。在这里，我将对其背后的逻辑进行总结。

Yes. In fact, this is actually a pretty standard thing to do in hardware. I'll give a summary of the logic behind it here.

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

If you do this bit-by-bit, you can just use XOR and AND on the bits. Consider adding 13 and 6.

13 = binary 1101
6 = binary 0110

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

We now operate on the bits one at a time, right to left:

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).

Wikipedia具有完整的真值表。在同一篇文章中，数字的逻辑是（A xor B）xor Cin ，其中 Cin 是进位

Wikipedia has the complete truth table for this. From the same article, the logic for the digit is (A xor B) xor Cin where Cin is the carry in.

结转的逻辑是

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

您可以看到数字电路图我正在使用此处 href = https://en.wikipedia.org/wiki/Logic_gate#Symbols rel = nofollow noreferrer>符号的描述。

You can see a diagram of the digital circuit that I'm describing here, using this description of the symbols.

从更数学的角度来看，二进制自然数在加法下形成 Abelian群和二进制自然数数字形成一个字段。 （实际上，十进制和二进制自然数的字段是同构）。

From a more mathematical perspective, binary natural numbers form an Abelian group under addition, and binary natural numbers form a field. (In fact, the fields of decimal and binary natural numbers are isomorphic).

从更实际的意义上说，二进制算术的工作方式类似于十进制算术。例如，它仍然是关联和可交换的。要点是，添加两个二进制数很像添加两个十进制数。考虑与上面的比较，将904和117相加。再次，我们从右到左添加。

What this means in a more tangible sense is that binary arithmetic works in a way that's analogous to decimal arithmetic. It's still associative and commutative, for example. Point being that adding two binary numbers is a lot like adding two decimal numbers. Consider, for comparison to above, adding 904 and 117. Again, we add right to left.

7 + 4 =13。因此，结果是3，结转是1.

0 +1 =1。还有一个结转，所以结果是2。

9 +1 = 10。因此，得出的数字为0，且进位值为1。

7 + 4 = 13. Thus, the result is 3 and the carry-out is 1.
0 + 1 = 1. There's also a carry-in, so the result is 2.
9 + 1 = 10. Thus, the resulting digit is 0 and the carry-out is 1.

最终结果：1021。

请注意，这与添加二进制数有多相似。我建议尝试手动添加一些二进制数字，以使人们对它的工作方式有更多的了解-实际上，这几乎就像对十进制数字的算术运算。

Note how similar that was to adding the binary numbers. I'd suggest trying to add a few binary numbers "by hand" just to get more of a feel for how it works - it's almost exactly like arithmetic on decimal numbers actually.

这是执行这些操作的C＃代码，我假设这是家庭作业，因此我将其保留为练习，以将其翻译为Python :)。 （希望语法很熟悉-它与Java非常相似。）

Here's C# code to perform these operations, I'm assuming this is homework so I'll leave it as an exercise to "translate" this into Python :). (Hopefully the syntax is familiar - it's very similar to 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);
    }

这篇关于用于基于标准逻辑运算（例如AND，OR，XOR，NOT）的两个整数相加的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！