Dividing 2 integers with some constraints This a problem i came across while practicing binary search. Here is the problem:

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.

Note:   


Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store 
      integers within the 32-bit signed integer range: [−2^31,  2^31 − 1]. For 
      the purpose of this problem, assume that your function returns 2^31 − 1 
      when the division result overflows.


A Brute force Solution is that subtract the dividend with the divisor till it is greater and the number of subtractions is the result. But it is giving Time Limit Exceeding error. 

How to solve the problem efficiently or using Binary Search ??

Also provide the time complexity as well.
Here is a strategy (I will only consider positive numbers): 
Let $d$ be the dividend and $x$ be the divisor. Generate all values $x_i = 2^i x$, up to some some $x_k$ such that $x_{k+1}$ exceeds the dividend. This can be done with only one addition per value since $x_{0} = x$ and, for $i \ge 1$, $x_i = x_{i-1} + x_{i-1}$.
Similarly, generate all values $b_i = 2^i$ for $i=0, \dots, k$.

Let $r$ be a variable that will hold the result. Initially $r=0$. For $i=k$ down to $0$ do the following:


Check whether $x_i$ is bigger than $d$;
If that is the case, then you know that, by subtracting $x_i$ from $d$, you are effectively subtracting $x$ from $d$ a total of $b_i = 2^i$ times. Update $d = d- x_i$, and $r = r + b_i$.


Finally, return $r$.

This strategy requires only a logarithmic number of operations w.r.t. $d/x$ (up to multiplicative and additive constants). Since this is at most $2^{31}$, the time needed is always upper bounded by a constant.



As an example, let's divide $62$ by $3$.
The sequences of values $x_i$ will be:
$x_0 = 3, x_1 = 6, x_2 = 12, x_3 = 24, x_4 = x_k = 48$, since $x_5 = 96 &gt; 62$.
The corresponding values $b_i$ are: $b_0 = 1, b_1=2, b_2=4, b_3=8, b_4=16$.


Initially $d=62$, $x=3$, $r=0$.
In the fist iteration ($i=k=4$) we have  $62 = d \ge  48 = x_4 $, and we update: $d = 62 - x_4 = 62-48 = 14$, and $r = 0 + b_4 = 0 + 16 = 16$.
In the second iteration ($i=3$) we do nothing since $d = 14 \not\ge 24 = x_3$.
In the third iteration ($i=2$) we have $d = 14 \ge 12 = x_2$, and we update $d = 14 - x_2 = 14 - 12 = 2$, and $r = 16 + b_2 = 16 + 4 = 20$.
In the forth iteration ($i=1$) we do nothing since $d = 2 \not\ge 6 = x_1$.
In the fifth and final iteration ($i=0$) we do nothing since $d = 2 \not\ge 3 = x_0$.


In the end we have $r=20$ and $d=2$. Indeed: $62 = 3 \cdot 20 + 2$.