103

as 引数を取り、合同モジュロ UINT_MAX+1 をunsigned int引数に返す関数を定義したいと考えています。int

最初の試行は次のようになります。

int unsigned_to_signed(unsigned n)
{
    return static_cast<int>(n);
}

しかし、どの言語弁護士も知っているように、INT_MAX より大きい値の unsigned から signed へのキャストは実装定義です。

(a) 仕様で義務付けられている動作のみに依存するようにこれを実装したいと考えています。（b）最新のマシンと最適化コンパイラでノーオペレーションにコンパイルされます。

奇妙なマシンについては... unsigned int に対する unsigned int 合同法 UINT_MAX+1 がない場合、例外をスローしたいとしましょう。複数ある場合 (これが可能かどうかはわかりません)、最大のものが欲しいとしましょう。

OK、2 回目の試行:

int unsigned_to_signed(unsigned n)
{
    int int_n = static_cast<int>(n);

    if (n == static_cast<unsigned>(int_n))
        return int_n;

    // else do something long and complicated
}

典型的な 2 の補数システムを使用していないときは、効率はあまり気にしません。そして、私のコードが 2050 年のどこにでもあるサインマグニチュード システムのボトルネックになったとしても、誰かがそれを見つけて最適化できるに違いありません。

さて、この 2 回目の試行は、私が望むものにかなり近いものです。一部の入力については、へのキャストintは実装定義ですが、へのキャスト バックunsignedは、モジュロ UINT_MAX+1 の値を保持することが標準によって保証されています。したがって、条件は私が望むものを正確にチェックし、遭遇する可能性のあるシステムでは何もコンパイルしません。

ただし...int実装定義の動作を呼び出すかどうかを最初に確認せずに、まだキャストしています。2050 年の仮想システムでは、誰が何を知っているかがわかります。だから私はそれを避けたいとしましょう。

質問: 「3 回目の試行」はどのように表示されますか?

要約すると、次のことを行います。

  • unsigned int から signed int へのキャスト
  • 値 mod UINT_MAX+1 を保持します
  • 標準で義務付けられた動作のみを呼び出す
  • 最適化コンパイラを使用して、典型的な 2 の補数のマシンでノーオペレーションにコンパイルします。

[アップデート]

これが些細な質問ではない理由を示す例を挙げましょう。

次のプロパティを持つ架空の C++ 実装を検討してください。

  • sizeof(int)4に等しい
  • sizeof(unsigned)4に等しい
  • INT_MAX32767 に等しい
  • INT_MIN-2 32 + 32768に等しい
  • UINT_MAX2 32 - 1に等しい
  • の算術演算intは 2 32を法として( ～ の範囲INT_MINにINT_MAX)
  • std::numeric_limits<int>::is_modulo本当です
  • unsignednを int にキャストすると、0 <= n <= 32767 の値が保持され、それ以外の場合はゼロになります。

この仮想的な実装では、int各値に一致する値 (mod UINT_MAX+1) が 1つだけありunsignedます。したがって、私の質問は明確に定義されます。

この架空の C++ 実装は、C++98、C++03、および C++11 の仕様に完全に準拠していると主張します。私はそれらすべての単語をすべて覚えていないことを認めます...しかし、関連するセクションを注意深く読んだと思います。したがって、私にあなたの答えを受け入れてもらいたい場合は、(a) この架空の実装を除外する仕様を引用するか、(b) 正しく処理する必要があります。

実際、正解は、標準で許可されているすべての仮想実装を処理する必要があります。それが、定義上、「標準で義務付けられた動作のみを呼び出す」という意味です。

std::numeric_limits<int>::is_moduloちなみに、ここでは複数の理由でまったく役に立たないことに注意してください。1 つには、trueunsigned-to-signed キャストが大きな unsigned 値に対して機能しない場合でも、可能性があります。別の例ではtrue、算術演算が整数範囲全体を単純にモジュロする場合、1 の補数または符号 - マグニチュード システムでも可能です。等々。あなたの答えが に依存しているならis_modulo、それは間違っています。

【アップデート2】

