2013-12-11

C++で、(a/b)*b + a%b != aとなる例

C++では、整数a, bにおいて、"(a/b)*b + a%b"の結果が、"a"と等しくない場合、a/bとa%bの挙動は未定義である(5.6 paragraph 4)

この条件に当てはまるaとbの値が、さっぱり思いつかなかった。b = 0の場合はそうなのだが、それは一つ前のセンテンスでカバーされている。わざわざ書く以上、b = 0以外の例があるはずだ。そこで人に聞いた。一瞬で答えを教えてもらった。

aとbがint型で、int型は2の補数で表現されていて、INT_MIN == -2^(n-1) (nはintのビット数)の場合における、a = INT_MIN, b = -1

なるほど、2の補数だから、最小値と最大値の絶対値が1ずれるわけだ。ずれは最小値の絶対値の方が1大きくなる。-1で割るということは、つまり最大値が最小値の絶対値になるということで、オーバーフローする。

#include <limits>
#include <iostream>

int main()
{
    int a = std::numeric_limits<int>::min() ;
    int b = -1 ;

    int c = (a/b)*b + a%b ;

    std::cout << c << '\n' ; 
}

興味深いことに、GNU/Linux x64のGCCとClangでコンパイルすると、標準出力にFloating point exceptionと出力され、その時点でプログラムの実行が止まる。

3 comments:

刈谷満 said...

え~と、正確には

"(a/b)*b + a%b"の結果が、"a"と等しくない場合、a/bとa%bの挙動は未定義である

ではなくて、

"a / b" の結果が結果の型で表せる場合、"(a / b) * b + a % b" は "a" と等しく、表せない場合は "a / b"、"a % b" 共に未定義である

ではないでしょうか。

ところでいつの間にかゼロ方向への切り捨てが必須になってたんですね。
知りませんでした…

江添亮 said...

(1) a / b" の結果が結果の型で表せる場合、
(2) "(a / b) * b + a % b" は "a" と等しい場合、

1, 2以外の場合は未定義。

Anonymous said...

原文はこう。
> For integral operands the / operator yields the algebraic quotient with
> any fractional part discarded; if the quotient a/b is representable in
> the type of the result, (a/b)*b + a%b is equal to a; otherwise, the
> behavior of both a/b and a%b is undefined.

刈谷さんの解釈が正解ですね。