ビット演算による割り算の解説

「ビット演算による割り算」に関して、個人的に納得のいく解説が見つからなかったため、自分なりの理解を書き留めます。

以下のような、典型的なコーディングテストの問題を解くためにも必要な知識です。
https://leetcode.com/problems/divide-two-integers

あくまで自分の理解を噛み砕いたもので、数学的な厳密さを重視した解説ではありません。

筆算　（10進数)　から考える

具体的に、2025を71で割るケースを考えます。
小学校で習う筆算を使うと、以下のようになり、商が28、余りが37と分かります。

深く考えず手続きとして覚えている人も多いと思いますが、筆算が実際に何をしているかというと、以下の式における「2」「8」を探す作業を行なっています。

$$2025 = (2 \times 71 \times 10^{1}) + (8 \times 71 \times 10^{0}) + 37$$

以下のようなステップで、その作業が行われています。

1. $2025$を$71 \times 10^{2}$で割る。答えは$0$なので、そのまま次へ。
2. $2025$を$71 \times 10^{1}$で割る。答えが$2$。$2025$から$2 \times 71 \times 10^{1}$を引いて、$605$を得る。
3. $605$を$71 \times 10^{0}$で割る。答えが$8$。$605$から$8 \times 71 \times 10^{0}$を引いて、$37$ (余り) を得る。

2進数で考える

一般的な筆算の場合には10進数ベースで行なわれますが、これを2進数ベースで行うことも可能です。
以下の式における、「1」「1」「1」「0」「0」を探す作業となります。

$$2025 = (1 \times 71 \times 2^4) + (1 \times 71 \times 2^3) + (1 \times 71 \times 2^2) + (0 \times 71 \times 2^1) + (0 \times 71 \times 2^0) + 37$$

1. $2025$を$71 \times 2^{5}$で割る。答えは$0$なので、そのまま次へ。
2. $2025$を$71 \times 2^{4}$で割る。答えは$1$。$2025$から$1 \times 71 \times 2^{4}$を引いて、$889$を得る。
3. $889$を$71 \times 2^{3}$で割る。答えは$1$。$889$から$1 \times 71 \times 2^{3}$を引いて、$321$を得る。
4. $321$を$71 \times 2^{2}$で割る。答えは$1$。$321$から$1 \times 71 \times 2^{2}$を引いて、$37$を得る。
5. $37$を$71 \times 2^{1}$で割る。答えは$0$なので、そのまま次へ。
6. $37$を$71 \times 2^{0}$で割る。答えは$0$。$37$が余りとなる。

この時、各ステップで得られた011100 (10進数表記で$28$) が答えとなります。

アルゴリズムへと一般化する

前セクションの具体例を一般化して、アルゴリズムに落とし込みます。
割り算を、$N = DQ + R$における、商$Q$と余り$R$ $(0 \leq R < D)$ を求める問題とします。

すると、前セクションの具体例と同様に、以下のようなステップで割り算を行うことが可能です。

1. $N_{i}$を$D \times 2^{i}$で割る。その答えを$d_{i}$とする。$N_{i}$から$d_{i} \times D \times 2^{i}$を引いて、$N_{i-1}$を得る。
2. $N_{i-1}$を$D \times 2^{i-1}$で割る。その答えを$d_{i-1}$とする。$N_{i-1}$から$d_{i-1} \times D \times 2^{i-1}$を引いて、$N_{i-2}$を得る。
3. $N_{i-k}$が0になるまで続ける。

十分に大きな$i$から始めることで、商を$d_{i}$, $d_{i-1}$, ..., $d_{0}$として得ることが可能です。

アルゴリズムをコードにする

前セクションのアルゴリズムをコードにします。一例としてC++コードで表します。

class Solution {
public:
    int divide(const int dividend, const int divisor) const {
        assert(divisor != 0);

        // 符号への対応
        bool isMinus = (dividend < 0) ^ (divisor < 0);
        long long n = std::abs((long long)dividend);
        long long d = std::abs((long long)divisor);

        unsigned int result = 0;
　　　　　// 32bit整数において十分に大きなiとして、31から始める。
        for (int i = 31; i >= 0; i--) {
            if (n >= (d << i)) { // NiをD * 2^iで割った答えを求める。
                result |= (1LL << i); // 答えが1であれば、答えのbitを立てる。
                n -= (d << i); // NiからD * 2^iを引いて、次のNi-1を得る。
            }
        }

        // 答えがINT_MAX + 1になってしまうエッジケースのハンドリング
        if (!isMinus && result > INT_MAX) {
            return INT_MAX;
        }
        // 符号を付けて返す。
        return isMinus ? -result : result;
    }
};