hvd の答えは私に何かを教えてくれました: 整数に対する私の架空の C++ 実装は、最新の C では許可されていません。C99および C11 標準は、符号付き整数の表現について非常に具体的です。実際、それらは 2 の補数、1 の補数、および符号の大きさのみを許可します (セクション 6.2.6.2 パラグラフ (2); )。

しかし、C++ は C ではありません。結局のところ、この事実が私の質問の核心にあるのです。

元の C++98 標準は、はるかに古い C89 に基づいていました (セクション 3.1.2.5):

符号付き整数型ごとに、対応する (ただし異なる) 符号なし整数型 (キーワード unsigned で指定) があり、同じ量のストレージ (符号情報を含む) を使用し、同じ配置要件があります。符号付き整数型の負でない値の範囲は、対応する符号なし整数型の部分範囲であり、各型の同じ値の表現は同じです。

C89 では、符号ビットが 1 つしかないことや、2 の補数/1 の補数/符号の大きさしか許可されていないことについては何も述べていません。

C++98 標準では、この言語をほぼそのまま採用しています (セクション 3.9.1 段落 (3))。

それぞれの符号付き整数型には、対応する (ただし異なる)符号なし整数型" unsigned char"、" unsigned short int"、" unsigned int"、および " unsigned long int" が存在し、それぞれが同じ量のストレージを占有し、同じアライメント要件 (3.9 ) 対応する符号付き整数型として; つまり、各符号付き整数型は、対応する符号なし整数型と同じオブジェクト表現を持ちます。符号付き整数型の負でない値の範囲は、対応する符号なし整数型の部分範囲であり、対応する各符号付き/符号なし型の値表現は同じでなければなりません。

C++03 標準は、C++11 と同様に、本質的に同一の言語を使用します。

私が知る限り、標準の C++ 仕様では、符号付き整数表現を C 仕様に制限することはできません。そして、単一の符号ビットまたはその種のものを義務付けるものは何もありません。それが言っているのは、負でない符号付き整数は対応する符号なしの部分範囲でなければならないということだけです。

したがって、ここでも、INT_MIN=-2 32 +32768を指定した INT_MAX=32767が許可されていると主張します。あなたの答えがそうでないと想定している場合、 C++標準を引用して私が間違っていることを証明しない限り、それは正しくありません。

4

8 に答える 8

79

user71404 の回答を拡張する:

int f(unsigned x)
{
    if (x <= INT_MAX)
        return static_cast<int>(x);

    if (x >= INT_MIN)
        return static_cast<int>(x - INT_MIN) + INT_MIN;

    throw x; // Or whatever else you like
}

x >= INT_MIN(昇格ルールを念頭に置いて、INT_MINに変換されますunsigned) の場合、、x - INT_MIN <= INT_MAXしたがって、これにはオーバーフローはありません。

それが明らかでない場合は、「If x >= -4u, then .」という主張を見て、少なくとも数学的な値 -INT_MIN - 1 に等しいことをx + 4 <= 3覚えておいてください。INT_MAX

最も一般的なシステム (ここで!(x <= INT_MAX)暗黙x >= INT_MINのうちに) では、オプティマイザは 2 番目のチェックを削除し、2 つのreturnステートメントを同じコードにコンパイルできることを判断し、最初のチェックも削除できるはずです (私のシステムでは可能です)。生成されたアセンブリ リスト:

__Z1fj:
LFB6:
    .cfi_startproc
    movl    4(%esp), %eax
    ret
    .cfi_endproc

あなたの質問の架空の実装:

  • INT_MAX は 32767 に等しい
  • INT_MIN は -2 32 + 32768に等しい

できないので、特に考慮する必要はありません。、または のINT_MINいずれかに等しくなります。これは、C の整数型の表現 (6.2.6.2) に従います。この表現では、ビットが値ビットであり、1 ビットが符号ビットである必要があり、1 つのトラップ表現のみが許可されます (パディング ビットのために無効な表現は含まれません)。つまり、それ以外の場合は負のゼロ / を表すものです。C++ では、C で許可されている以上の整数表現は許可されていません。-INT_MAX-INT_MAX - 1n-INT_MAX - 1

