Integer Division Algorithm with no Division or Multiplication Operators.

I was working through a number theory problem today and I needed an efficient algorithm to find a largest integer $n$ s.t $a\times n \leq b$ for any given integers $a, b$ (w.l.o.g $a < b$). Clearly $n$ is the quotient when $b$ is divided by $a$. Following is an algorithm which can compute the quotient and reminder in $\Theta(\log(a) + \log(b))$ operations without using multiplication or division operators. In fact if the number of bits in $a$ and $b$ are known then the algorithm runs in $\Theta(\log(a) - \log(b))$ operations.

typedef unsigned int uint;

// Integer division of b with a without using division
// or multiplication operators.
div_t integer_div(uint a, uint b) {
  div_t result;
  uint bit_diff = bit_count(a) - bit_count(b);
  uint prod = 0, prod_shift = b << bit_diff, shift = 1 << bit_diff;

  result.quot = 0;
  do {
    if (prod + prod_shift <= a) {
      prod += prod_shift;
      result.quot += shift;
    }
    shift >>= 1;
    prod_shift >>= 1;
  } while (shift);
  result.rem = a - prod;

  return result;
}

// utility function to find number of bits
// required to represent the value of a.
uint bit_count(uint a) {
  unsigned int i = 0;
  do {
    ++i;
  } while ((a = a >> 1));
  return i;
}

The above algorithm was tested on $4294967293$ pairs of $(a,b), a,b \in [1, INT\_MAX]$ and compared with std::div -- running all these combinations just take around $2$ minutes on a mac book pro. It makes sense because that $\log(a) \leq 32$ (word size on the machine) hence we were just running around four billion constant operations. Typically in all algorithm analysis the word size is considered a $O(1)$, so as long as the inputs bit-widths are within the word size of the machine the runtime of the algorithm can be considered $O(1)$.


Notice that the algorithm is greedy in nature and will provide a correctness next.

Let $c=\sum_{i=0}^{\log(a)-\log(b)}t_i\times 2^{i}$ and $t_{\log(a)-\log(b)}t_{\log(a)-\log(b)-1}\ldots t_0$ the bit representation of $c$. The algorithm tries to pick the powers of $2$ in a greedy manner (i.e. $2^{\log(a)-\log(b)}\geq 2^{\log(a)-\log(b)-1} \geq \ldots 2^{0}$). Consider the choice of $i^{th}$ bit of $c$, if $2^{i}\times a \leq b$ then any $i$-bit integer with a $0$ in the $i^{th}$ bit is strictly less than $2^{i}$. Since $2^{i-1} + 2^{i-2} + \ldots 2^{0} = \frac{2^{i-1+1} -1}{2-1} = 2^{i}-1 < 2^{i}$. We can use induction of $i$ to complete the proof. Hence we can claim that if we greedily pick the powers of $2$ (i.e ${2^i\,\,| \log(a)-\log(b)\leq i \leq 0 }$) it will yield the largest integer $c$ s.t $a\times c \leq b$. The integer division algorithm is just corollary of this basic fact.