C++で剰余演算子（%）を使わずに余りを求めるプログラム

この記事では、2つの整数NとDが与えられたとき、C++で剰余演算子（%）を使用せずに余りを求めるプログラムの作成方法を解説します。

問題の概要

数値NをDで割ったときに余る値を求めるのが課題です。ただし、モジュロ演算子（%）は使用できません。

入力例

N = 53
D = 3

出力例

2

解法1：Dの倍数を利用する方法

最もシンプルなアプローチは、N以下で最大のDの倍数を見つけ、Nからその値を引くことで余りを求める方法です。ループでDの倍数を順に確認し、Nを超えた時点で直前の倍数を使えば、余りが計算できます。

実装例

#include <iostream>
using namespace std;
int findRem(int N, int D) {
    int i ;
    for(i = 0; ;i++) {
        if(D * i >= N)
            break;
    }
    return N - (D * (i-1));
}
int main(){
    int N = 45, D = 6 ;
    cout<<"The remainder after dividing "<<N<<" by "<<D<<" is "<<findRem(N, D);
    return 0;
}

出力

The remainder after dividing 45 by 6 is 3

解法2：整数除算の商を利用する方法

もう一つの効率的な方法は、整数型変数に除算結果を代入して商の整数部分を取得する方法です。C++では整数型に代入すると小数点以下が自動的に切り捨てられるため、商Qを求めた後、D×QをNから引けば余りが得られます。この方法は計算量がO(1)で、解法1よりも高速です。

実装例

#include <iostream>
using namespace std;
int findRem(int N, int D) {
    int Q = N/D;
    int R = N - (D * Q);
    return R;
}
int main(){
    int N = 45, D = 6 ;
    cout<<"The remainder after dividing "<<N<<" by "<<D<<" is "<<findRem(N, D);
    return 0;
}

出力

The remainder after dividing 45 by 6 is 3

まとめ

剰余演算子（%）を使わなくても、Dの倍数を順に探す方法や整数除算の商を利用する方法など、複数のアプローチで余りを求めることができます。実用面では、定数時間で処理できる解法2の整数除算を利用する方法が最も効率的です。用途や制約に応じて適切な方法を選択しましょう。