更新: Microsoft のコンパイラは明らかにそれを認識せずx > 10をx >= 11テストします。x >= INT_MINが に置き換えられた場合にのみ、必要なコードを生成します(このプラットフォームでは)x > INT_MIN - 1uの否定として検出できますx <= INT_MAX

[質問者 (Nemo) からの更新、以下の議論について詳述]

私は今、この答えがすべての場合に機能すると信じていますが、複雑な理由があります。私はこのソリューションに賞金を授与する可能性が高いですが、誰かが気にかけている場合に備えて、すべての悲惨な詳細をキャプチャしたいと思います.

C++11 のセクション 18.3.3 から始めましょう。

表 31 では、ヘッダーについて説明し<climits>ます。

...

内容は、標準 C ライブラリのヘッダーと同じ<limits.h>です。

ここで、「標準 C」とは C99 を意味し、その仕様は符号付き整数の表現を厳しく制限しています。それらは符号なし整数に似ていますが、「符号」専用の 1 ビットと「パディング」専用の 0 個以上のビットがあります。パディング ビットは整数の値には寄与せず、符号ビットは 2 の補数、1 の補数、または符号の大きさとしてのみ寄与します。

C++11<climits>は C99 からマクロを継承しているため、INT_MIN は -INT_MAX または -INT_MAX-1 のいずれかであり、hvd のコードは動作することが保証されています。(パディングのため、INT_MAX は UINT_MAX/2 よりもはるかに小さくなる可能性があることに注意してください...ただし、signed->unsigned キャストの仕組みのおかげで、この回答はそれをうまく処理します。)

C++03/C++98 はよりトリッキーです。「標準 C」から継承するために同じ言葉遣いを使用します<climits>が、現在「標準 C」は C89/C90 を意味します。

これらすべて -- C++98、C++03、C89/C90 -- には、質問で指定した文言がありますが、これも含めます (C++03 セクション 3.9.1 パラグラフ 7):

整数型の表現は、純粋な 2 進数システムを使用して値を定義する必要があります。

脚注 (44) では、「純粋な 2 進数システム」を定義しています。

2 進数の 0 と 1 を使用する整数の位置表現。連続するビットで表される値は加法的であり、1 で始まり、2 の連続する整数乗で乗算されます。ただし、おそらく最高位のビットは除きます。

この言い回しの興味深い点は、それ自体が矛盾していることです。「純粋な 2 進数システム」の定義では、符号/大きさの表現が許可されていないからです。上位ビットの値を -2 n-1 (2 の補数) または -(2 n-1 -1) (1 の補数) にすることはできます。ただし、符号/大きさになる上位ビットの値はありません。

とにかく、私の「仮想実装」は、この定義では「純粋なバイナリ」とは見なされないため、除外されます。

ただし、上位ビットが特別であるという事実は、それが任意の値に寄与していると想像できることを意味します: 小さな正の値、大きな正の値、小さな負の値、または大きな負の値。(符号ビットが -(2 n-1 -1) に寄与できる場合、なぜ -(2 n-1 -2) に寄​​与しないのでしょうか? など)

それでは、奇抜な値を「符号」ビットに割り当てる符号付き整数表現を想像してみましょう。

符号ビットの小さな正の値は正の範囲int(おそらく と同じ大きさunsigned) になり、hvd のコードはそれを問題なく処理します。

符号ビットに大きな正の値を指定するintと、最大値が よりも大きくなりますがunsigned、これは禁止されています。

符号ビットに大きな負の値を指定するintと、連続しない値の範囲を表すことになり、仕様の他の表現ではそれが規定されています。

最後に、小さな負の量に寄与する符号ビットはどうでしょうか? 「符号ビット」の 1 を int の値に、たとえば -37 に寄与させることはできますか? では、INT_MAX は (たとえば) 2 31 -1 になり、INT_MIN は -37 になりますか?

これにより、いくつかの数値が 2 つの表現を持つことになります...しかし、1 の補数は 2 つの表現をゼロに与え、それは「例」に従って許可されます。2 つの表現を持つ可能性がある唯一の整数はゼロであると仕様はどこにも述べていません。したがって、この新しい仮説は仕様で許可されていると思います。

