c++ - Subtracting unsigned long longs with signed long long result?

Question

Suppose I have these two types:

typedef unsigned long long uint64;
typedef signed long long sint64;

And I have these variables:

uint64 a = ...;
uint64 b = ...;
sint64 c;

I want to subtract b from a and assign the result to c, clearly if the absolute value of the difference is greater than 2^63 than it will wrap (or be undefined) which is ok. But for cases where the absolute difference is less than 2^63 I want the result to be correct.

Of the following three ways:

c = a - b; // sign conversion warning ignored

c = sint64(a - b);

c = sint64(a) - sint64(b);

Which of the them are guaranteed to work by the standard? (and why/how?)

Answer 1

None of the three work. The first fails if the difference is negative (no matter the absolute value), the second is the same as the first, and the third fails if either operand is too large.

It's impossible to implement without a branch.

c = b < a? a - b : - static_cast< sint64 >( b - a );

Fundamentally, unsigned types use modulo arithmetic without any kind of sign bit. They don't know they wrapped around, and the language spec doesn't identify wraparound with negative numbers. Also, assigning a value outside the range of a signed integral variable results in an implementation-defined, potentially nonsense result (integral overflow).

Consider a machine with no hardware to convert between native negative integers and two's complement. It can perform two's complement subtraction using bitwise negation and native two's complement addition, though. (Bizarre, maybe, but that is what C and C++ currently require.) The language leaves it up to the programmer, then, to convert the negative values. The only way to do that is to negate a positive value, which requires that the computed difference be positive. So…</p>

The best solution is to avoid any attempt to represent a negative number as a large positive number in the first place.

EDIT: I forgot the cast before, which would have produced a large unsigned value, equivalently to the other solutions!

Answer 2

Potatoswatter's answer is probably the most pragmatic solution, but "impossible to implement without a branch" is like a red rag to a bull for me. If your hypothetical system implements undefined overflow/cast operations like that, my hypothetical system implements branches by killing puppies.

So I'm not completely familiar with what the standard(s) would say, but how about this:

sint64 c,d,r;
c = a >> 1;
d = b >> 1;
r = (c-d) * 2;
c = a & 1;
d = b & 1;
r += c - d;

I've written it in a fairly verbose fasion so the individual operations are clear, but have left some implicit casts. Is anything there undefined?

Steve Jessop rightly points out that this does fail in the case where the difference is exactly 2^63-1, as the multiply overflows before the 1 is subtracted.

So here's an even uglier version which should cover all underflow/overflow conditions:

sint64 c,d,r,ov;
c = a >> 1;
d = b >> 1;
ov = a >> 63;
r = (c-d-ov) * 2;
c = a & 1;
d = b & 1;
r += ov + ov + c - d;

Answer 3

if the absolute value of the difference is greater than 2^63 than it will wrap (or be undefined) which is ok. But for cases where the absolute difference is less than 2^63 I want the result to be correct.

Then all three of the notations you suggest work, assuming a conventional architecture. The notable difference is that the third one sint64(a) - sint64(b) invokes undefined behavior when the difference is not representable, whereas the first two are guaranteed to wrap around (unsigned arithmetic overflow is guaranteed to wrap around and conversion from unsigned to signed is implementation-defined, whereas signed arithmetic overflow is undefined).