CODEWITHSUNDEEP
c++math
Baldrick
Baldrick

Reputation: 11002

Shortest way to calculate difference between two numbers?

I'm about to do this in C++ but I have had to do it in several languages, it's a fairly common and simple problem, and this is the last time. I've had enough of coding it as I do, I'm sure there must be a better method, so I'm posting here before I write out the same long winded method in yet another language;

Consider the (lilies!) following code;

// I want the difference between these two values as a positive integer
int x = 7
int y = 3
int diff;
// This means you have to find the largest number first 
// before making the subtract, to keep the answer positive
if (x>y) { 
     diff = (x-y);
} else if (y>x) {
     diff = (y-x);
} else if (x==y) {
    diff = 0;
}

This may sound petty but that seems like a lot to me, just to get the difference between two numbers. Is this in fact a completely reasonable way of doing things and I'm being unnecessarily pedantic, or is my spidey sense tingling with good reason?

Upvotes: 30

Views: 107372

Answers (5)

Max Barraclough
Max Barraclough

Reputation: 264

All the existing answers will overflow on extreme inputs, giving undefined behaviour. @craq pointed this out in a comment.

If you know that your values will fall within a narrow range, it may be fine to do as the other answers suggest, but to handle extreme inputs (i.e. to robustly handle any possible input values), you cannot simply subtract the values then apply the std::abs function. As craq rightly pointed out, the subtraction may overflow, causing undefined behaviour (consider INT_MIN - 1), and the std::abs call may also cause undefined behaviour (consider std::abs(INT_MIN)). It's no better to determine the min and max of the pair and to then perform the subtraction.

More generally, a signed int is unable to represent the maximum difference between two signed int values. The unsigned int type should be used for the output value.

I see 3 solutions. I've used the explicitly-sized integer types from stdint.h here, to close the door on uncertainties like whether long and int are the same size and range.

Solution 1. The low-level way.

// I'm unsure if it matters whether our target platform uses 2's complement,
// due to the way signed-to-unsigned conversions are defined in C and C++:
// >  the value is converted by repeatedly adding or subtracting
// >  one more than the maximum value that can be represented
// >  in the new type until the value is in the range of the new type
uint32_t difference_int32(int32_t i, int32_t j) {
    static_assert(
        (-(int64_t)INT32_MIN) == (int64_t)INT32_MAX + 1,
        "Unexpected numerical limits. This code assumes two's complement."
    );

    // Map the signed values across to the number-line of uint32_t.
    // Preserves the greater-than relation, such that an input of INT32_MIN
    // is mapped to 0, and an input of 0 is mapped to near the middle
    // of the uint32_t number-line.
    // Leverages the wrap-around behaviour of unsigned integer types.

    // It would be more intuitive to set the offset to (uint32_t)(-1 * INT32_MIN)
    // but that multiplication overflows the signed integer type,
    // causing undefined behaviour. We get the right effect subtracting from zero.
    const uint32_t offset = (uint32_t)0 - (uint32_t)(INT32_MIN);
    const uint32_t i_u = (uint32_t)i + offset;
    const uint32_t j_u = (uint32_t)j + offset;

    const uint32_t ret = (i_u > j_u) ? (i_u - j_u) : (j_u - i_u);
    return ret;
}

I tried a variation on this using bit-twiddling cleverness taken from https://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax but modern code-generators seem to generate worse code with this variation. (I've removed the static_assert and the comments.)

uint32_t difference_int32(int32_t i, int32_t j) {
    const uint32_t offset = (uint32_t)0 - (uint32_t)(INT32_MIN);
    const uint32_t i_u = (uint32_t)i + offset;
    const uint32_t j_u = (uint32_t)j + offset;

    // Surprisingly it helps code-gen in MSVC 2019 to manually factor-out
    // the common subexpression. (Even with optimisation /O2)
    const uint32_t t = (i_u ^ j_u) & -(i_u < j_u);
    const uint32_t min = j_u ^ t; // min(i_u, j_u)
    const uint32_t max = i_u ^ t; // max(i_u, j_u)
    const uint32_t ret = max - min;
    return ret;
}

