ビット演算子だけで整数の割り算（余あり）をする方法


掛け算の場合は

[code]

    5 * 10 = 0b101 * 0b1010
           = 0b101 * (2^3 + 2^1)
           = (0b101 << 3) + (0b101 << 1) = 0b110010 = 50
    
[/code]

で計算できるのは分かるのですが、5/3などを計算する場合どうすればいいのか思い当たらないので説明いただければと思います。
そのまま割る方法でも、1/3をバイナリで表現する方法でも大丈夫です（5 * 1/3 と出来るので）。




下記コードは、割り算の筆算アルゴリズムを2進数でそのまま実装したものです。（C言語を使用）

[code]

    void div(int n, int d)
    {
      int m = 1, q = 0;
      while (d <= n) {
        d <<= 1;
        m <<= 1;
      }
      while (1 < m) {
        d >>= 1;
        m >>= 1;
        if (n >= d) {
          n -= d;
          q |= m;
        }
      }
      // q=商 / n=余り
    }
    
[/code]

LiveDemo: <http://melpon.org/wandbox/permlink/blNO0ai7MChwg4a0>




下記コードは、割り算の筆算アルゴリズムを2進数でそのまま実装したものです。（C言語を使用）

[code]

    void div(int n, int d)
    {
      int m = 1, q = 0;
      while (d <= n) {
        d <<= 1;
        m <<= 1;
      }
      while (1 < m) {
        d >>= 1;
        m >>= 1;
        if (n >= d) {
          n -= d;
          q |= m;
        }
      }
      // q=商 / n=余り
    }
    
[/code]

LiveDemo: <http://melpon.org/wandbox/permlink/blNO0ai7MChwg4a0>

