我怎样才能安全地找到C中2个有符号整数之间的绝对差？

问题描述 投票：0回答：4

绝对差是两个数字之间差的绝对值。假设我有 2 个 

int
变量（
x
和 
y
），我想找到绝对差异。一个简单的解决方案是：

unsigned diff = abs(x-y);

但是，如果发生溢出，这些会调用未定义的行为并给出不正确的结果，例如 

x
是 
INT_MIN
且 
y
是 
INT_MAX
。这返回
1
（假设环绕行为）而不是预期的
UINT_MAX
。

c math difference absolute-value absolute-difference
4个回答
7
投票

好的，下面的工作。 @user16217248 让我开始了。请参阅答案下的讨论。

如何安全高效找到
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;
}

秘密是与 

signed
整数值进行 num1 > num2 三元比较，然后重新解释将它们转换为 unsigned 整数值，以便在获取 
num1 - num2
的绝对值时允许明确定义的上溢和下溢行为.

这是我的完整测试代码：

absolute_value_of_num1_minus_num2.c 来自我的 eRCaGuy_hello_world 存储库：

///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 3 in my answer here
    // (https://stackoverflow.com/a/72654668/4561887) applies, and the `>`
    // comparison, as well as subtraction, takes 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;
}

示例运行和输出：

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

相邻相关

  1. 上面的“绝对减法”让我想起了您也可以使用整数数学来实现的“舍入除法”解决方案集。为此，请参阅我的其他答案：舍入整数除法（而不是截断）。我介绍了在进行整数除法时向上舍入、向下舍入和四舍五入到最接近的值。

另请参阅

  1. 我对隐式转换/升级以及C和C++中的整数和浮点排名和升级规则的回答
  2. https://cppinsights.io/ - 一个非常有用的工具，可将您的 C++ 代码扩展为编译器所看到的内容，包括在编译器中应用所有自动隐式类型提升规则之后。
    1. 例如：请参阅上面的代码：https://cppinsights.io/s/bfc425f6 --> 然后单击播放按钮将其转换并展开为编译器所看到的内容。
3
投票

此问题的一个简单解决方案是通过始终从较大的值中减去较小的值来完全避免溢出。即使对于 

x == INT_MIN
和 
y == INT_MAX
，这也给出了预期的结果。这里的 
signed
到 
unsigned
的转换是 安全:

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

编辑：为了保证减法在“较小”的值小于零的情况下不会导致有符号溢出，操作数必须转换为无符号。

1
投票

您可以使用 stdint.h 类型，进行差异，然后取绝对值并转换为 int。 像这样的东西：

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;
0
投票

对于那些不想选角的人，请使用 @Gabriel Staple 答案的变体。

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

注意： 

int
随意更改为 
unsigned
，仍可能会出现迂腐警告。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.