C++で安全に絶対値を求める方法について、調べても出てこないので書いておきます。 安全に、というのは「オーバーフローなどの未定義動作を起こさず」という意味です。
#include <type_traits> #include <cstdint> template<class T, class U = std::make_unsigned_t<T>> U SafeAbs( T x ) { return x < 0 ? -static_cast<uintmax_t>(x) : x; }
解説
std::make_unsigned_t<T>
は見慣れないですが、単にT
の符号なしバージョンを持ってこれるメタ関数です。たとえば、std::make_unsigned_t<int>
はunsigned int
になります。
T
が符号付整数の場合、その絶対値はT
で表せるとは限らないので、符号なしバージョンを使わないと安全ではありません。
実際、負の数を二の補数で表現している処理系では、INT_MIN
の絶対値はint
に収まらないことが問題となります。
まず、x
が非負ならば自明にそのまま返せば問題ありません。以下、負の場合に何をやっているかを説明します。
uintmax_t
も見る機会があまりありませんが、符号なし整数のうち最も大きいものです。
-x
としてしまった瞬間にオーバーフローの危険性があるので、まずは符号なし整数に変換します。
符号なし整数に変換されるときは、負の数であれば2Nを加えると決まっています。ここで、Nはその符号なし整数(ここではuintmax_t
)のビット幅です。
次に、uintmax_t
にキャストしたものに単項負符号演算子を適用しています。符号なし整数に単項負符号演算子を適用するのは一見するとおかしなことになりそうですが、問題ありません。
このような場合、数学的な結果を2Nで割った余りが得られることに決まっています。そのため、数学的には、-(x+2N) mod 2N を計算していることと等価になり、結局-xが得られます。
最後に、なぜuintmax_t
を使っているかについて説明します。この部分は、U
でも問題なさそうに思われます。しかし、U
を使う場合、移植性をはばむ、C++における二大問題を避けることが困難になります。
- 符号付整数のビット表現
- 汎整数昇格
そんな処理系はまずありえないのですが、C++においては符号付整数の表せる範囲は物凄く偏っている可能性があります(C言語では、必ず「二の補数」「一の補数」「符号と絶対値」しかありえません)。
int
は符号付整数ですので、やはりものすごく偏っている可能性があります。
たとえば、int
の表せる範囲が-1073741824~3221225471という可能性もあります。
U
にキャストした場合、単項負符号演算子を適用する前に汎整数昇格が発生するかもしれません。
汎整数昇格が発生するのは、U
で表せる値がすべてint
でも表せる場合ですので、この部分でオーバーフローが発生することはありません。
しかし、前述のようにint
で表せる範囲が偏っている場合、int
に昇格した値に単項負符号演算子を適用した結果がint
で表せる保証はありません。
uintmax_t
を用いた場合、int
に昇格する可能性はないため、この問題は発生しません。
重箱の隅をつつくようですが、こういうパターンがあるためにuintmax_t
の代わりにU
を使うのは真の意味で「安全」とは言えません。とはいえ、むしろそのような処理系があれば教えていただきたいくらいのレベルで珍しい処理系ですが……。
速度について
ちなみに、安全性は気にしないから速度を重視したいという方もいらっしゃると思います。少なくともx86のネイティブコードを出力するまともなコンパイラであれば処理速度的にそれほど劣ったコードにはなりません。
gccでは、uintmax_t
であってもU
であってもビット演算を用いた条件分岐のないコードになりました。clangでは、uintmax_t
であってもU
であっても、char
以外はcmov
命令を用いたコードになり、cmov
命令が使えないchar
の場合はgccとほぼ同様のコードになりました。
ちなみに、char
やshort
の場合はキャストをしなくても安全です。clangでは変化しませんが、gccでは特定のパターンであることを見抜いたのか、cdq
命令を使うようになります。
一方、int
やlong long
の場合、キャストをしないとソースコード上に潜在的に未定義動作を含むことになります。ただし、キャストをしない場合とコンパイラの出力するコードは変わりません。
この場合、結果は望むものになるとはいえ、ソースコード上は潜在的に未定義動作を含んでいます。
ちなみに、以下のように(移植性はないが、その処理系にとっての)未定義動作を排除したコードでは、コンパイラは条件分岐を出力するようです。
なお、gccかつlong long
版のみ、後半部分を見抜いてcqo
命令を使うようになりました。なぜint
の時はcdq
にならないのか、x == LLONG_MIN
の分岐がないとcqo
にならないのかは不明です。
unsigned long long Abs( long long x ) { return x == LLONG_MIN ? 1ull<<63 : x < 0 ? -x : x; }
ただし、これらの結果は関数単位でのコンパイル結果を見ている点については注意が必要です。呼び出し規約上、char
やshort
の引数は符号拡張されてから関数に渡されます。
実際にはこのような関数はほぼ確実にインライン展開されるため、符号拡張命令分のコストを考える必要もあります。
参考
絶対値以外の、一般の演算についてその安全性を議論した記事として、
C++ における整数型の怪と "移植性のある" オーバーフローチェッカー (第1回 : 整数型の怪と対策の不足)
があります。落とし穴が詳しく解説されているためおすすめです。