CPlus
CPlus

Reputation: 4848

How could I safely find the absolute difference between 2 signed integers in C?

An absolute difference would be the absolute value of the difference between 2 numbers. Suppose I have 2 int variables (x and y) and I would like to find the absolute difference. An easy solution would be:

unsigned diff = abs(x-y);

However these invoke undefined behavior and give incorrect results if overflow occurs such as if x is INT_MIN and y is INT_MAX. This returns 1 (assuming wraparound behavior) instead of UINT_MAX as expected.

Upvotes: 5

Views: 3996

Answers (5)

poby
poby

Reputation: 1756

I know it's not C but in C++ the simplest is:

uint32_t diff(int a, int b) { return std::max(a, b) - std::min(a, b); };

MSVC translates this to:

mov         eax,ebp
cmp         ebx,ebp  
cmovl       eax,ebx  
cmovg       ebp,ebx  
sub         ebp,eax

So one comparison, no jumps and it works with INT_MIN and INT_MAX

UPDATE

As suggested by @CPlus, the identical code is generated if std::max and std::min are replaced with x > y ? x : y and x < y ? x : y respectively. So this method will work for C.

Upvotes: 2

Gabriel Staples
Gabriel Staples

Reputation: 53065

Alright, the following works. @user16217248 got me started. See the discussion under that answer.

How to safely and efficiently find abs((int)num1 - (int)num2)

/// Safely and efficiently return `abs((int)num1 - (int)num2)`
unsigned int abs_num1_minus_num2_int(int num1, int num2)
{
    unsigned int abs_diff = num1 > num2 ?
        (unsigned int)num1 - (unsigned int)num2 :
        (unsigned int)num2 - (unsigned int)num1;

    return abs_diff;
}

The secret is to do the num1 > num2 ternary comparison with signed integer values, but then to reinterpret cast them to unsigned integer values to allow for well-defined overflow and underflow behavior when getting the absolute value of num1 - num2.

Here is my full test code:

absolute_value_of_num1_minus_num2.c from my eRCaGuy_hello_world repo:

///usr/bin/env ccache gcc -Wall -Wextra -Werror -O3 -std=gnu17 "$0" -o /tmp/a -lm && /tmp/a "$@"; exit
// For the line just above, see my answer here: https://stackoverflow.com/a/75491834/4561887

#include <limits.h>
#include <stdbool.h> // For `true` (`1`) and `false` (`0`) macros in C
#include <stdint.h>  // For `uint8_t`, `int8_t`, etc.
#include <stdio.h>   // For `printf()`


#define TEST_EQ(func, num1, num2, equals) \
    printf("%s\n", func((num1), (num2)) == (equals) ? "Passed" : "FAILED")

/// Safely and efficiently return `abs((int8_t)num1 - (int8_t)num2)`
uint8_t abs_num1_minus_num2_int8(int8_t num1, int8_t num2)
{
    // Note: due to implicit type promotion rules, rule 2 in my answer here
    // (https://stackoverflow.com/a/72654668/4561887) applies, and both the `>`
    // comparison, as well as subtraction, take place below as `int` types.
    // While signed `int` overflow and underflow is undefined behavior, none of
    // that occurs here.
    // - It's just useful to understand that even though we are doing
    //   `(uint8_t)num1 -(uint8_t)num2`, the C compiler really sees it as this:
    //   `(int)(uint8_t)num1 - (int)(uint8_t)num2`.
    // - This is because all small types smaller than `int`, such as `uint8_t`,
    //   are first automatically implicitly cast to `int` before any
    //   mathematical operation or comparison occurs.
    // - The C++ compiler therefore sees it as this:
    //   `static_cast<int>(static_cast<unsigned char>(num1)) - static_cast<int>(static_cast<unsigned char>(num2))`.
    //   - Run this code through https://cppinsights.io/ to see that.
    //     See here: https://cppinsights.io/s/bfc425f6 --> and click the play
    //     button.
    uint8_t abs_diff = num1 > num2 ?
        (uint8_t)num1 - (uint8_t)num2 :
        (uint8_t)num2 - (uint8_t)num1;

    // debugging
    printf("num1 = %4i (%3u); num2 = %4i (%3u); num1-num2=%3u;  ",
        num1, (uint8_t)num1, num2, (uint8_t)num2, abs_diff);

    return abs_diff;
}