実際、-1 から までの負の値-INT_MAX-1は「符号ビット」の値として許容されるように見えますが、それより小さい値はありません (範囲が不連続にならないように)。言い換えると、～-1のいずれINT_MINかになる可能性があります。-INT_MAX-1

さて、何を推測しますか？hvd のコードの 2 番目のキャストが実装定義の動作を回避するために必要なのは、x - (unsigned)INT_MIN以下の値だけですINT_MAX。今示したINT_MINのは、少なくとも-INT_MAX-1です。明らかに、xせいぜいUINT_MAXです。負の数を unsigned にキャストすることは、 を追加することと同じUINT_MAX+1です。すべてをまとめる：

x - (unsigned)INT_MIN <= INT_MAX

場合に限り

UINT_MAX - (INT_MIN + UINT_MAX + 1) <= INT_MAX
-INT_MIN-1 <= INT_MAX
-INT_MIN <= INT_MAX+1
INT_MIN >= -INT_MAX-1

最後の例は先ほど示したものなので、このひねくれたケースでも、コードは実際に機能します。

それはすべての可能性を使い果たし、この非常に学術的な演習を終了します.

結論: C89/C90 の符号付き整数の動作は、C++98/C++03 に継承されており、非常に仕様が不十分です。C99で修正されており、C++11<limits.h>はC99から組み込むことで間接的に修正を継承しています。しかし、C++11 でさえ、自己矛盾する「純粋なバイナリ表現」という表現を保持しています...

于 2012-11-03T11:39:30.497 に答える
19

このコードは、仕様で義務付けられている動作のみに依存しているため、要件 (a) は簡単に満たされます。

int unsigned_to_signed(unsigned n)
{
  int result = INT_MAX;

  if (n > INT_MAX && n < INT_MIN)
    throw runtime_error("no signed int for this number");

  for (unsigned i = INT_MAX; i != n; --i)
    --result;

  return result;
}

要件 (b) ではそれほど簡単ではありません。これは、gcc 4.6.3 (-Os、-O2、-O3) および clang 3.0 (-Os、-O、-O2、-O3) ではノーオペレーションにコンパイルされます。Intel 12.1.0 はこれを最適化することを拒否します。また、Visual C に関する情報はありません。

于 2012-11-03T17:34:40.287 に答える
3

やりたいことをコンパイラに明示的に伝えることができます。

int unsigned_to_signed(unsigned n) {
  if (n > INT_MAX) {
    if (n <= UINT_MAX + INT_MIN) {
      throw "no result";
    }
    return static_cast<int>(n + INT_MIN) - (UINT_MAX + INT_MIN + 1);
  } else {
    return static_cast<int>(n);
  }
}

gcc 4.7.2for x86_64-linux( g++ -O -S test.cpp) toでコンパイル

_Z18unsigned_to_signedj:
    movl    %edi, %eax
    ret
于 2012-11-03T07:29:21.637 に答える
2

私xたちの入力は...

の場合、 < <のようなx > INT_MAX定数を見つけたいと考えています。k0x - k*INT_MAXINT_MAX

これは簡単です -- unsigned int k = x / INT_MAX;. 次に、みましょうunsigned int x2 = x - k*INT_MAX;

安全にキャストできるようx2になりました。intさせてint x3 = static_cast<int>(x2);

UINT_MAX - k * INT_MAX + 1からx3、ifのようなものを引きたいと思いk > 0ます。

さて、2 の補数システムでは、 である限りx > INT_MAX、これは次のように機能します。

unsigned int k = x / INT_MAX;
x -= k*INT_MAX;
int r = int(x);
r += k*INT_MAX;
r -= UINT_MAX+1;

C++ ではゼロが保証されていることに注意してくださいUINT_MAX+1。int への変換は失敗であり、減算k*INT_MAXしてから「同じ値」に加算し直しました。したがって、受け入れ可能なオプティマイザーは、そのばかげたことをすべて消去できるはずです!

