C++で安全に絶対値を求める

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とほぼ同様のコードになりました。

ちなみに、charshortの場合はキャストをしなくても安全です。clangでは変化しませんが、gccでは特定のパターンであることを見抜いたのか、cdq命令を使うようになります。

一方、intlong 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;
}

ただし、これらの結果は関数単位でのコンパイル結果を見ている点については注意が必要です。呼び出し規約上、charshortの引数は符号拡張されてから関数に渡されます。 実際にはこのような関数はほぼ確実にインライン展開されるため、符号拡張命令分のコストを考える必要もあります。

参考

絶対値以外の、一般の演算についてその安全性を議論した記事として、

C++ における整数型の怪と "移植性のある" オーバーフローチェッカー (第1回 : 整数型の怪と対策の不足)

があります。落とし穴が詳しく解説されているためおすすめです。