/// Safely and efficiently return `abs((int)num1 - (int)num2)`
unsigned int abs_num1_minus_num2_int(int num1, int num2)
{
    unsigned int abs_diff = num1 > num2 ?
        (unsigned int)num1 - (unsigned int)num2 :
        (unsigned int)num2 - (unsigned int)num1;

    // debugging
    printf("num1 = %11i (%10u); num2 = %11i (%10u); num1-num2=%10u;  ",
        num1, (unsigned int)num1, num2, (unsigned int)num2, abs_diff);

    return abs_diff;
}


int main()
{
    printf("Absolute difference tests.\n");

    // ---------------
    // int8_t types
    // ---------------

    int8_t num1_8;
    int8_t num2_8;

    printf("\n");
    printf("INT8_MIN = %i, INT8_MAX = %i\n", INT8_MIN, INT8_MAX); // -128, 127

    num1_8 = -7;
    num2_8 = -4;
    TEST_EQ(abs_num1_minus_num2_int8, num1_8, num2_8, 3);

    num1_8 = INT8_MIN;
    num2_8 = INT8_MAX;
    TEST_EQ(abs_num1_minus_num2_int8, num1_8, num2_8, UINT8_MAX);

    num1_8 = INT8_MAX;
    num2_8 = INT8_MIN;
    TEST_EQ(abs_num1_minus_num2_int8, num1_8, num2_8, UINT8_MAX);

    num1_8 = 100;
    num2_8 = 10;
    TEST_EQ(abs_num1_minus_num2_int8, num1_8, num2_8, 90);

    num1_8 = 10;
    num2_8 = 100;
    TEST_EQ(abs_num1_minus_num2_int8, num1_8, num2_8, 90);

    num1_8 = 10;
    num2_8 = 10;
    TEST_EQ(abs_num1_minus_num2_int8, num1_8, num2_8, 0);

    num1_8 = INT8_MAX;
    num2_8 = 1;
    TEST_EQ(abs_num1_minus_num2_int8, num1_8, num2_8, 126);

    num1_8 = 1;
    num2_8 = INT8_MAX;
    TEST_EQ(abs_num1_minus_num2_int8, num1_8, num2_8, 126);

    // ---------------
    // int types
    // ---------------

    int num1;
    int num2;

    printf("\n");
    printf("INT_MIN = %i, INT_MAX = %i\n", INT_MIN, INT_MAX); // -2147483648, 2147483647

    num1 = -7;
    num2 = -4;
    TEST_EQ(abs_num1_minus_num2_int, num1, num2, 3);

    num1 = INT_MIN;
    num2 = INT_MAX;
    TEST_EQ(abs_num1_minus_num2_int, num1, num2, UINT_MAX);

    num1 = INT_MAX;
    num2 = INT_MIN;
    TEST_EQ(abs_num1_minus_num2_int, num1, num2, UINT_MAX);

    num1 = 100;
    num2 = 10;
    TEST_EQ(abs_num1_minus_num2_int, num1, num2, 90);

    num1 = 10;
    num2 = 100;
    TEST_EQ(abs_num1_minus_num2_int, num1, num2, 90);

    num1 = 10;
    num2 = 10;
    TEST_EQ(abs_num1_minus_num2_int, num1, num2, 0);

    num1 = INT_MAX;
    num2 = 1;
    TEST_EQ(abs_num1_minus_num2_int, num1, num2, 2147483646);

    num1 = 1;
    num2 = INT_MAX;
    TEST_EQ(abs_num1_minus_num2_int, num1, num2, 2147483646);


    return 0;
}

