ほぼ常に符号なし

ほぼ常に符号なし Dale Weiler 著 Twitter GitHub 最終更新日 2022年1月1日 符号付き整数演算の必要性は、プログラム内のほとんどの整数が負の値を示すことがないため、しばしば誤解されています。配列のインデックス付けやループの反復回数もこの概念を反映しています。符号なし整数をもっと頻繁に使用する傾向があるはずですが、それにもかかわらず、ほとんどのコードは誤って符号付き整数をほぼ排他的に選択しています。 この記事の動機の大部分はCおよびC++に適用されますが、Go、Rust、Odinなどの他の言語の例も提示し、この概念が言語の選択（例えばCおよびC++は符号付き整数のラップを未定義とする）に関係なく、算術自体に固有のものであることを確立しようと試みます。 符号なしに対する議論 符号なし整数の使用には多くの議論があります。それらがほとんど間違っていると私が考える理由を説明しましょう。 安全性に関する議論 符号なし整数の使用に対する最も典型的な議論は、オーバーフローよりもアンダーフローの方がはるかに容易であるため、よりエラーを起こしやすいというものです。このアドバイスは非常に一般的であるため、公式のGoogle C++スタイルガイドは符号なし型の使用を outright に推奨していません。後続の議論で、これらの安全性の問題がどこから来るのか、そしてそれらを回避するために、すべてを符号付きで使用するよりも理解しやすい簡単なイディオムでどのように容易に回避できるかを見ていきます。これらの議論は、安全でないコードを書き続け、使用することを奨励しているため、ほとんどの場合間違っていることもわかります。 逆順ループに関する議論 forループのカウンタが逆順にカウントする必要があり、ループ本体がカウンタがゼロの場合にも実行される必要がある場合、ほとんどのプログラマはi >= 0が常に真と評価されるため、符号なしの使用が難しいと感じるでしょう。符号なし値を符号付き値にキャストしたくなる誘惑に駆られます。例えば: for (int64_t i = int64_t(size) - 1; i >= 0; i--) { // ... } もちろん、これは幅の狭い変換であり、正当な警告を沈黙させるキャストであるため危険です。CおよびC++では、特定の大きな値が与えられると未定義の動作を呼び出し、ほとんど確実に悪用可能です。ほとんどのアプリケーションは、入力が >= 0x7ffffffffffffffff の場合にクラッシュするでしょう。 典型的な議論は、そのような値は「病的な」ものになるだろうということです。この議論は間違っているだけでなく、後で見るように、さらに危険です。この危険性は、常に符号付き整数演算を使用することの背後にある支持的な議論の1つです。 しかし、この議論は間違っています。なぜなら、int64_t は 0x7ffffffffffffffff より大きい値を決して許可しないからです。それは、その制限を超える特定の数値範囲が必要だった場合に、その問題を回避しているだけであり、その大きな値が必要で、Googleの賢明なアドバイスに従って常に符号付きを使用していた場合、あなたはさらに悪い問題を抱えることになります。なぜなら、あなたは無条件に符号付きオーバーフローを呼び出したことになるからです。CやC++のような言語では、未定義の動作を呼び出します。GoやOdinのような言語ではラップし、そのラップ動作の結果としてループ内で間違った数値範囲になります。 ここでの正しいアプローチは、CおよびC++では符号なしアンダーフローは明確に定義されており、ラップ算術の動作を教えるべきです。なぜなら、それは一般的に有用であり、逆順の反復を順方向と同じくらい簡単にできるからです。 for (size_t i = size - 1; i < size; i--) { // ... } ここでのアプローチは、size - 1から開始し、各反復でカウントダウンすることです。カウンタがゼロに達すると、デクリメントによりカウンタはアンダーフローし、符号なし型の最大可能な値にラップアラウンドします。この値はsizeよりもはるかに大きいため、条件i < sizeは偽と評価され、ループは停止します。 Rustのような言語は、デバッグビルドでは符号なしアンダーフローさえもトラップ表現にしましたが、Rangeのような特定の機能により、はるかにクリーンな構文で、アンダーフロー時の効率的なラップ動作を安全に達成できます。 for i in (0..size).rev() { // ... } このアプローチでは、キャストは不要で、サイレントバグも導入されず、「病的な」入力も正しく機能します。実際、この形式は[0, 0xffffffffffffffff)のすべての可能な値を許可し、全範囲をカバーします。size == 0の場合でもこれらのループは機能することに注意してください。なぜなら、0 - 1は符号なし型の最大可能な値を生成し、それはsize（依然として0）よりも大きいため、ループは決して実行されないからです。 2つの数値の差が負になる場合 数値の差（またはデルタ）を計算したい場合、次のように表現することがよくあります: delta = x - y; ほとんどの場合、符号は必要ないため、次のように記述・表示する傾向があります: delta = abs(x - y); ここでの議論は、y > xの場合にアンダーフローが発生するため、符号なしは危険であるということです。この議論の問題点は、コード自体がxとyの符号に関係なく間違っているため、有効ではないということです。xとyの両方に対して、符号付き整数アンダーフローを発生させる値が存在します。したがって、以前と同様に、CやC++のような言語では、符号付き整数アンダーフローは未定義であるため、無条件に未定義の動作を呼び出したことになります。 符号付き整数で差を安全に計算することは、ラップ動作をサポートする言語であっても、アンダーフローのために実際には非常に困難であることがわかります。例えばINT_MAX - INT_MINは依然として不正確になります。これを安全に行う簡単な方法はありません。これが私が現在知っている最善のテクニックです。 if ((y > 0 && x < INT_MIN + y) || (y < 0 && x > INT_MAX + y)) { // error } else { delta = abs(x - y); } しかし、符号なし整数では、delta = max(x, y) - min(x, y); と書く方がはるかに簡単です。これにより、常に絶対差が安全に得られます。個人的な好みかもしれませんが、私はこちらの方が読みやすいと思います。この式は自己文書化されているため、deltaという名前はもはや必要ありません。 符号付き算術でインデックスを計算する方が安全 上記の議論の拡張として、インデックスを計算するために、より複雑な式がある場合、それを符号付きで表現する方が安全だというものがあります。この議論は主にアンダーフローとオーバーフローの誤った直感から来ていますが、符号付きではさらに悪い形で現れます。 インデックスを計算するための最も単純な「わずかに複雑な」式の例として、区間の中間点を取り上げます: int mid = (low + high) / 2; これはほとんどの人が書く方法です。lowとhighの平均を、最も近い整数に切り捨てたものです。lowとhighの合計が2^31-1を超えると、合計は負の値にオーバーフローし、その負の値は除算されても負のままです。より大きな符号付き整数型を使用しても、合計が2^63-1を超えるのは簡単であるため、救われるわけではありません。 前の例と同様に、このコードは理想的ではありません。実際、2つの変数の中心点を安全に計算することは、ライブラリ関数の助けなしではどの言語でもほぼ不可能です。なぜなら、ラップやその他の方法では、失敗する特定の入力があるからです。 符号付きの一般的な解決策は、これを次のようなイディオムに書き直すことですが、high = INT_MAX かつ low = INT_MIN の場合は依然として失敗します。 int mid = low + (high - low) / 2; 符号なし整数に固執すると、最初に意図した明白な方法で書けると思うかもしれませんが、これにも問題があることがわかります。 size_t mid = (low + high) / 2; これは実際には機能しません。例えば、low = 0x80000000 かつ high = 0x80000002 の場合、アンダーフローして2になり、それを2で割ると1になりますが、正しい値は実際には0x80000001です。 ここで符号なしが役立つのは、これらが配列のインデックスとして使用される場合です。符号付きの動作は、ほぼ間違いなく無効なインデックスを生成し、メモリの安全性に関する問題につながります。符号なしの方法は決してそうはならず、それは維持されます。