How to deal with long overflow?

Question

I've been struggling with this for quite a while. I want to solve it using a binary search, and my code is quite straightforward, and I think, correct:

          if (x < 0) {
            return -1;
          }
        if (x == 0 || x == 1) {
            return x;
        }
        int start = 1;
        int end = x;
        while (start<=end) {
            int mid = start+ (end-start)/2;
            if (mid*mid<=x && (mid+1)*(mid+1)>x) return mid;
            if(mid*mid>x) {
                end = mid-1;
            } else {
                start = mid+1;
            }
        }
        return 0;

Of course, it fails for 2147483647 case, because mid*mid causes integer overflow. I've tried dealing with long instead:

long tmp = mid*mid;
long tmp1 = (mid+1)*(mid+1)
if (tmp<=x && tmp1>x) return mid;

However, I get time limit exceeded, because even that overflows. How to deal with situations like this? What am I missing?

Answer 1

As I know, in cpp int is same as long, what you need here is long long. I have no idea about ur time limit exceeded cause by the overflow.

UPDATE

I think I know your problem now.

long tmp = mid*mid;
long tmp1 = (mid+1)*(mid+1)
if (tmp<=x && tmp1>x) return mid;

In your code above, the mid is still int, which means mid * mid is int before the value assigns to tmp, so it will get overflow. The casting order in most language is like this. You should pay attention.

Answer 2

You should use "long long".

Sometimes, "long" == "long int" == "int" or "short" == "short int" == "int". It depends on the system.

Comments

sorry, maybe it wasn't quite obvious, but I am using Java :)