9

公衆衛生警告の編集-この質問には、未定義の行動に関する誤った仮定が含まれています。受け入れられた答えを参照してください。

最近のブログ投稿を読んだ後、私はすべての標準を回避することの実用性について多くのことを考えてきました-CおよびC++コードの未定義の仮定。これは、符号なし128ビット加算を行うためにC++から切り取ったスニペットです...

void c_UInt64_Pair::operator+= (const c_UInt64_Pair &p)
{
  m_Low  += p.m_Low;
  m_High += p.m_High;

  if (m_Low < p.m_Low)  m_High++;
}

これは明らかにオーバーフロー動作に関する仮定に依存しています。明らかに、ほとんどのマシンは適切な種類の2進整数をサポートできますが（おそらく32ビットチャンクなどから構築されます）、オプティマイザーがここで標準未定義の動作を悪用する可能性が高まっているようです。つまり、m_Low < p.m_Low条件が通過できる唯一の方法は、m_Low += p.m_Lowオーバーフローの場合です。これは未定義の動作であるため、オプティマイザーは、条件が常に失敗することを合法的に判断できます。その場合、このコードは単に壊れています。

したがって、問題は...

未定義の動作に依存することなく、上記の合理的に効率的なバージョンをどのように書くことができますか？

適切な64ビットのバイナリマシン整数があるが、未定義の動作を可能な限り最悪の（または不可能な）方法で常に解釈する悪意のあるコンパイラがあると想定します。また、特別な組み込み、組み込み、ライブラリなど、それを行うためのライブラリがないと仮定します。

マイナーな説明を編集 します-これはオーバーフローを検出するだけでなく、m_Lowとm_Highの両方が2 ^ 64を法とする正しい結果になるようにすることでもあります。これも、標準では定義されていません。

4

2 に答える 2

17

C ++ 1998標準、3.9.1（4）から：「符号なしで宣言された符号なし整数は、2 ^ nを法とする算術の法則に従うものとします。ここで、nは、その特定のサイズの整数の値表現のビット数です。」ここでの「整数」は、単なる。ではなく、任意の整数型を指すことに注意してくださいint。

したがって、これらが符号なし整数であると仮定すると、タイプの「UInt64」が示唆するように、これはC ++で定義された動作であり、期待どおりに機能するはずです。

于 2010-08-25T19:37:04.120 に答える
0

実際に効率的な方法が必要な場合は、CまたはC++以外でコーディングする必要があります。適度に効率的にするには、オーバーフローが発生しないようにし、オーバーフローが発生したときにそれを検出して補正する必要があります。

基本的に、64ビットコンポーネントごとに、下位63ビットと上位ビットを使用して加算を個別に計算する必要があります。これらの個別の計算から、64ビットの合計が何であるか、およびキャリーがあったかどうかを判断できます。

次に、上位64ビットの加算を行うときに、キャリーがある場合はそれを加算します。その結果としてキャリーが発生した場合は、128ビット変数がオーバーフローしているため、例外をトリガーするか、ケースを処理する必要があります。

于 2010-08-25T19:36:40.493 に答える