C++における割り算問題はなかなか難しく、どのように実装するか悩ましい。時々競プロで出題されるが、負の整数に対して切り上げ、切り捨てを含む割り算の記事がないような気がしたので、せっかくなのでここにまとめておく。

結論

$x, y \in \mathbb{Z}, y \neq 0$ のとき、 $\lfloor x/y \rfloor$ (切り捨て), $\lceil x/y \rceil$ (切り上げ)はそれぞれ

auto div_floor = [](ll x, ll y){ 
  if(y < 0) x = -x, y = -y;
  if(x >= 0) return x / y;
  return (x-y+1)/y;
};
auto div_ceil = [](ll x, ll y){
  if(y < 0) x = -x, y = -y;
  if(x >= 0) return (x+y-1)/y;
  return x/y;
};

考えかた

まず、非負整数 $a, b$ に対して、 $a/b$ の切り上げ、切り捨ては次のように簡単に実装できる：

int div_ceil(int a, int b) { // 切り上げ
  return (a+b-1)/b;
}
int div_floor(int a, int b) { // 切り捨て
  return a/b;
}

C++11以降では、負の数に対する割り算の挙動が次のように定められている( 整数に対する除算と剰余算の丸め結果を規定 - cpprefjp C++日本語リファレンス )：

整数型を項とする/演算子の結果は代数的な商から小数部を切り捨てたものとなる。注釈：これは「ゼロ方向への切り捨て(truncation towards zero)」とも呼ばれる。

例を出すと次のようになる。

+7 / +2 == +3
-7 / +2 == -3
+7 / -2 == -3
-7 / -2 == +3

もうこの時点で四つ場合分け出てきて面倒くさいので、以下除数を正で固定しておく。もし除数が負なら、被除数と除数の符号を反転すればよい。こうするとだいぶ考えやすくなる。つまり、

+7 / +2 == +3    // 数学的には切り捨て
-7 / +2 == -3    // 数学的には切り上げ

にだけ焦点を当てればよい。これを見るとわかるが、数学的に言えば、C++11以降の実装では除算は正の被除数に対しては切り捨てであるが、負の被除数に対しては切り上げである。結構盲点ではある。ここまでで言えば、場合分けは次のようになる( $b>0$ )：

floor(a/b) = a/b    // a>=0のとき
floor(a/b) = ???    // a<0 のとき
ceil(a/b) = ???     // a>=0のとき
ceil(a/b) = a/b     // a<0 のとき

残った二つのうちfloor(a/b)から考える。例えばb=5のときを考えると-15, -14, -13, -12, -11が-3となってほしい被除数だが、実際のC++(11+)では-19, -18, -17, -16, -15が-3となる被除数である。この差を埋めるには5-1=b-1を引けばよい。一般化するほどじゃない（しめんどい）のでこれで良しとすると、

floor(a/b) = (a-b+1)/b

でok。 ceil(a/b)もほぼ同じ。b=5なら6,7,8,9,10が2となってほしい被除数だが、実際には10,11,12,13,14が2となる被除数。この差を埋めるには5-1=b-1を足せばよい。よって

ceil(a/b) = (a+b-1)/b

とすればよく、これは初めに見せたものと同じものである。

らんどせりーたの備忘録

C++11以降の負の整数に対する割り算の切り上げ、切り捨て問題を解決する

結論

考えかた