27

これを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;
}

これはささいなことのように聞こえるかもしれませんが、2つの数値の違いを理解するためだけに、私には多くのように思えます。これは実際に物事を行うための完全に合理的な方法であり、私は不必要に衒学者であるのですか、それとも私のスパイダーマンは正当な理由でうずきますか?

4

5 に答える 5

54

差の絶対値を取得するだけです。

#include <cstdlib>
int diff = std::abs(x-y);
于 2012-05-14T19:10:50.580 に答える
31

std::abs()ここで他の人が示唆しているように、関数を使用することはこれを行うための1つの明確な方法です。

しかし、おそらくあなたはライブラリ呼び出しなしでこの関数を簡潔に書くことに興味があります。

その場合

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

短い方法です。

あなたのコメントで、あなたはスピードに興味があることを提案しました。その場合、分岐を必要としないこの操作を実行する方法に興味があるかもしれません。このリンクはいくつかを説明しています。

于 2012-05-14T19:17:12.047 に答える
13
#include <cstdlib>

int main()
{
    int x = 7;
    int y = 3;
    int diff = std::abs(x-y);
}
于 2012-05-14T19:09:41.990 に答える
2

まあそれはあなたが最短で何を意味するかに依存します。最速のランタイム、最速のコンパイル、最小の行数、最小のメモリ量。私はあなたが実行時間を意味すると仮定します。

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

これは2つの比較と1つの操作を行います(これは避けられませんが、特定の場合の特定のビット単位の操作によって最適化できますが、コンパイラーが実際にこれを行う場合があります)。また、コンパイラが十分に賢い場合は、1つの比較のみを実行し、他の比較のために結果を保存できます。たとえば、X> Yの場合、最初の比較からY <Xであることがわかりますが、コンパイラがこれを利用しているかどうかはわかりません。

于 2013-10-07T12:14:15.773 に答える
2

既存のすべての回答は極端な入力でオーバーフローし、未定義の動作を与えます。@craqはコメントでこれを指摘しました。

値が狭い範囲内にあることがわかっている場合は、他の回答が示すように行うのが良いかもしれませんが、極端な入力を処理する(つまり、可能な入力値を堅牢に処理する)には、単純に値を減算してから適用することはできません。std::abs働き。craqが正しく指摘しているように、減算がオーバーフローして未定義の動作を引き起こす可能性があり(consider INT_MIN - 1)、std::abs呼び出しによっても未定義の動作が発生する可能性があります(consider std::abs(INT_MIN))。ペアの最小値と最大値を決定してから減算を実行するのは良いことではありません。

より一般的には、asigned intは2つの値の最大差を表すことができませんsigned intunsigned intタイプは出力値に使用する必要があります。

3つの解決策があります。ここから、明示的なサイズの整数型を使用して、とが同じサイズと範囲であるstdint.hかどうかなどの不確実性についてドアを閉めました。longint

解決策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;
}
于 2020-05-10T11:31:17.203 に答える