C++: Difference of two unsigned 64-bit integer in a signed 64-bit integer

Question

I am trying to write a function in C++ which takes two 64 bit unsigned integers and returns their difference in a signed 64 bit integer. It seems to be a bit complicated because of the overflow situation - Since the inputs are two unsigned positive integers, if the absolute difference between these two is greater than maximum signed value (INT64_MAX), then the difference cannot be transmitted through a signed integer. So I have written the following implementation, and I was wondering, first, if this is correct functionally, and second, is there a simpler implementation. Any suggestions would be greatly appreciated. Thanks! (I am going to replace the assert with an exception, it is just there for now!)

int64_t GetDifference(uint64_t first, uint64_t second) {
  uint64_t abs_diff = (first > second) ? (first - second): (second - first);    
  uint64_t msb_abs_diff = (abs_diff >> (sizeof(abs_diff)*8 - 1)) & 1;
  assert(msb_abs_diff == 0);
  int64_t diff = first - second;
  return diff;
}

Fanatical

Okay, Thanks to all the answers! I was more worried about the functional correctness, which is okay I guess.. The improvements are all valid, albeit not fundamentally different, and I would incorporate them. – Fanatical

any decent compiler should be able to optimize such code, jut make sure it is correct. – Hallmark

Answer 1

To me this seems a simpler and more readable implementation.

int64_t GetDifference(uint64_t first, uint64_t second) {
    uint64_t abs_diff = (first > second) ? (first - second): (second - first);
    assert(abs_diff<=INT64_MAX);
    return (first > second) ? (int64_t)abs_diff : -(int64_t)abs_diff;
}

Anatomical

Answer 2

This is shorter and likely faster.

int64_t GetDifference(uint64_t first, uint64_t second)
{
  int64_t diff = first - second;
  bool overflowed = (diff < 0) ^ (first < second);
  assert(!overflowed);
  return diff;
}

A good optimizing compiler should notice that diff < 0 is the negative flag and first < second is the carry flag from the prior expression. Comparing these two flags is the classic test for overflow.

Even if it doesn't detect that, there are fewer operations required.

But the biggest reason I prefer this is that there are no magic numbers.

Conglobate

Thanks.. I see your point... if there was int / uint instead of int64_t / uint64_t this would be the one that would work... – Fanatical

There are no magic numbers but you are relying on "undefined behaviour", that is the fact that casting an unsigned which overflows the integer representation wraps around – Dabbs

@Triskeldeian: It's "implementation defined", not "undefined". – Conglobate

Answer 3

Three nitpicks:

• sizeof(abs_diff)*8 - 1 can be replaced by the literal 63 without loss of portability (in fact, it will be more portable because of platforms where a char is not 8 bits wide)
• & 1 is not needed, since the result of the shift is always one bit
• You can derive diff from abs_diff without repeating the subtraction.

Otherwise, this seems perfectly correct to me.

Huxley

sizeof(abs_diff)*CHAR_BIT - 1 will be more portable – Nairobi

Answer 4

How about this:

int64_t GetDifference(uint64_t first, uint64_t second) {
    int64_t diff = (int64_t)(first - second);
    assert first >= second && diff >= 0 || first < second && diff < 0;
    return diff;
}

Erbium