C++で乗算・除算・剰余演算を使わずに2つの整数を除算する方法

問題概要

2つの整数「被除数(dividend)」と「除数(divisor)」が与えられます。乗算(*)・除算(/)・剰余演算子(%)を使用せずに、被除数を除数で割った商を求めてください。ただし、整数除算の結果はゼロ方向へ切り捨てるものとします。入力はいずれも整数です。

例えば、被除数 = 7、除数 = -3 が与えられた場合、出力は -2 となります。

解法の考え方

この問題は、ビットシフトを活用した繰り返し減算によって効率的に解くことができます。ビットシフトは値を2倍(または半分)にする操作であるため、これを組み合わせることで、禁止された演算子を使わずに除算と同等の処理を実現できます。

具体的な手順は以下の通りです。

• 2つの引数 x(被除数)と y(除数)を受け取ります。
• x が INT_MIN かつ y が -1 の場合、結果がオーバーフローするため INT_MAX を返します。
• a := |x|、b := |y| として絶対値を取り、答え ans := 0 で初期化します。
• a − b ≥ 0 の間、以下を繰り返します。
  • p := 0 とします。
  • a − (b を左に (p+1) 回シフトした値) ≥ 0 の間、p := p + 1 とします。
  • a := a − (b を左に p 回シフトした値)
  • ans := ans + (1 を左に p 回シフトした値)
• x と y の符号が一致していれば ans を返し、異なる場合は −ans を返します。

このアルゴリズムは、a から「b の2の冪倍」のうち収まる最大のものを引き、対応する2の冪を答えに加算していくことで、二進法の筆算のような処理を実現しています。1ずつ減算する単純な方法に比べ、計算回数が対数オーダーで抑えられるため大幅に高速です。

C++での実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int divide(int l, int y) {
      if(l <= INT_MIN && y == -1)return INT_MAX;
      lli a = labs(l);
      lli b = labs(y);
      lli ans = 0;
      while(a-b >= 0){
         int x = 0;
         while(a-(b << 1 << x) >= 0){
            x++;
         }
         a -= b<<x;
         ans += 1<<x;
      }
      return (l>0)== (y>0)?ans:-ans;
   }
};
main(){
   Solution ob;
   cout << ob.divide(40, 3);
}

入力

40
3

出力

13

コードのポイント

• オーバーフロー対策： INT_MIN ÷ (-1) は int 型で表現できないため、事前に INT_MAX を返しています。
• long long の使用： シフト演算時のオーバーフローを防ぐため、絶対値は long long 型(lli)で保持しています。
• 符号の判定： 最後に (l > 0) == (y > 0) で両者の符号が一致するかを確認し、商の正負を決定しています。

上記の実行例では、40 ÷ 3 = 13.33… となるため、ゼロ方向へ切り捨てた結果 13 が出力されます。