Infinite loop while adding two integers using bitw

Question

I am trying to solve a question which is about writing python code for adding two integers without the use of '+' or '-' operators. I have the following code which works perfectly for two positive numbers:

def getSum(self, a, b):

    while (a & b):
        x = a & b
        y = a ^ b
        a = x << 1
        b = y

    return a ^ b

This piece of code works perfectly for if input is two positive integers or two negative integers but it fails when one number is positive and other is negative. It goes into infinite loop. Any idea as to why this might be happening ?

Answer 1

I'm guessing that this is a homework question, so I don't want to just give you a function that works --- you'll learn more by struggling with it.

The issue stems from the way that negative integers are stored. For illustration purposes, let's pretend that you're dealing with 4-bit signed integers (instead of 32-bit signed integers, or whatever). The number +1 is 0001. The number -1 is 1111. You should be able to sit down with a pen and paper and manually run your function using these two numbers. The answer, of course, should be 0000, but I think you'll discover what's going wrong with your code by working this simplified case with a pen and paper.

Answer 2

Python 3 has arbitrary-precision integers ("bignums"). This means that anytime x is negative, x << 1 will make x a negative number with twice the magnitude. Zeros shifting in from the right will just push the number larger and larger.

In two's complement, positive numbers have a 0 in the highest bit and negative numbers have a 1 in the highest bit. That means that, when only one of a and b is negative, the top bits of a and b will differ. Therefore, x will be positive (1 & 0 = 0) and y will be negative (1 ^ 0 = 1). Thus the new a will be positive (x<<1) and the new b will be negative (y).

Now: arbitrary-precision negative integers actually have an infinite number of leading 1 bits, at least mathematicallly. So a is a larger and larger positive number, expanding by 2 each iteration. b keeps getting more and more leading 1 bits added to be able to carry out the bitwise & and ^ with a. Thus whatever bits of a are turned on line up with one of the added 1 bits of b, so a & b is always true, so the loop runs forever.