无算术运算符，Python的VS C ++ A + B [英] A + B without arithmetic operators, Python vs C++

问题描述

我是想解决一个古老的问题：

  

编写添加两个[整数]数A功能和B，则不应使用+或任何算术运算符。

最好的解决方法是这样的，从林特code-A报价+ B有问题：

  

有关的任​​何基地+ B，我们可以把加为两部分：1，A + B无进位; 2.通过A + B产生进位。在A + B则等于第1部分加上一部分2.如果第1部+第二部分产生更多的套利，我们可以再重复这个过程，直到没有随身携带。

我可以理解这种算法，一切似乎不错，所以我测试的皮棉$ C与code $ C 粘贴下面。

 类解决方案：
    
    @Param一：第一个整数
    @param B：第二个整数
    @return：a和b的总和
    
    高清aplusb（自我，A，B）：

        而B = 0！
            携带= A和b
            A = A ^ B
            B =进＆LT;＆LT; 1

        返回
 

但出乎意料的是，它给了我时间超出限制测试的情况下误差 [100，-100] 。于是我就在本地打印的a，b，每循环：

 （ -  8,8）
（-16，16）
（-32，32）
（-64，64）
（-128，128）
（-256，256）
（-512，512）
（-1024，1024）
（-2048，2048）
（-4096，4096）
（-8192，8192）
（-16384，16384）
（-32768，32768）
（-65536，65536）
（-131072，131072）
...
 

的计算是正确的，所以我觉得这种算法不适合这样的输入工作，但是当我用C ++写了同样的算法，它只是工作：

 类解决方案{
上市：
    INT aplusb（INT A，INT B）{
        状态，（b！= 0）{
            INT进位= A和B：
            A = A ^ B;
            B =进＆LT;＆LT; 1;
        }
        返回;
    }
};
 

我不知道应该怎样准确地问道，基本问题是：

1. 为什么C ++给出正确的输出 0 而Python不？
2. 如果我使用Python，我怎么修改这个算法，使其工作？

解决方案

二进制，2的补重presentation -4 是

  ... 11100
 

是的，我确实意味着无限多的 1 的左侧;这是一个二进制的重复标号。从技术上来说， 4 是一个重复的数字太：

  ... 00100
 

它只是重复 0 的左侧。

您另外的问题是

  ... 11100
+ ... 00100
--------------------
   ... 00000
 

运营商 ^ ，＆LT;＆LT; 和＆安培; 没有麻烦无穷多个二进制数字计算，但问题是，有无限多的承载者，你是计算它们的一位数字时间的。这将永远不会结束。

因此​​，你不得不承认，当这个算法将陷在这种情况下，做一些别的解释了。

---

您不会遇到在C / C ++这个问题，因为，例如，如果 INT 是除了最右边32位，则所有的数字31位得到简化成单个位，所以它的剩余携带的一次。

不过，从技术上来说，意义左移一个 INT 是在价值方面为整数，而不是作为一个位模式，所以你调用未定义行为的，如果两个最显著位执行是以往任何时候都不同的，因为那样的话执行＆LT;＆LT; 1 将产生溢出）。

I was trying to solve an old question:

Write a function that add two [integer] numbers A and B. You should not use + or any arithmetic operators.

The best solution is like this, quoted from "LintCode-A+B Problem":

For a + b in any base, we can treat the plus as two part: 1. a + b without carry; 2. the carry generated by a +b. The a+b then equals to part 1 plus part 2. If part1+part2 generates more carry, we can then repeat this procedure, until there is no carry.

I can understand this algorithm and everything seems good, so I tested it on lintcode with code pasted below.

class Solution:
    """
    @param a: The first integer
    @param b: The second integer
    @return:  The sum of a and b
    """
    def aplusb(self, a, b):

        while b != 0:
            carry = a & b
            a = a ^ b
            b = carry << 1

        return a

But surprisingly, it gave me Time Limit Exceeded error in test case [100, -100]. So I ran it locally and print a, b for every loop:

(-8, 8)
(-16, 16)
(-32, 32)
(-64, 64)
(-128, 128)
(-256, 256)
(-512, 512)
(-1024, 1024)
(-2048, 2048)
(-4096, 4096)
(-8192, 8192)
(-16384, 16384)
(-32768, 32768)
(-65536, 65536)
(-131072, 131072)
...

The calculation is correct, so I think this algorithm does not work for such input but when I wrote the same algorithm in C++, it just works:

class Solution {
public:
    int aplusb(int a, int b) {
        while (b!=0){
            int carry = a & b;
            a = a^b; 
            b = carry << 1;
        }
        return a;
    }
};

I don't know what should be asked exactly, basically the questions are:

1. Why does C++ give the correct output 0 while Python doesn't?
2. If I use Python, how do I modify this algorithm to make it work?

解决方案

The binary, 2's complement representation of -4 is

...11100

Yes, I really do mean infinitely many 1's to the left; this is a binary repeating numeral. Technically, 4 is a repeating numeral too:

...00100

it's just repeating 0's to the left.

Your addition problem is

   ...11100
+  ...00100
--------------------
   ...00000

The operators ^, <<, and & have no trouble computing with infinitely many binary digits, but the problem is that there are infinitely many carries, and you are computing them one digit at a time. This will never finish.

Thus, you have to recognize when this algorithm will get stuck in this situation and do something else to account for it.

---

You don't run into this problem in C/C++, because, for example, if int is 32-bits, then all of the digits except for the rightmost 31 digits get collapsed into a single bit, so it does the remaining carries all at once.

However, technically speaking, the meaning of left shifting an int is in terms of the value as an integer, rather than as a bit pattern, so you are invoking undefined behavior if the two most significant bits carry are ever different, because then carry << 1 would produce an overflow).

这篇关于无算术运算符，Python的VS C ++ A + B的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！