Paul Mason - Division using Two's Complement

We started the journey towards optimizing the division operation within a decimal number implementation in Rust last time by investigating long division. This week we take a look at a second way to perform division upon binary numbers using the “two’s complement” method:

Part 1 - Division using Long Division
Part 2 - Division using Two’s Complement
Part 3 - A simple implementation of division in Rust

The basic concept

An alternative method for dividing a number in any base is to simply keep subtracting the divisor from the dividend. Each time you’re able to successfully subtract the full divisor you incrememt the quotient. At the very end, you’re left with the remainder.

As an example, let’s work with $\dfrac{19}{6}$:

$$ 19 - 6 = 13\;\;(q = 1) \\ 13 - 6 = 7\;\;(q = 2) \\ 7 - 6 = 1\;\;(q = 3) $$

We were able to subtract $6$ from $19$ three times with a remainder of one:

$$ q = 3 \\ r = 1 $$

It seems a little simplistic however I’m sure the programmers reading this will be able to notice some loop logic present with this concept. Subtraction isn’t the easiest operation to perform with binary numbers so how can we leverage the binary representation of a negative number to optimize this?

Signed binary number concepts

The binary value $1101$ could represent various integers depending on the number representation being used. As an unsigned integer, it is fairly trivial to calculate what the number represents using $2^0 + 2^2 + 2^3 = 13$. Typically when dealing with sign however, the first bit is used to express whether the number is positive or negative. Given the first bit of the number above is $1$ it could be assumed that the number is negative.

How the next bits are interpreted depend on the number representation being used. Two common systems are one’s complement and two’s complement. In one’s complement this binary number would represent $-2$ however using a two’s complement system this would be $-3$.

One’s complement

First of all, it’s useful to understand the basis behind one’s complement. Fundamentally, if you reverse the bits of an integer then you’ll get the negative representation.

If we were to take astep back from the example above, we know that $2$ is represented as $0010$ in binary. If we flip the bits we get $1101$. Using our simple “negation” logic means that we now have $-2$. Seems like a pretty straight forward operation; so what’s the catch?

To ensure that this rule can always be upheld, we unfortunately need to represent both $0$ (as $0000$) as well as $-0$ ($1111$). Given that $0 = -0$ it seems like a waste of space having to represent the same number twice. Enter the need for two’s complement.

Two’s complement

Two’s complement is the most common method of representing signed integers in a computer system. The general idea is that to get the negative of a number we inverse the bits and add one. Consider $0001$; if we reverse the bits and add one we get $1111$ (i.e. $1110 + 0001$). This was previously the number that represented $-0$ in our one’s complement system and consequently our range of numbers has now increased by one (i.e. from $+7$ through to $-8$ as opposed to being capped at $-7$).

What if we applied this logic to $0000$? Well, if we take the inverse and add one we essentially get $1,0000$. This of course is an overflow situation however if we discard the carry bit, we’re left with what we expect: $0000$.

So why are we talking about two’s complement? In the introduction we talked about using subtraction as a method of calculating the quotient for a division operation. By calculating the two’s complement of a number, we can now avoid having to do a subtraction but instead perform simple addition. How so?

Consider we have the number $5$ ($0101$) and we want to subtract $1$ ($0001$). If we calculate the two’s complement representation of $-1$ we get $1111$. Now if we add these two numbers together and throw away the carry bit we get:

$$ \begin{array}{r} \phantom{+}0101 \\[-3pt] + \underline{1111} \\[-3pt] 0100 \\[-3pt] \end{array} $$

This of course is what we expect: $5 + -1 = 4$.

Combining these concepts

Now that we know that two’s complement can assist us with subtraction, we can continue to combine the basic concept above to perform division. Let’s use the original example of $\dfrac{19}{6} = 3;;(r = 1)$.

Firstly, $19$ is represented in binary as $0001,0011$ and $6$ is represented as $0000,0110$. Consequently, the two’s complement representation of $-6$ is $1111,1010$.

Now if we add together these two numbers and discard the carry bit we get:

$$ \begin{array}{r} \phantom{+}0001\,0011 \\[-3pt] + \underline{1111\,1010} \\[-3pt] 0000\,1101 \\[-3pt] \end{array} \\ q = 0001 $$

$0000,0110$ is smaller than $0000,1101$ so we should try again:

$$ \begin{array}{r} \phantom{+}0000\,1101 \\[-3pt] + \underline{1111\,1010} \\[-3pt] 0000\,0111 \\[-3pt] \end{array} \\ q = 0010 $$

Once again, $0000,0110$ is smaller than $0000,0111$ so we try again:

$$ \begin{array}{r} \phantom{+}0000\,0111 \\[-3pt] + \underline{1111\,1010} \\[-3pt] 0000\,0001 \\[-3pt] \end{array} \\ q = 0011 $$

We can now see that $0000,0110$ is bigger than $0000,0001$ so we can stop. Consequently as expected, we have a quotient of $0011$ ($3$) and a remainder of $0001$ ($1$).

Next steps: implementing the algorithm

That’s it for today; next time we’ll go into how to implement integral division using the Rust language. Once we’ve covered the basics of integral division we’ll investigate how we can represent high precision fractions.

Division using Two's Complement