Infinite loop while adding two integers using bitwise operations?

Question

I am trying to solve a problem, using python code, which requires me to add 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 if the input is two positive integers or two negative integers but it fails when one number is positive and other is negative. It goes into an infinite loop. Any idea as to why this might be happening?

EDIT: Here is the link discussing the code fix for this.

Which test values are you using for a and b? Print or watch the values of a and b during the loop - do they fall into a repeating pattern? Also, does it make a difference whether a or b is the negative operand? — cxw
– cxw, Commented Aug 24, 2016 at 2:39

cxw · Accepted Answer · 2016-08-24 02:55:54Z

9

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.

edited Aug 24, 2016 at 2:55

answered Aug 24, 2016 at 2:47

cxw

17.2k2 gold badges50 silver badges84 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Mr Matrix Over a year ago

Thanks for your explanation. This is exactly what was happening when I printed the numbers.

Mr Matrix Over a year ago

what tweak would you suggest to this code to handle this edge case ?

cxw Over a year ago

@Mowgli Ah! That is an entirely different question :) . Seriously, though, I would suggest you post a new question, linking to this one, and asking "how to fix." I've never seen anyone complain about doing so. SO values tightly focused questions, and who knows? someone else may have a better fix than I would come up with. Post the link to that question in a comment here and I'll take a look at it.

cxw Over a year ago

@Mowgli I also wouldn't describe something that happens for 50% of integer pairs as an "edge case." :) :) If I had to tweak it, I would do if math.copysign(a,b) != a: raise ValueError("I'm sorry, Dave. I'm afraid I can't do that.") at the beginning of the function. :)

Mikhail_Sam · Accepted Answer · 2022-10-19 15:41:52Z

I faced the same problem. More precise: you get infinity loop only when one number positive, another negative AND positive >= abs(negative). As @cvx said it works so because of extra carry bit - another languages ignore overflows, but python adds this additional 1 to number and it become more and more and b never become zero.

So the solution is to use mask: lets ignore this additional bit:

def getSum(a: int, b: int) -> int:
    mask = 0xffffffff
    while b&mask > 0:
        carry = a & b
        cur_sum = a ^ b
        a = cur_sum
        b = carry << 1

    return a&mask if b>0 else a

Also the last line is important! As python adds such 1 to a also, and python thinks about it like a negative value. We should skip those bits and get only last part of the a as positive number.

More information here: https://leetcode.com/problems/sum-of-two-integers/discuss/489210/Read-this-if-you-want-to-learn-about-masks

kloppen · Accepted Answer · 2016-08-24 02:53:16Z

-2

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.

answered Aug 24, 2016 at 2:53

kloppen

152 bronze badges

2 Comments

cxw Over a year ago

Welcome to the site, and thanks for answering! I agree that learning by doing is the best. While you're online, check out the tour for more about what goes into an answer that is likely to receive upvotes. Enjoy!

Mr Matrix Over a year ago

Thanks for answering kloppen. I never wanted the working code. I just wanted to understand what was happening. And this is not a homework question. :)

Collectives™ on Stack Overflow

Infinite loop while adding two integers using bitwise operations?

3 Answers 3

4 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related