[解決済み] 実装依存の挙動を回避した効率的な符号なし→符号ありキャスト

質問

を受け取る関数を定義したい。 unsigned int を引数として取り int を引数にとり、UINT_MAX+1のモジュロで合同となる。

最初の試みは次のようなものです。

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

しかし、言語専門家なら誰でも知っているように、INT_MAXより大きな値に対する符号なしから符号ありへのキャストは、実装で定義されています。

私はこれを、(a) 仕様によって義務付けられた動作にのみ依存し、(b) 最新のマシンと最適化コンパイラーでは何もせずにコンパイルできるように実装したいと思います。

奇妙なマシンに関しては... UINT_MAX+1 のモジュロを持つ符号付き int が符号なし int に一致しない場合、私が例外をスローしたいとします。 複数ある場合 (これが可能かどうかは分かりませんが)、最大のものが欲しいとします。

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度目の正直はどのようなものでしょうか？

要約すると、私は

• 符号なしintから符号ありintへのキャスト
• mod UINT_MAX+1 の値を保持します。
• 標準的に要求される動作のみを呼び出す
• 最適化コンパイラを搭載した典型的な 2 補数マシン上では no-op にコンパイルされます。

[アップデート］

なぜこれが些細な質問でないかを示すために、例を挙げてみましょう。

以下のプロパティを持つ仮想的なC++の実装を考えてみましょう。

• sizeof(int) イコール 4
• sizeof(unsigned) は 4 に等しい
• INT_MAX は32767に等しい
• INT_MIN イコール -2 ³² + 32768
• UINT_MAX は2に等しい ³² - 1
• 算術演算 int はモジュロ2 ³² (範囲に INT_MIN を経て INT_MAX )
• std::numeric_limits<int>::is_modulo は真
• 符号なしをキャストする n をintにキャストすると、0 <= n <= 32767の値が保持され、次のようになります。 ゼロ そうでなければ

この仮想的な実装では、ちょうど1つの int に一致する (mod UINT_MAX+1) 値があります。 unsigned の値と合同です。 だから、私の質問はよく定義されているでしょう。

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

確かに、正しい答えは すべての を処理しなければなりません。それが、定義上、quot;invoke only standard-mandated behavior"が意味するものです。

ちなみに、以下の点に注意してください。 std::numeric_limits<int>::is_modulo は、複数の理由から、ここでは全く役に立たないことに注意してください。 ひとつには、それは true であっても、符号なしから符号ありへのキャストは大きな符号なし値ではうまくいきません。 もうひとつは、これは true であっても、演算が単純に整数範囲全体をモジュロするものであれば、1 つの補数または符号振幅システム上であっても などなど。 もしあなたの答えが is_modulo であれば、間違っています。

[更新2】です。］

hvdの回答 は私に何かを教えてくれました。私の仮想的な整数のC++実装は ではなく C99 と C11 標準は符号付き整数の表現について非常に具体的であり、実際、それらは 2 補数、1 補数、および符号付き整数（セクション 6.2.6.2 パラグラフ (2); ）のみを許可しています。

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

オリジナルのC++98標準は、はるかに古いC89に基づいており、そこには次のように書かれています（3.1.2.5項）。

符号付き整数型のそれぞれについて、対応する（しかし異なる）符号なし整数型が存在する。 キーワード「unsigned」で指定される）符号なし整数の型があります。 符号情報を含む）同じ量のストレージを使用し、同じアラインメント要件を持つ、対応する（しかし異なる）符号なし整数型（キーワードunsignedで指定）があります。 を含む)を使用し、同じアラインメント要件を持っています。 符号付き整数型の非負値の範囲は 符号付き整数型の負でない値の範囲は，対応する符号なし整数型の部分範囲です。 の部分範囲であり，それぞれの型の同じ値の表現は同じです。 それぞれの型における同じ値の表現は同じです。

C89では、符号ビットを1つだけ持つことや、twos-complement/ones-complement/sign-magnitudeのみを許可することについては何も述べていません。

C++98標準はこの言語をほぼそのまま採用しました（3.9.1項（3）項）。

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

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

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

ということで、再びINT_MAX=32767でINT_MIN=-2であると主張します。 ³² +32768 は許可されています。 もしあなたの答えがそうでないと仮定しているならば、あなたが C++ 標準は私が間違っていることを証明する。

どのように解決するのですか？

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 となるので、オーバーフローすることはありません。

もしこれが明白でないなら、クレームを見てみましょう "もし x >= -4u であれば x + 4 <= 3 ."であることに留意してください。 INT_MAX は少なくとも数学的な値である -INT_MIN - 1 と等しくなることに留意してください。

最も一般的なシステムで !(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 に等しい ³² + 32768

は不可能なので、特に考慮する必要はありません。 INT_MIN はどちらかというと -INT_MAX または -INT_MAX - 1 . これは，C言語の整数型の表現(6.2.6.2)からも言えることで，整数型の表現には n ビットを値ビット、1ビットを符号ビットとし、1つのシングルトラップ表現（パディングビットのために無効な表現を含まない）、すなわち、そうでなければ負のゼロを表現するものだけを許可しています />。 -INT_MAX - 1 . C++はCが許容する以上の整数表現を許容しません。

更新 : マイクロソフトのコンパイラは、どうやら x > 10 と x >= 11 は同じことをテストします。これは、もし x >= INT_MIN が x > INT_MIN - 1u の否定として検出することができます。 x <= INT_MAX (の否定として検出することができます（このプラットフォームでは）。

[質問者（ネモ）からの更新、以下の私たちの議論を詳しく説明する】。］

私は今、この回答がすべてのケースで機能すると信じていますが、複雑な理由があります。 私はこの解決策に賞金を授与する可能性がありますが、誰かが気になる場合に備えて、すべての複雑な詳細を記録しておきたいと思います。

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

表 31 では、ヘッダー <climits> .

...

内容は標準Cライブラリのヘッダと同じである <limits.h> .

ここで、quot;Standard C" とは C99 のことで、その仕様は符号付き整数の表現に厳しい制約を課しています。 符号なし整数と同じですが、符号専用のビットが1つ、パディング専用のビットが0つまたはそれ以上あります。 パディングビットは整数の値には寄与せず、符号ビットは2補数、1補数、符号倍数としてのみ寄与します。

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

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

これらすべて -- C++98、C++03、C89/C90 -- には、私の質問であげた文言がありますが、これ（C++03 セクション 3.9.1 パラグラフ 7）も含まれています。

<ブロッククオート

積分型の表現は，純粋な二進法を使って値を定義しなければならない。 純粋な二進法で値を定義しなければならない(44) [ ]。 例 この国際規格では 2の補数、1の補数、符号付の大きさの表現が可能です。 表現が可能です。］

脚注(44)では、"pure binary numeration system"を定義しています。

<ブロッククオート

2進数の0と1を用いた整数の位置表現。 と1という2進数を使って表現する整数の位置表現で、連続するビットが表現する値は 1から始まり、連続する整数倍されます。 2の累乗を乗じたものです。

この表現で興味深いのは、それ自体が矛盾していることです。なぜなら、quot;pure binary numeration system" の定義では、符号/倍数表現を許可していないからです! しかし、上位ビットが例えば値 -2 を持つことは許可しています。 ^n-1 (2進数の補数) または -(2 ^n-1 -1) (1の補数)です。 しかし、符号/大きさになる上位ビットの値はありません。

とにかく、私の "hypothetical implementation" は、この定義の下では "pure binary" として適格ではないので、除外されます。

しかし、上位ビットが特別であるという事実は、それがどんな値でも貢献することを想像できることを意味します。小さな正の値、巨大な正の値、小さな負の値、または巨大な負の値です。 (もし、符号ビットが -(2 ^n-1 -1)に貢献できるのであれば、なぜ-(2 ^n-1 -2)ではないのか、など)

そこで、"sign"ビットにおかしな値を割り当てる符号付き整数表現を想像してみましょう。

符号ビットに小さな正の値を指定すると、正の範囲の int (と同じ大きさになる可能性があります。 unsigned を含む)、hvd のコードはそれをうまく処理します。

符号ビットに巨大な正の値を指定すると int よりも大きい最大値を持つことになります。 unsigned よりも大きい最大値を持つことは禁じられています。

符号ビットに巨大な負の値を指定すると、結果として int は連続しない値の範囲を表すことになり、仕様の他の文言はそれを除外しています。

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

これはいくつかの数字が2つの表現を持つことになります...。 しかし、ones-complementは0に2つの表現を与え、それは"Example"に従って許可されています。 仕様ではどこにも、ゼロが だけ ゼロが 2 つの表現を持つ可能性のある唯一の整数であるとは、仕様には書かれていません。 ですから、この新しい仮説は仕様によって許可されていると思います。

確かに、-1から下はどんな負の値でも -INT_MAX-1 までの任意の負の値が符号ビットの値として許容されるようですが、これより小さいものはありません (範囲が非連続にならないように)。 言い換えると INT_MIN は -INT_MAX-1 から-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 でも自己矛盾した "純粋なバイナリ表現" という文言が残されています...