c - 大きな数とオーバーフローの処理

Question

N 要素の配列が与えられ、0 から P の範囲の値の合計が P+1 から N-1 の範囲の値の合計に等しい、この配列内のインデックス P を見つける必要があります。

配列内の各要素の値の範囲は -2147483648 ～ 2147483647 で、N は最大 10000000 です。

これを考えると、各値を追加してインデックス P を見つけるときにオーバーフローがないようにするにはどうすればよいですか?

Answer 1

最悪のシナリオでは、P+1 = N-1 です。ynumber の最大値は、単一の数値に対して 2147483647 または -2147483647 しかないため、最悪の場合、P は long の最大値または最小値になることを意味します。それ以外の場合、P は長整数のままです。このため、最悪のシナリオでのみ long を使用する必要があります (最悪のケースで予想される結果が、単一の数値が long になる可能性のある最大の数値が P である場合)。

それより大きいものを使用する必要がないことを確認するには、負の値と正の値を組み合わせて、long のオーバーフローを超えないようにします。

ab と c の 3 つの数字があるとします。a + b が long データ型をオーバーフローする場合、c が P ではないことがわかります。

ここで、a + b + c = d (d が P であることを意味する) となる 4 つの数値 a、b、c、d があると想像してください。a + b が長くオーバーフローする場合、1) c は P にならない 2) そこにあることを意味します。 long のデータ型がオーバーフローする必要がないように、a + b + c を組み合わせたものです。

たとえば、a が最大長、b が最大長、c が最小長、d が 0 の場合、a + c + b = d は、long より大きいデータ型を使用しないための演算の正しい組み合わせになります。 a + c を試すことができます。これは、a + b が P の可能な最大値より長くオーバーフローするため、c が P になり得ないことがわかっているためです。