回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我想解决一个老问题:</p>
<blockquote>
<p>Write a function that add two [integer] numbers A and B. You should not use + or any arithmetic operators.</p>
</blockquote>
<p>最好的解决方案是这样的,引用自“<a href="http://www.cnblogs.com/lishiblog/p/4194937.html" rel="nofollow">LintCode-A+B Problem</a>”:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>我能理解这个算法,而且一切看起来都很好,所以我在<a href="http://www.lintcode.com/en/problem/a-b-problem/" rel="nofollow">lintcode</a>上用下面粘贴的代码测试了它。</p>
<pre><code>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
</code></pre>
<p>但令人惊讶的是,它在测试用例中给了我<code>Time Limit Exceeded</code>错误。所以我在本地运行它并为每个循环打印a,b:</p>
<pre><code>(-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)
...
</code></pre>
<P>计算是正确的,所以我认为这种算法对于这样的输入不起作用,但是当我在C++中写同样的算法时,它只是工作:</p>
<pre><code>class Solution {
public:
int aplusb(int a, int b) {
while (b!=0){
int carry = a & b;
a = a^b;
b = carry << 1;
}
return a;
}
};
</code></pre>
<p>我不知道该问什么,基本上问题是:</p>
<ol>
<为什么C++给出正确的输出^ {< CD3}},而Python却不呢?</li>
<li>如果我使用Python,如何修改该算法使其工作?</li>
</ol>