This post is part of the *“Algos in Plain English”* post series.

The discussed algorithm aims to efficiently express floor division without use of multiplication (`*`

), division (`/`

or `//`

, depending on the language), and modulo (`%`

) operators. This algorithm is expected to run in `O(log(n))`

, where `n`

is the `dividend`

.

The problem statement (pulled straight from Leetcode), is as follows:

Given two integers

`dividend`

and`divisor`

, divide two integerswithoutusing multiplication, division, and mod operator.

Constraints on the problem include:

`-(2 ** 31) <= dividend, divisor <= 2 ** 31 - 1`

- If the quotient is strictly greater than
`2**31 - 1`

, then return`2 ** 31 - 1`

, - If the quotient is strictly less than
`-(2 ** 31)`

, then return`-(2 ** 31)`

.

NOTE: Division can always be thought of as an operator between 2 unsigned integers, with a sign applied later based on the similarity or difference of the `dividend`

and `divisor`

signs. In the discussions below, we will speak of division as if it’s between unsigned integers for the sake of simplicity.

A common approach to solve this problem is to repeatedly subtract `divisor`

from `dividend`

until we can’t subtract a full `divisor`

from `dividend`

without going below `0`

. This algorithm would keep track of the number of times we could subtract `divisor`

from `dividend`

. The naive approach can be written as follows:

```
from decimal import DivisionByZero
MAX_INT = 2**31 - 1
MIN_INT = -(2**31)
def basic_divide(dividend: int, divisor: int) -> int:
if divisor == 0:
raise DivisionByZero()
is_pos = (dividend < 0 and divisor < 0) or (dividend > 0 and divisor > 0)
dividend, divisor = abs(dividend), abs(divisor)
answer = 0
while dividend >= divisor:
answer += 1
dividend -= divisor
return max(min(answer if is_pos else -answer, MAX_INT), MIN_INT)
```

Outside of some boilerplate code to check inputs and deal with signs, this code is very basic. However, it is also very slow for larger `dividend`

’s and small `divisor`

’s. It runs in `O(n)`

time, where `n`

is the `dividend`

.

Assume the following pathological input:

```
basic_divide(MAX_INT, 1)
```

The algorithm above literally counts from `0`

to `MAX_INT`

, which is incredibly slow. If we run the above `python`

code, **it takes 169.63s to run on my Macbook Pro 15’.**

To understand the improved algorithm, we must build on a few concepts.

The naive approach fails to recognize a facet of numbers we can exploit for a logarithmic runtime:

Any number can be expressed by some summation of unique powers of 2 (1, 2, 4, 8, etc.)

Let’s look at some examples of what I mean:

`7 = 4 + 2 + 1`

`8 = 8`

`9 = 8 + 1`

`10 = 8 + 2`

`11 = 8 + 2 + 1`

The above is obvious if you think of numbers in terms of their binary representation. The binary representation of a number is literally expressing what powers of 2 sum to a given number by having a `1`

in the binary value if that corresponding power of 2 is part of the summation, and a `0`

if it’s not. Let’s look at a few of the above examples in their binary representations:

`7 = 111`

`8 = 1000`

`9 = 1001`

`10 = 1010`

`11 = 1011`

To really drive this point home, take `7`

. `7`

can be expressed as a summation in the following way:

```
(1 * 2 ** 2) + (1 * 2 ** 1) + (1 * 2 ** 0)
```

Notice how each “chunk” of this summation is the bit value at a given position, multiplied by a power of 2. `9`

can be expressed the following way:

```
(1 * 2 ** 3) + (0 * 2 ** 2) + (0 * 2 ** 1) + (1 * 2 ** 0)
```

At this point, you may be asking why this binary intuition is necessary. Well…

Given the above intuition, we can apply it to the original problem. If any number can be expressed as a summation of unique powers of `2`

, **this means our quotient can be expressed in this way as well.** How can we derive the quotient then?

It helps to start with an example upfront of why the above is important. Say we want to perform the following operation:

```
divide(100, 5)
```

One could subtract `5`

from `100`

a total of `20`

times, but let’s see if we can apply some of our intuition to the problem.

Let’s ask ourselves a question: *what is the highest power of 2 that 5 can be multiplied by where the product of said multiplication is still <= 100*? This can be stated formally as:

What is largest

`n`

where`(2 ** n) * divisor <= dividend`

?

*NOTE: The above question is not framed in terms of the power of 2, but rather the exponent that yields a power of 2.*

In the case of `5`

and `100`

, the highest value of `n`

is `4`

(which represents `16`

as the power of `2`

), because `5 * 16 = 80`

. This is valuable intel, because we now know that `5`

goes into `100`

at least `16`

times.

Now what? Well, let’s perform `100 - 80 = 20`

, since we already know how many times `5`

goes into `80`

. We are concerned now with understanding how many times `5`

goes into `20`

. We can now ask a similar question to before: *what is the highest power of 2 that 5 can be multiplied by where the product of said multiplication is still <= 20* The answer to this question is

`4`

(or `n = 2`

in terms of the exponent), because `5 * 4 = 20`

