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

Question

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

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**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

Results:

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

If 1-bit binary math operations (^) are forbidden, go for unary!

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

That is because python is not normally using 32 bit signed int.

See:ctypes.c_int32

Accepted solution:

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