Solution 2. The easy way. Avoid overflow by doing the work using a wider signed integer type. This approach can't be used if the input signed integer type is the largest signed integer type available.

uint32_t difference_int32(int32_t i, int32_t j) {
    return (uint32_t)std::abs((int64_t)i - (int64_t)j);
}

Solution 3. The laborious way. Use flow-control to work through the different cases. Likely to be less efficient.

uint32_t difference_int32(int32_t i, int32_t j)
{   // This static assert should pass even on 1's complement.
    // It's just about impossible that int32_t could ever be capable of representing
    // *more* values than can uint32_t.
    // Recall that in 2's complement it's the same number, but in 1's complement,
    // uint32_t can represent one more value than can int32_t.
    static_assert( // Must use int64_t to subtract negative number from INT32_MAX
        ((int64_t)INT32_MAX - (int64_t)INT32_MIN) <= (int64_t)UINT32_MAX,
        "Unexpected numerical limits. Unable to represent greatest possible difference."
    );

    uint32_t ret;
    if (i == j) {
        ret = 0;
    } else {

        if (j > i) { // Swap them so that i > j
            const int32_t i_orig = i;
            i = j;
            j = i_orig;
        } // We may now safely assume i > j

        uint32_t magnitude_of_greater; // The magnitude, i.e. abs()
        bool     greater_is_negative; // Zero is of course non-negative
        uint32_t magnitude_of_lesser;
        bool     lesser_is_negative;

        if (i >= 0) {
            magnitude_of_greater = i;
            greater_is_negative = false;
        } else { // Here we know 'lesser' is also negative, but we'll keep it simple
            // magnitude_of_greater = -i; // DANGEROUS, overflows if i == INT32_MIN.
            magnitude_of_greater = (uint32_t)0 - (uint32_t)i;
            greater_is_negative = true;
        }

        if (j >= 0) {
            magnitude_of_lesser = j;
            lesser_is_negative = false;
        } else {
            // magnitude_of_lesser = -j; // DANGEROUS, overflows if i == INT32_MIN.
            magnitude_of_lesser = (uint32_t)0 - (uint32_t)j;
            lesser_is_negative = true;
        }

        // Finally compute the difference between lesser and greater
        if (!greater_is_negative && !lesser_is_negative) {
            ret = magnitude_of_greater - magnitude_of_lesser;
        } else if (greater_is_negative && lesser_is_negative) {
            ret = magnitude_of_lesser - magnitude_of_greater;
        } else { // One negative, one non-negative. Difference is sum of the magnitudes.
            // This will never overflow.
            ret = magnitude_of_lesser + magnitude_of_greater;
        }
    }
    return ret;
}

Upvotes: 5

ShinTakezou
ShinTakezou

Reputation: 9661

Using the std::abs() function is one clear way to do this, as others here have suggested.

But perhaps you are interested in succinctly writing this function without library calls.

In that case

diff = x > y ? x - y : y - x;

is a short way.

In your comments, you suggested that you are interested in speed. In that case, you may be interested in ways of performing this operation that do not require branching. This link describes some.

Upvotes: 35

Rapnar
Rapnar

Reputation: 147

Well it depends on what you mean by shortest. The fastet runtime, the fastest compilation, the least amount of lines, the least amount of memory. I'll assume you mean runtime.

#include <algorithm>    // std::max/min   
int diff = std::max(x,y)-std::min(x,y);

This does two comparisons and one operation (this one is unavoidable but could be optimized through certain bitwise operations with specific cases, compiler might actually do this for you though). Also if the compiler is smart enough it could do only one comparison and save the result for the other comparison. E.g if X>Y then you know from the first comparison that Y < X but I'm not sure if compilers take advantage of this.

Upvotes: 4

user529758
user529758

Reputation: 

#include <cstdlib>

int main()
{
    int x = 7;
    int y = 3;
    int diff = std::abs(x-y);
}

Upvotes: 14

juanchopanza
juanchopanza

Reputation: 227370

Just get the absolute value of the difference:

#include <cstdlib>
int diff = std::abs(x-y);

Upvotes: 59

Related Questions