A + B without arithmetic operators, Python vs C++

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

The problem are negative numbers, or, how they are represented. In Python integer numbers have arbitrary accuracy, while C++ ints are 32bit or 64bit. So in Python, you have to handle negative numbers, e.g. subtraction, separately, or limit the number of bits by hand.

Following the great explanation by @Hurkyl , I stepped through the algorithm for a=4 and b=-4 using the fact that python implements an infinite two's compliment representation:

Step 0:a = ...(0)...000100b = ...(1)...111100carry = a & b = ...(0)...000100a = a ^ b = ...(1)...111000b = carry << 1 = ...(0)...001000Step 1:a = ...(1)...111000b = ...(0)...001000carry = a & b = ...(0)...001000a = a ^ b = ...(1)...110000b = carry << 1 = ...(0)...010000Step 2:a = ...(1)...110000b = ...(0)...010000carry = a & b = ...(0)...010000a = a ^ b = ...(1)...100000b = carry << 1 = ...(0)...100000

It is clear that there needs to be an effective cutoff to emulate something like a 32-bit signed two's compliment integer. Once the carry bit bubbles up beyond highest bit the algorithm needs to be halted. The following appears to work:

MAX_BIT = 2**32MAX_BIT_COMPLIMENT = -2**32def 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

Results:

>>> aplusb(100,-100)0>>> aplusb(100,-99)1>>> aplusb(97,-99)-2>>> aplusb(1000,-500)500>>> aplusb(-1000,8000)7000