A + B без арифметических операторов, Python vs С++
Я пытался решить старый вопрос:
Напишите функцию, которая добавит два [целочисленных] числа 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, как мне изменить этот алгоритм, чтобы он работал?
Ответы
Ответ 1
Бинарное, 2-комплементное представление -4 равно
...11100
Да, я действительно имею в виду бесконечное число 1 слева; это двоичная повторяющаяся цифра. Технически, 4 также является повторяющейся цифрой:
...00100
он просто повторяет 0 влево.
Проблема с добавлением
...11100
+ ...00100
--------------------
...00000
Операторы ^, << и & не имеют проблем с вычислением с бесконечным числом двоичных цифр, но проблема в том, что существует бесконечно много переносов, и вы вычисляете их по одной цифре за раз. Это никогда не закончится.
Таким образом, вам нужно узнать, когда этот алгоритм застрянет в этой ситуации и сделает что-то еще для его учета.
Вы не сталкиваетесь с этой проблемой в C/С++, потому что, например, если int является 32-битным, тогда все цифры, кроме самых правых 31 цифр, сворачиваются в один бит, поэтому остальное несет все сразу.
Однако, с технической точки зрения, значение сдвига влево int имеет значение как целое число, а не как битовый шаблон, поэтому вы вызываете поведение undefined, если два наиболее значимых бита carry всегда разные, потому что тогда carry << 1 приведет к переполнению).
Ответ 2
Проблема - это отрицательные числа или, как они представлены. В Python целые числа имеют произвольную точность, а С++ ints - 32-битные или 64-битные. Поэтому в Python вам приходится обрабатывать отрицательные числа, например. вычитания, отдельно или ограничить количество бит вручную.
Ответ 3
Следуя большому объяснению @Hurkyl, я прошел через алгоритм для a=4 и b=-4, используя тот факт, что python реализует бесконечное два представления комплимента:
Step 0:
a = ...(0)...000100
b = ...(1)...111100
carry = a & b = ...(0)...000100
a = a ^ b = ...(1)...111000
b = carry << 1 = ...(0)...001000
Step 1:
a = ...(1)...111000
b = ...(0)...001000
carry = a & b = ...(0)...001000
a = a ^ b = ...(1)...110000
b = carry << 1 = ...(0)...010000
Step 2:
a = ...(1)...110000
b = ...(0)...010000
carry = a & b = ...(0)...010000
a = a ^ b = ...(1)...100000
b = carry << 1 = ...(0)...100000
Понятно, что должно быть эффективное обрезание для эмуляции чего-то вроде 32-битного подписанного двух комплиментов integer. После того, как бит переноса пузырится выше максимального бита, алгоритм должен быть остановлен. Появится следующее:
MAX_BIT = 2**32
MAX_BIT_COMPLIMENT = -2**32
def aplusb(a, b):
while b != 0:
if b == MAX_BIT:
return a ^ MAX_BIT_COMPLIMENT
carry = a & b
a = a ^ b
b = carry << 1
return a
Результаты:
>>> aplusb(100,-100)
0
>>> aplusb(100,-99)
1
>>> aplusb(97,-99)
-2
>>> aplusb(1000,-500)
500
>>> aplusb(-1000,8000)
7000
Ответ 4
Если 1-битные бинарные математические операции (^) запрещены, перейдите к унарным!
from itertools import chain
def unary(x):
"Unary representation of x"
return ''.join(['x' for _ in range(0,x)])
def uplus(x, y):
"Unary sum of x and y"
return [c for c in chain(x,y)]
def plus(i, j):
"Return sum calculated using unary math"
return len(uplus(unary(i), unary(j)))
Ответ 5
Это связано с тем, что в python обычно не используется 32-битный подписанный int.
Смотрите: ctypes.c_int32
Принятое решение:
class Solution:
"""
@param a: The first integer
@param b: The second integer
@return: The sum of a and b
"""
def aplusb(self, a, b):
import ctypes
a = ctypes.c_int32(a).value
a = ctypes.c_int32(a).value
while b != 0:
carry = ctypes.c_int32(a & b).value
a = ctypes.c_int32(a ^ b).value
b = ctypes.c_int32(carry << 1).value
return a
Ответ 6
Мое решение:
def foo(a, b):
"""iterate through a and b, count iteration via a list, check len"""
x = []
for i in range(a):
x.append(a)
for i in range(b):
x.append(b)
print len(x)
Как уже было сказано, поразрядное лучше.