Sample run and output:

eRCaGuy_hello_world/c$ ./absolute_value_of_num1_minus_num2.c
Absolute difference tests.

INT8_MIN = -128, INT8_MAX = 127
num1 =   -7 (249); num2 =   -4 (252); num1-num2=  3;  Passed
num1 = -128 (128); num2 =  127 (127); num1-num2=255;  Passed
num1 =  127 (127); num2 = -128 (128); num1-num2=255;  Passed
num1 =  100 (100); num2 =   10 ( 10); num1-num2= 90;  Passed
num1 =   10 ( 10); num2 =  100 (100); num1-num2= 90;  Passed
num1 =   10 ( 10); num2 =   10 ( 10); num1-num2=  0;  Passed
num1 =  127 (127); num2 =    1 (  1); num1-num2=126;  Passed
num1 =    1 (  1); num2 =  127 (127); num1-num2=126;  Passed

INT_MIN = -2147483648, INT_MAX = 2147483647
num1 =          -7 (4294967289); num2 =          -4 (4294967292); num1-num2=         3;  Passed
num1 = -2147483648 (2147483648); num2 =  2147483647 (2147483647); num1-num2=4294967295;  Passed
num1 =  2147483647 (2147483647); num2 = -2147483648 (2147483648); num1-num2=4294967295;  Passed
num1 =         100 (       100); num2 =          10 (        10); num1-num2=        90;  Passed
num1 =          10 (        10); num2 =         100 (       100); num1-num2=        90;  Passed
num1 =          10 (        10); num2 =          10 (        10); num1-num2=         0;  Passed
num1 =  2147483647 (2147483647); num2 =           1 (         1); num1-num2=2147483646;  Passed
num1 =           1 (         1); num2 =  2147483647 (2147483647); num1-num2=2147483646;  Passed

Adjacently related

  1. The "absolute subtraction" above reminds me of the "rounding divide" set of solutions you can do with integer math too. For that, see my other answer here: Rounding integer division (instead of truncating). I present rounding up, rounding down, and rounding to nearest when doing integer division.

See also

  1. My answer on implicit casting/promotion and Integer and floating point rank and promotion rules in C and C++
  2. https://cppinsights.io/ - a very useful tool which expands your C++ code into exactly what the compiler sees, including after applying all automatic implicit type promotion rules in the compiler.
    1. Ex: see my code above here: https://cppinsights.io/s/bfc425f6 --> then click the play button to convert and expand it into what the compiler sees.

Upvotes: 9

jCres
jCres

Reputation: 41

You can use stdint.h types, do the difference and then take the absolute value and convert to int. Something like this:

int32_t a,b,res;
...

int_least64_t diff = (int_least64_t)a - (int_least64_t)b; // int_least64_t to be sure
int_least64_t absDiff = llabs(diff);

// Finally 
res = absDiff > INT_MAX ? INT_MAX : (int32_t)absDiff;

Upvotes: 1

CPlus
CPlus

Reputation: 4848

A simple solution to this problem is to avoid overflow entirely by always subtracting the smaller one from the bigger one. This gives the expected results, even for x == INT_MIN and y == INT_MAX. The signed to unsigned conversion here is safe:

unsigned diff = x > y ? (unsigned)x-(unsigned)y : (unsigned)y-(unsigned)x;

Edit: In order for the subtraction to be guaranteed to not cause signed overflow in cases of the 'smaller' one being less than zero, the operands must be cast to unsigned.

Upvotes: 3

chux
chux

Reputation: 154169

For those who like to avoid casting, a variation on @Gabriel Staple answer.

unsigned abs_num1_minus_num2_int(int num1, int num2) {
    unsigned abs_diff = num1 > num2 ?
        0u + num1 - num2 :
        0u + num2 - num1;
    return abs_diff;
}

Note: Pedantic warnings may still arise from an int casually changing to an unsigned.

Upvotes: 0

Related Questions