两个有符号数之间的距离

Question

两个数字之间的距离通常是这样计算的：

long distance(long x, long y)
{
     return x > y ? x - y : y - x;
}

然而，对于带符号的 x 和 y，这些减法可能会溢出，因此该函数可以在 C 和 C++ 中调用未定义的行为。

解决该问题的一种方法是使用无符号类型来表示结果距离。距离不能为负，因此不需要带符号的类型。有符号类型的最小值和最大值之间的距离应适合相同大小的无符号类型。（编辑： 正如 chux 回答的那样，这不是完全正确的假设。）所以我确实像这样修改了第一个函数：

unsigned long distance(long x, long y)
{
    return (x > y) ? (unsigned long)x - (unsigned long)y
                   : (unsigned long)y - (unsigned long)x;
}

它现在能以符合标准且可移植的方式正确计算两个有符号长整数之间的距离吗？如果没有，修复方法是什么？

Answer 1

由于 C 和 C++ 明确定义了无符号溢出（和下溢），因此当使用 2 的补码算法时，您修改后的函数完全没问题。

Answer 2

Does it now correctly calculate the distance between two signed longs in standard conforming and portable manner?

是的。

罕见的例外¹ 必须使用更宽的类型。

考虑 x > y

的 3 种情况

x >= 0, y >= 0

以下是正确的，因为转换没有改变 value.

(unsigned long)x - (unsigned long)y

x < 0, y < 0

由于 (unsigned long)，x,y 值都增加了 ULONG_MAX + 1，减法抵消了它。

// is akin to 
((unsigned long)(x + ULONG_MAX + 1) - (unsigned long)(y + ULONG_MAX + 1))
// or
x - y // with unsigned math.

x >= 0, y < 0

(unsigned long)y有y + ULONG_MAX + 1的价值，比x多。（假设ULONG_MAX/2 >= LONG_MAX¹）差值为负。然而 unsigned 数学环绕，并加回 ULONG_MAX + 1.

// is akin to 
((unsigned long)x - (unsigned long)(y + ULONG_MAX + 1)) + (ULONG_MAX + 1).
// or
x - y // with unsigned math.

x < 0, y >= 0

这种情况不可能，因为 x > y。

¹：C 没有指定 ULONG_MAX/2 == LONG_MAX，尽管这非常常见。很久以前我只遇到过一次它不适用的地方。在那种情况下，它是 ULONG_MAX == LONG_MAX。 ULONG_MAX/2 == LONG_MAX 如此受欢迎，以至于我怀疑现代平台会冒着不这样做的风险。 C 确实指定了 ULONG_MAX >= LONG_MAX.

The range of nonnegative values of a signed integer type is a subrange of the corresponding unsigned integer type, and the representation of the same value in each type is the same. ... C11dr §6.2.5 9

代码可以使用下面的代码来检测这些稀有平台。

#if ULONG_MAX/2 < LONG_MAX
  #error `unsigned long` too narrow.  Need new approach.
#endif

Answer 3

假设 sizeof(unsigned long long) > sizeof(unsigned long) 可以安全地将其声明为：unsigned long long distance(long x, long y)

但是因为如今 ones complement 或其他奇异的格式数字不常用（实际上，任何人都不太可能有机会在这样的机器上编写 C 代码）unsigned long 类型可以容纳所有可能的距离。

两个有符号数之间的距离

distance between two signed numbers

c

c++

distance

language-lawyer