それは問題を残すx > INT_MAXかどうかです。さて、2 つのブランチを作成します。1 つはx > INT_MAXあり、もう 1 つはなしです。ないものは、コンパイラがヌープに最適化するストレートキャストを行います。... を持つものは、オプティマイザーが完了した後に noop を実行します。スマート オプティマイザーは両方の分岐を同じものに認識し、分岐をドロップします。

問題:UINT_MAXが に比べて非常に大きい場合INT_MAX、上記は機能しない可能性があります。私はk*INT_MAX <= UINT_MAX+1暗黙のうちにそれを仮定しています。

おそらく、次のようないくつかの列挙型でこれを攻撃できます。

enum { divisor = UINT_MAX/INT_MAX, remainder = UINT_MAX-divisor*INT_MAX };

これは、2 の補数システムで 2 と 1 になると私は信じています (その数学が機能することが保証されていますか? それはトリッキーです...)、これらに基づいてロジックを実行し、非 2 の補数システムで簡単に最適化します...

これにより、例外ケースも開かれます。UINT_MAX が (INT_MIN-INT_MAX) よりもはるかに大きい場合にのみ可能であるため、例外コードを if ブロックに配置して、何らかの方法で正確にその質問をすることができ、従来のシステムで速度が低下することはありません。

それを正しく処理するためにこれらのコンパイル時定数を構築する方法が正確にはわかりません。

于 2012-10-31T03:26:47.383 に答える
1

int型は少なくとも2バイトだと思うので、INT_MINとINT_MAXはプラットフォームによって異なる可能性があります。

基本的なタイプ

≤climits≥ヘッダー

于 2012-11-06T01:33:52.110 に答える
1

std::numeric_limits<int>::is_moduloコンパイル時定数です。テンプレートの特殊化に使用できます。少なくともコンパイラがインライン化と一緒に機能する場合、問題は解決しました。

#include <limits>
#include <stdexcept>
#include <string>

#ifdef TESTING_SF
    bool const testing_sf = true;
#else
    bool const testing_sf = false;
#endif

// C++ "extensions"
namespace cppx {
    using std::runtime_error;
    using std::string;

    inline bool hopefully( bool const c ) { return c; }
    inline bool throw_x( string const& s ) { throw runtime_error( s ); }

}  // namespace cppx

// C++ "portability perversions"
namespace cppp {
    using cppx::hopefully;
    using cppx::throw_x;
    using std::numeric_limits;

    namespace detail {
        template< bool isTwosComplement >
        int signed_from( unsigned const n )
        {
            if( n <= unsigned( numeric_limits<int>::max() ) )
            {
                return static_cast<int>( n );
            }

            unsigned const u_max = unsigned( -1 );
            unsigned const u_half = u_max/2 + 1;

            if( n == u_half )
            {
                throw_x( "signed_from: unsupported value (negative max)" );
            }

            int const i_quarter = static_cast<int>( u_half/2 );
            int const int_n1 = static_cast<int>( n - u_half );
            int const int_n2 = int_n1 - i_quarter;
            int const int_n3 = int_n2 - i_quarter;

            hopefully( n == static_cast<unsigned>( int_n3 ) )
                || throw_x( "signed_from: range error" );

            return int_n3;
        }

        template<>
        inline int signed_from<true>( unsigned const n )
        {
            return static_cast<int>( n );
        }
    }    // namespace detail

    inline int signed_from( unsigned const n )
    {
        bool const is_modulo = numeric_limits< int >::is_modulo;
        return detail::signed_from< is_modulo && !testing_sf >( n );
    }
}    // namespace cppp

#include <iostream>
using namespace std;
int main()
{
    int const x = cppp::signed_from( -42u );
    wcout << x << endl;
}

編集: modular-int 以外のマシンでのトラップの可能性を回避するためにコードを修正しました (1 つだけが存在することが知られています。つまり、Unisys Clearpath の古風に構成されたバージョンです)。簡単にするために、これは値 -2 n -1をサポートしないことによって行われます。ここで、nはそのintようなマシン (つまり、クリアパス) では値のビット数です。実際には、この値はマシンでもサポートされません (つまり、符号と大きさまたは 1 の補数表現)。

于 2012-10-31T03:30:08.230 に答える