Binary and Hexadecimal Arithmetic
Addition
Consider the addition of two decimal numbers: for example, 29 + 19:
where the "c" in the top row correspond to the carry (with a value of 1).
Notice that the addition was performed on consecutive place values, from the
least significant digit to the most significant digit. In the 1's place,
the sum of the digits is 18; since this is greater than 9, 8 is written down in the 1's place
and the 1 is carried to the place value on the left (10's). The carry is then added into the next place value.
By analogy, in an arbitrary base "n", if the sum of the digits in any place value is greater than n - 1, the
1's portion of the sum is written down and the "n's" portion is carried to the place value on the left. In the
binary number system, therefore, if the sum of the digits in any place value is
greater than 1, the 1's portion
of the sum is written down and the 2's portion is carried to the place value on the left:
| | c | c | c | c | c |
| | | 1 | 1 | 1 | 0 | 1 |
| + | | 1 | 0 | 0 | 1 | 1 |
| | - | - | - | - | - | - |
| | 1 | 1 | 0 | 0 | 0 | 0 | |
In this example,
- 1 + 1 in the 1's place was 10 2: the 0 was written down in the 1's place and
the 1 was carried into the 2's place.
- 1 + 0 + 1 in the 2's place was 10 2, and
the 0 was written down in the 2's place and the 1 was carried into the 4's place.
- In the 4's place, 1 + 1 + 0 was 10 2, with 0 written in the 4's place and 1 carried
into the 8's place.
-
The same thing happened in the 8's place.
-
In the 16's place, 1 + 1 + 1 was 11 2, with the 1 written in the 16's place and 1
carried into the 32's place.
-
And in the 32's place, 1 + 0 + 0 was 1.
You should verify that this binary example corresponds to the previous example in decimal.
In exactly the same fashion, we can do hexadecimal addition:
In this example, D 16 + 3 16 in the 1's place was 10 16, and the 0 was
written down in the 1's place while the 1 was carried into the 16's place. Verify that this, too, is the
same problem as the others.
Subtraction
Most of us learned subtraction using the technique of borrowing from place values to the left. In the
binary number system, depending on the particular numbers being subtracted, borrowing can be quite painful.
Instead, we will use a technique called "2's complement".
Suppose that we wish to subtract 1 0 1 1 0 1 2 from 1 1 1 1 0 1 1 2 :
| | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| - | | 1 | 0 | 1 | 1 | 0 | 1 |
| | - | - | - | - | - | - | - |
| | | | | | | | ? |
The first step is to compute the "1's complement" of the number being subtracted (if we're subtracting
a - b, we need the complement of b).The 1's complement is simply the inverse of the number: every 1 is
replaced by 0 and every 0 is replaced by 1:
0 1 0 1 1 0 1 2 becomes 1 0 1 0 0 1 0 2.
Notice that before taking the complement, we inserted a leading 0: this is necessary whenever we are
subtracting a number which has fewer bits than the number we're subtracting it from (enough
leading zeros must added so that the two numbers have exactly the same
number of bits).
The 2's complement is then obtained by simply adding 1 to the 1's complement:
| | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| + | | | | | | | 1 |
| | - | - | - | - | - | - | - |
| | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
To perform the subtraction, we just add the 2's complement to the number which we originally wanted to
subtract from:
| | c | c | c | | | c | c |
| | | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| + | | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| | | - | - | - | - | - | - | - |
| | | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
Notice that we have a carry left over; when using 2's complement subtraction, this is expected: the final
carry is "thrown away."
It is amusing to note that this technique works in any number system: if you don't like to borrow in
ordinary decimal subtraction, you can always add the "10's complement" instead. For example, 59 - 45 can
be computed by first finding the "9's complement" of 45, which is
99 - 45 = 54,
adding 1 to get the
"10's complement" and adding that to 59:
We then throw away the extra carry to get 14.
And of course, we can use "16's complement" to perform subtraction in hexadecimal. To compute
3B 16 - 2D 16, we first find the "15's complement" of 2D 16:
add 1 to that to get D3 16, and add that to 3B 16 to get:
But borrowing is not the same problem in hexadecimal as it is in the binary number system: in the previous
example, we can borrow a 1 from the 16's place:
becomes
since 10 16 + B 16 - D 16 is E 16.
And of course by now you have realized that all of the subtraction examples above are really
the same problem!
Now we are ready to see how unsigned and signed integers are stored
in computers.
©2002, Kenneth R. Koehler. All Rights Reserved. This document may be freely
reproduced provided that this
copyright notice is included.
Please send comments or suggestions to
the author.