Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

トップ > C++ > 【C++】整数同士の除算における切り捨て・切り上げ処理に関するメモ

【C++】整数同士の除算における切り捨て・切り上げ処理に関するメモ

C++ 天井関数 床関数 プログラミング AtCoder

はじめに

AtCoder の問題を解いていると時々必要になってくるのが、


整数 A, B が与えられる。 A を B で割った値を切り捨てた値、および切り上げた値を求めよ。ただし、 A, B は負の値になることもあり、 B \neq 0 である。

という、整数同士の除算における切り捨て・切り上げの処理だ。特に、負の数の除算は切り捨て時の挙動がプログラミング言語ごとに異なるので混乱しやすい。

ということでこの記事では、 C++ における整数同士の除算の切り捨て・切り上げ処理の実装について、自分のメモがてら書くことにする。

まずは定義から

具体的な実装に入る前に、まずは切り捨て・切り上げの定義についてまとめる。

切り捨て (床関数)

ある実数 x に対して、「 x を切り捨てる」とは、 x 以下の最大の整数を求めることである。この操作を行う関数として床関数というものがあり、以下のように定義される。


x \in \mathbb{R} に対して、 x 以下の最大の整数を返す関数 :

\lfloor \cdot \rfloor : \mathbb{R} \to \mathbb{Z}

を床関数という。

ちなみに、中学・高校数学で出てくるであろう「ガウス関数」も全く同じ挙動をする。

例えば、
\begin{align*}
\lfloor 5.7 \rfloor & = 5 \\
\lfloor 2 \rfloor & = 2 \\
\lfloor -7.6 \rfloor & = -8 \\
\end{align*}
となる。

この関数には、次のような性質がある。

  1. \lfloor x \rfloor \leq x < \lfloor x \rfloor + 1
  2. \lfloor x + n \rfloor = \lfloor x \rfloor + n

切り上げ (天井関数)

ある実数 x に対して、「 x を切り上げる」とは、 x 以上の最小の整数を求めることである。この操作を行う関数として天井関数というものがあり、以下のように定義される。


x \in \mathbb{R} に対して、 x 以上の最小の整数を返す関数 :

\lceil \cdot \rceil : \mathbb{R} \to \mathbb{Z}

を天井関数という。

例えば、
\begin{align*}
\lceil 4.5 \rceil & = 5 \\
\lceil 8 \rceil & = 8 \\
\lceil -1.2 \rceil & = -1 \\
\end{align*}
となる。

この関数には、次のような性質がある。

  1. \lceil x \rceil - 1 < x \leq \lceil x \rceil
  2. \lceil x + n \rceil = \lceil x \rceil + n

整数同士の除算に関する性質

次に、整数同士の除算を考えるときに成り立つ性質について考えてみる。特に、床関数と天井関数を結び付ける関係式は後述の実装過程において重要となる。

「切り捨てのマイナス」は「マイナスの切り上げ」

任意の実数 x に対して、

-\lfloor x \rfloor = \lceil -x \rceil

【証明】
まず、 n = \lfloor x \rfloor とすると、床関数の性質1より、


n \leq x < n + 1

各辺に -1 を掛けると、

-n - 1 < -x \leq -n

この式は天井関数の性質1の式と等しい。したがって -n = \lceil -x \rceil とおくことができる。よって、

-n = -\lfloor x \rfloor = \lceil -x \rceil

が成り立つ。(証明終)

例えば、

\biggl\lfloor \dfrac{10}{3} \biggr\rfloor = 3 \quad \biggl\lceil -\dfrac{10}{3} \biggr\rceil = -3

である。

「割り算に〇を足したものの切り捨て」は「割り算の切り捨てに〇を足したもの」

任意の整数 A, N, d \: (d \neq 0) に対して、

\biggl\lfloor \dfrac{N}{d} \pm A \biggr\rfloor = \biggl\lfloor \dfrac{N}{d} \biggr\rfloor \pm A

【証明】
まず、 x = \dfrac{N}{d}, n = \lfloor x \rfloor とすると、床関数の関係式1より、

n \leq x < n + 1

各辺に A または -A を加えると、

n \pm A \leq x \pm A < n \pm A + 1

n, A は整数であるから、

\lfloor x \pm A \rfloor = n \pm A = \lfloor x \rfloor

が成り立つ。(証明終)

この式は天井関数についても同様に成り立つ。

\biggl\lceil \dfrac{N}{d} \pm A \biggr\rceil = \biggl\lceil \dfrac{N}{d} \biggr\rceil \pm A

「割り算の切り上げ」は「分子を1引いた割り算の切り捨てに1を足す」

任意の整数 N, d \: (d \neq 0) に対して、

\biggl\lceil \dfrac{N}{d} \biggr\rceil = \biggl\lfloor \dfrac{N-1}{d} \biggr\rfloor + 1 = \biggl\lfloor \dfrac{N+d-1}{d} \biggr\rfloor

【証明】
まず、 \biggl\lceil \dfrac{N}{d} \biggr\rceil = \biggl\lfloor \dfrac{N+d-1}{d} \biggr\rfloor について示す。
x = \biggl\lceil \dfrac{N}{d} \biggr\rceil とすると、天井関数の関係式1より、

x - 1 < \dfrac{N}{d} \leq x

各辺に d を掛けて d - 1 を足すと、

d(x-1) + d-1 < N+d-1 \leq dx + d-1

各辺を d で割ると、

x-1 + \dfrac{d-1}{d} < \dfrac{N+d-1}{d} \leq x + \dfrac{d-1}{d}

ここで、この不等式の各項は非整数なので、床関数を取っても大小関係は変わらないから、

