计算两个数字之间差异的最短方法？

Question

我将在C++中这样做,但我不得不用几种语言来做,这是一个相当普遍和简单的问题,这是最后一次.我已经足够像我一样对它进行编码了,我确信必须有一个更好的方法,所以在我用另一种语言写出相同的长卷曲方法之前我在这里发帖;

考虑下面代码的(百合!);

// 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;
}

这可能听起来很小,但这对我来说似乎很重要,只是为了得到两个数字之间的区别.这实际上是一种完全合理的做事方式,我是不必要的迂腐,还是我的狡猾感觉有充分的理由刺痛？

Answer 1

只需获得差异的绝对值:

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

Answer 2

std::abs()正如其他人在此提出的那样,使用该功能是一种明确的方法.

但也许你有兴趣在没有库调用的情况下简洁地编写这个函数.

在这种情况下

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

是一个简短的方法.

在您的评论中,您建议您对速度感兴趣.在这种情况下,您可能对执行此操作的方法感兴趣,而不需要分支.这个链接描述了一些.

Answer 3

#include <cstdlib>

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

Answer 4

所有现有的答案都会在极端输入上溢出，从而给出未定义的行为。@craq 在评论中指出了这一点。

如果您知道您的值将落在一个狭窄的范围内，则可以按照其他答案的建议进行操作，但要处理极端输入（即稳健地处理任何可能的输入值），您不能简单地减去这些值，然后应用std::abs功能。正如 craq 正确指出的那样，减法可能会溢出，导致未定义的行为（考虑INT_MIN - 1），并且std::abs调用也可能导致未定义的行为（考虑std::abs(INT_MIN)）。确定该对的最小值和最大值然后执行减法并不更好。

更一般地，asigned int无法表示两个signed int值之间的最大差异。该unsigned int类型应用于输出值。

我看到 3 个解决方案。我在这里使用了明确大小的整数类型stdint.h，以消除诸如long和是否int具有相同大小和范围之类的不确定性。

解决方案1.低级方式。

// 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;
}

我尝试了一种使用来自https://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax的巧妙的变体，但现代代码生成器似乎会用这种变体生成更糟糕的代码。（我已经删除了static_assert和 评论。）

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;
}

解决方案2.简单的方法。通过使用更宽的有符号整数类型来完成工作，以避免溢出。如果输入有符号整数类型是可用的最大有符号整数类型，则无法使用此方法。

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

解决方案3.费力的方法。使用流量控制来处理不同的情况。效率可能会降低。

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;
}