. At this point, we’ve found the answer because performing `20 - 20 = 0`

. This means the result of our division is `16 + 4 = 20`

.Let’s take another example: `divide(55, 7)`

. Let’s run through our approach:

```
55 - (7 * 4) = 27
27 - (7 * 2) = 13
13 - (7 * 1) = 6
```

In the above example, we avoid going to `0`

because `7`

can’t go into `6`

a total of `1`

or more times. Our answer would be `4 + 2 + 1 = 7`

.

With the above building blocks, we can formalize the final question our algorithm aims to answer:

What unique powers of

`2`

can I multiply by`divisor`

and sum up to derive my answer to the division question?

An ideal algorithm would enable us to find `16 + 4`

quickly in the `100 / 5`

example, and `4 + 2 + 1`

quickly in the `55 / 7`

example.

**Wait!?** What’s all this talk of multiplication? I thought that wasn’t allowed based on the question prompt? Well, a useful property of binary numbers is that multiplication and division can be expressed as left and right shifts respectively. For example:

```
7 << 1 = 14 # 111 -> 1110; this is equivalent to multiplying by 2
7 >> 1 = 3 # 111 -> 11; this is the equivalent of dividing by 2
```

This means we can “multiply” by using bit shifts; we can derive the power of 2 that we’re considering by tracking the number of bit shifts in a separate variable.

At this point, we’re ready to put the approach into code.

Below is the sample code for the improved algorithm. It is a heavily commented and tweaked version of some of the code found in this detailed StackOverflow answer.

```
from decimal import DivisionByZero
MAX_INT = 2**31 - 1
MIN_INT = -(2**31)
def divide(dividend: int, divisor: int) -> int:
# Early exit on invalid input
if divisor == 0:
raise DivisionByZero()
# Derive the sign info; it's easier to work with unsigned
# integers
is_pos = (dividend < 0 and divisor < 0) or (dividend > 0 and divisor > 0)
# Make both integers positive, and therefore "unsigned"
dividend, divisor = abs(dividend), abs(divisor)
# Early exit, as this would be 0 no matter what;
# technically this algorithm would run correctly without
# this check (as if divisor > dividend, current would
# never be shifted left, and the shift right would make
# it perma-0 throughout the run of the algorithm)
if dividend < divisor:
return 0
# Answer will be what is built throughout the
# algorithm's progression below
answer = 0
# Represents the most-significant bit we can add to answer, as
# the algorithm's logic flows
current = 1
# This run finds the highest n where:
# (2 ** n) * divisor <= dividend
while divisor <= dividend:
divisor <<= 1
current <<= 1
# Backtrack as the above loop will overshoot the highest
# n by 1
divisor >>= 1
current >>= 1
# Loop until we have no divisor left
while divisor != 0:
# Attempt to see if the current divisor (which is
# multiplied by power of 2) is <= the remaining dividend
if divisor <= dividend:
# If it is <=, then `current` represents a new
# power of 2 we can add to `answer`; OR-ing the numbers
# together is a simple way to add that power of 2 to
# answer
answer |= current
# The dividend is subtracted by divisor; for the rest
# of the while-looping, a new, lower n is attempted to be
# found which satisfies the condition:
# (2 ** n) * divisor <= dividend (what is remaining of it)
dividend -= divisor
# Akin to dividing each by 2
divisor >>= 1
current >>= 1
# When submitting this answer on Leetcode, the answer must be within
# the bounds of 2 specified integers; this max(min(...)) sequence
# ensures that
return max(min(answer if is_pos else -answer, MAX_INT), MIN_INT)
```

`while`

-loops doing?The most important nuance of this approach is that it doesn’t start from `0`

to determine the power of `2`

to add to the answer at each step. It uses the fact that the `quotient`

will be the sum of **unique** powers of `2`

. This means the algorithm can scan the powers of `2`

from highest to lowest, adding the ones to the answer that, when multiplied by `divisor`

, incrementally “chip away” at `dividend`

.

The above approach results in a single clean pass. This is more efficient than “counting up” (e.g. `1, 2, 4, 8 ...`

) to see what power of 2 can be added to the answer based on the `divisor`

going into the remaining `dividend`

that number of times.

The above algorithm has a time-complexity of `O(log(n))`

, where `n = dividend`

. Counting up to the most significant bit takes `log(n)`

time, and going down to `0`

again takes `log(n)`

time.

Practically speaking, running:

```
divide(MAX_INT, 1)
```

…**takes 0.03s to run on my Macbook Pro 15’.** Recall, the naive solution

`169.63s`

to run on my Macbook Pro 15’.`5000x`

speedup).Analyzing algorithms like this one enables one to understand the binary number system better, and how it can be used creatively for efficient operations on numbers. It’s also a good look “under the hood” at how mathematical operations can be built programmatically.

- The above efficient algorithm passed Leetcode’s “Divide Two Integers” question.
- Jerry Coffin’s great StackOverflow answer was instrumental in enabling me to understand the algorithm myself. Go check out his answer for a great comparison to how this algorithm mirrors traditional long divison!