Jan 102017
 

Binary NumbersIn my last post about binary signed integers, I introduced the ones complement representation. At the time, I said that the ones complement was found by taking the bitwise complement of the number. My explanation about how to do this was simple: invert each bit, flipping 1 to 0 and vice versa. While it’s true that this is all you need to know in order to determine the ones complement of a binary number, if you want to understand how computers do arithmetic with signed integers and why they represent them the way they do, then you need to understand what complements are and how the method of complements allows computers to subtract one integer from another, or add a positive and negative integer, by doing addition with only positive integers.

Radix

The radix of a number system, also known as a number system’s base, is the number of unique digits, including zero, that are used to represent the system’s numbers. The decimal number system consisting of digits 0 – 9 has a radix of 10. The binary number system, which we are interested in here, has two digits: 0 and 1 so its radix is 2. One other number system that plays an important role in computer systems in hexadecimal. Hexadecimal numbers are base 16. In addition to the digits 0 – 9, the system also includes the digits A, B, C, D, E, and F to represent the decimal numbers 10, 11, 12, 13, 14, and 15 respectively.

In instances where the radix of a number is ambiguous, it will be denoted as a subscript to the right of the number. For example, 11_{10} is decimal number 11 while 11_{2} is binary 11 (decimal number 3).

Radix Complement

The radix complement of an n-digit number in radix b is defined to be:

    \[b^n - y\]

So what does that make the radix complement? Let’s think about 2 digit decimal numbers. Since we are dealing in radix (base) 10, then b^n equals 100, the smallest 3 digit decimal number. The radix complement, therefore, is the number that when added to cause the sum to “rollover” from 2 digits to three digits.

This is true regardless of the radix. If we consider a four digit binary number, say 101_2, then b^n equals 1000_2. The radix complement is calculated thusly:

\begin{tabular}{ccccc} & 1 & 0 & 0 & 0 \\ - & 0 & 1 & 0 & 1 \\ \hline & 0 & 0 & 1 & 1 \\ \end{tabular}

So the radix complement of 101_2 is 011_2.

The radix complement of decimal number is known as the tens complement, while the radix complement of a binary number is called the twos complement. Be sure to remember the latter!

There is an easier way to calculate the radix complenment, but to do so you first need to know about the diminished radix complement.

Diminished Radix Complement

The diminished radix complement of an n-digit number y in radix b is defined as:

    \[(b^n - 1) - y\]

We see that the diminished radix complement is just one less than the radix complement. It is the number that when added to yields the largest number that can be represented by n digits in radix b. The diminished radix complement of a decimal number is called the nines complement while the diminished radix complement of a binary number is called the ones complement. Sound familiar?

So why bother? Why give this number it’s own name when we’ve already got the radix complement? The answer is because by its nature, the diminished radix complement is much easier to compute than the radix complement. Once you’ve got the diminished radix complement all you need to do is add 1 to it to get the radix complement:

    \[\underbrace{\overbrace{(b^n - 1) - y}^{\substack{\text{diminished radix} \\ \text{complement}}} + 1}_\text{radix complement}\]

How easy is it to calculate the diminished radix complement? Simple. Subtract every digit in your number from (b – 1) and you’re done. Easy peasy.

For example, to find the nines complement of 487341 just subtract each digit from 9, and you’ve got your answer: 512658. The tens complement? To calculate it just add 1, and you get 512659. We can do a quick sanity check by adding our original number to the tens compliment. The tens complement of six digit decimal (radix 10) number should be 10^6 or 1000000.

\begin{tabular}{cccccccc} & & 4 & 8 & 7 & 3 & 4 & 1 \\ + & & 5 & 1 & 2 & 6 & 5 & 9 \\ \hline & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{tabular}

And it is. We’re sane.  Or I am anyway. I can’t speak for you.

Now we can understand why taking the bitwise complement of a binary number yields the ones compliment, ie., the diminished radix complement. Flipping each bit from 0 to 1 and vice versa is the same as subtracting each bit value from 1 (b - 1), our shortcut for calculating the diminished radix complement. 1 - 0 = 1 and 1 - 1 = 0.

But why does that work? Why can we subtract every digit from b - 1 to get the diminished radix complement? That can be explained with a little algebra.

Consider:

b^n - 1

This is equivalent to:

b^n - 1^n

This is binomial that can be factored according to the rule:

x^{n + 1} - y^{n+1} = (x - y)\sum_{k=0}^{n}x^{k}y^{n-k}

Applying this rule to our binomial:

b^n - 1^n = (b - 1)\sum_{k=0}^{n-1}b^{k}1^{n-k} =(b - 1) \sum_{k=0}^{n-1}b^{k}

The answer is in there, but we can tease it out to make it a little more obvious. Let’s expand the summation:

b^n - 1 = (b-1)(b^{n-1} + b^{n-2} + \ldots + b + 1)

Now multiply through:

b^n - 1 = (b-1)b^{n-1} + (b-1)b^{n-2} + \ldots + (b-1)b + (b-1)

Hopefully it is obvious now. 0, b, b^2, \ldots , b^{n-2}, b^{n-1} are the respective place values of an n-digit number with radix b. Multiplying each place value by b – 1 gives us an n-digit number where each digit is b – 1.  So, if every digit of b^n -1 is b – 1, then subtracting is the same as subtracting every digit of y from b  – 1.

That wraps up this introduction to complements. In the next post I am going to discuss the method of complements, a method use to subtract one number from another using the addition of only positive numbers. It is this principle that underlies the way computers perform addition and subtraction with binary signed integers. Until then.

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

(required)

(required)