\biggl\lfloor x-1 + \dfrac{d-1}{d} \biggr\rfloor < \biggl\lfloor \dfrac{N+d-1}{d} \biggr\rfloor \leq \biggl\lfloor x + \dfrac{d-1}{d} \biggr\rfloor

0 < \dfrac{d-1}{d} < 1 より、 \biggl\lfloor x-1 + \dfrac{d-1}{d} \biggr\rfloor = x - 1, \: \biggl\lfloor x + \dfrac{d-1}{d} \biggr\rfloor = x であるから、

\biggl\lfloor \dfrac{N+d-1}{d} \biggr\rfloor = x = \biggl\lceil \dfrac{N}{d} \biggr\rceil

が成り立つ。そして、床関数の関係式2より、

\biggl\lfloor \dfrac{N+d-1}{d} \biggr\rfloor = \biggl\lfloor \dfrac{N-1}{d} + 1\biggr\rfloor = \biggl\lfloor \dfrac{N-1}{d} \biggr\rfloor + 1

が成り立つ。以上より、

\biggl\lceil \dfrac{N}{d} \biggr\rceil = \biggl\lfloor \dfrac{N-1}{d} \biggr\rfloor + 1 = \biggl\lfloor \dfrac{N+d-1}{d} \biggr\rfloor

が示された。(証明終)

また、この等式の N+d-1 を改めて N とすれば、次式が成り立つ。

\biggl\lfloor \dfrac{N}{d} \biggr\rfloor = \biggl\lceil \dfrac{N+1}{d} \biggr\rceil - 1 = \biggl\lceil \dfrac{N-d+1}{d} \biggr\rceil

C++ で切り捨て・切り上げ処理を実装してみる

いよいよ本題。 C++ で切り捨て (床関数) と切り上げ (天井関数) を実装してみよう。


ここで一つ注意しておきたいのは、 C++ における整数同士の除算の切り捨て処理の仕様だ。

C++ で除算を扱う二項演算子は/であり、同符号の整数a, bに対してa / bの値が割り切れないときは \biggl\lfloor \dfrac{a}{b} \biggr\rfloor 、つまり商を床関数に代入したものを返す。

...とここまではいいのだが、注意したいのは ab < 0 、つまり a と b の一方が負の数のときは、返す値は上述の床関数の代入結果ではなく、 \dfrac{a}{b} の小数部分を切り捨て (0 方向への切り捨て) た結果となる。

cpprefjp.github.io

learn.microsoft.com

例えば、

8 / 2     // 4
-8 / 2   // -4
8 / -2   // -4
-8 / -2  // 4

9 / 2     // 4
-9 / 2   // -4 (-5 ではない!)
9 / -2   // -4 (-5 ではない!)
-9 / -2  // 4

となる。


分子が正で分母が負のときは両者の符号を入れ替えるとすれば、 C++ でこれらを実装するには分子の符号による場合分けが必要になる。

床関数div_floor()を実装

仕様 :

  • 2つの整数 a, b を引数に取る。
  • b < 0 のとき
    • a を正、 b を負にする。

この下で、

  • a \geq 0 のとき
    • 普通にa / bを実行。
  • a < 0 のとき
    • 整数除算の関係式3 : \biggl\lfloor \dfrac{a}{b} \biggr\rfloor = \biggl\lceil \dfrac{a-b+1}{b} \biggr\rceil を用いる。

ただし、 \biggl\lceil \dfrac{a}{b} \biggr\rceil = \biggl\lfloor \dfrac{a-b+1}{b} \biggr\rfloor をそのまま計算すると、aが -2147483648 (int型変数の最小値) 、bが 10 といったようなときに、分子の計算でオーバーフローが起きてしまうことがあるので、整数除算の関係式2を用いて \dfrac{a+1}{b} - 1 を用いることで ( a-b+1 < 0 に注意) 、最低限のオーバーフローを防ぐ。


実装は以下のようになる。

template <class T1, class T2>
inline auto div_floor(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a >= 0)
        return a / b;
    else
        return (a + 1) / b - 1;
}

天井関数div_ceil()を実装

仕様 :

  • 2つの整数 a, b を引数に取る。
  • b < 0 のとき
    • a を正、 b を負にする。

この下で、

  • a <= 0 のとき
    • 普通にa / bを実行。
  • a > 0 のとき
    • 整数除算の関係式3 : \biggl\lceil \dfrac{a}{b} \biggr\rceil = \biggl\lfloor \dfrac{a+b-1}{b} \biggr\rfloor を用いる。

ただし、床関数のときと同様にオーバーフローを防ぐため、整数除算の関係式2を用いて \dfrac{a-1}{b} + 1 を用いる ( a \geq 0 の条件だと a = 0 のときに分子が負になることに注意) 。


実装は以下のようになる。

template <class T1, class T2>
inline auto div_ceil(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a <= 0)
        return a / b;
    else
        return (a - 1) / b + 1;
}

動作確認

では、実装した2つの関数の動作確認として、過去の AtCoder コンテストの問題を解いてみよう。

まずはdiv_floor。

atcoder.jp

コード : 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// ======================================== //

template <class T1, class T2>
inline auto div_floor(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a >= 0)
        return a / b;
    else
        return (a + 1) / b - 1;
}

int main()
{
    ll X;
    cin >> X;

    cout << div_floor(X, 10) << endl;
}

atcoder.jp

無事 AC した。


続いてdiv_ceil。

atcoder.jp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// ======================================== //

template <class T1, class T2>
inline auto div_ceil(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a <= 0)
        return a / b;
    else
        return (a - 1) / b + 1;
}

int main()
{
    ll X;
    cin >> X;

    cout << div_ceil(X, 10) << endl;
}

atcoder.jp

無事 AC した。

参考記事

qiita.com