A + B без арифметических операторов, Python против C++

Question

Я пытался решить старый вопрос:

Написать функцию, которая добавить два [целые] числа A и B. Не следует использовать + или любую арифметику операторы.

Лучшее решение, как это, цитата из «LintCode-A+B Problem»:

Для + Ь в любой базе, мы можем рассматривать плюс как две части: 1. а + б без переноса; 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]. Так что я побежал локально и печатать, а для каждого цикла:

(-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++, он просто работает :

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

Я не знаю, что следует задавать точно, в основном вопросы являются:

1. Почему C++ дать правильный вывод 0 в то время как Python не делает?
2. Если я использую Python, как мне изменить этот алгоритм, чтобы он работал?

Answer 1

Двоичный, 2 дополнением представление -4 является

...11100 

Да, я действительно имею в виду бесконечное множество 1 «S влево; это двоичная повторяющаяся цифра. Технически 4 это повторение цифры тоже:

...00100 

это просто повторение 0 «S влево.

Ваша проблема добавления

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

Операторы ^, << и & не имеют никаких проблем вычислений с бесконечным числом двоичных разрядов, но проблема в том, что существует бесконечно много несет, и вы их вычисления одна цифра за раз. Это никогда не закончится.

Таким образом, вы должны признать, что этот алгоритм застрянет в этой ситуации и сделает что-то еще для его учета.

---

Вы не столкнулись с этой проблемой в C/C++, потому что, например, если int имеет длину 32 бита, то все из цифр для правых 31 цифр, за исключением получить рухнуло в один бит, так что остальное несет все сразу.

Однако с технической точки зрения, смысл оставил сдвинув int в терминах значения как целое, а не как битовый шаблон, так что вы призываете неопределенное поведение если два старших бита carry когда-либо другой, потому что тогда carry << 1 произведет переполнение).

Answer 2

Проблема - это отрицательные числа, или, как они представлены. В Python целые числа имеют произвольную точность, а C++ ints - 32-битные или 64-битные. Поэтому в Python вам приходится обрабатывать отрицательные числа, например. вычитания, отдельно или ограничить количество бит вручную.

Answer 3

После большого объяснения по @Hurkyl, я прошел через алгоритм a=4 и b=-4 используя тот факт, что питон реализует бесконечное двоичное комплимент представление:

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-разрядного целого числа комплиментов двух подписей. После того, как бит переноса пузырится выше максимального бита, алгоритм должен быть остановлен. Далее, кажется, работает:

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 

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

Answer 5

Мое решение:

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) 

Как уже говорилось, побитовое лучше.

Answer 6

Это потому, что 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