Я пытался решить старый вопрос:
Напишите функцию, которая добавит два [целочисленных] числа A и B. Вы не должны использовать + или любые арифметические операторы.
Лучшее решение похоже на это: " проблема LintCode-A + B:
При a + b в любой базе мы можем рассматривать плюс как две части: 1. a + b без переноса; 2. перенос, генерируемый a + b. Затем a + b равен части 1 плюс часть 2. Если part1 + part2 генерирует больше переносов, мы можем повторить эту процедуру до тех пор, пока не будет перенесено.
Я могу понять этот алгоритм, и все кажется хорошим, поэтому я тестировал его на lintcode с кодом, вставленным ниже.
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
Но удивительно, что это дало мне ошибку Time Limit Exceeded в тестовом случае [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)
...
Расчет правильный, поэтому я думаю, что этот алгоритм не работает для такого ввода, но когда я написал тот же алгоритм в С++, он просто работает:
class Solution {
public:
int aplusb(int a, int b) {
while (b!=0){
int carry = a & b;
a = a^b;
b = carry << 1;
}
return a;
}
};
Я не знаю, что именно следует задать, в основном вопросы:
- Почему С++ дает правильный вывод
0, в то время как Python не работает? - Если я использую Python, как мне изменить этот алгоритм, чтобы он работал?
