Binary and Hexadecimal Arithmetic



Addition

Consider the addition of two decimal numbers: for example, 29 + 19:
c
2 9
+ 1 9
- -
4 8
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 + 1 in the 1's place was 102: the 0 was written down in the 1's place and the 1 was carried into the 2's place.
  2. 1 + 0 + 1 in the 2's place was 102, and the 0 was written down in the 2's place and the 1 was carried into the 4's place.
  3. In the 4's place, 1 + 1 + 0 was 102, with 0 written in the 4's place and 1 carried into the 8's place.
  4. The same thing happened in the 8's place.
  5. In the 16's place, 1 + 1 + 1 was 112, with the 1 written in the 16's place and 1 carried into the 32's place.
  6. 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:

c
1 D
+1 3
- -
3 0
In this example, D16 + 316 in the 1's place was 1016, 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

Before subtracting binary numbers, you must know how many bits your computer uses to add and subtract. As we will see shortly, subtraction is performed as addition of a complement. For our example, we will use a 6 bit adder.

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 1 0 12 from 1 1 0 1 12 :

1 1 0 1 1
- 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 0 1 1 0 12 becomes 1 1 0 0 1 02.
Notice that before taking the complement, we inserted
leading zeroes: this is necessary whenever we are subtracting a number which has fewer bits than the number of bits in our adder (enough leading zeros must added so that the two numbers have exactly that number of bits).

The 2's complement is then obtained by simply adding 1 to the 1's complement:

11 0 01 0
+ 1
- - - - - -
1 1 0 0 1 1

Notice that the left most bit is 1; this tells you that the value is negative.

To perform the subtraction, we just add the 2's complement to the number which we originally wanted to subtract from:
cc cc
0 1 1 0 1 1
+ 1 1 0 0 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 not actually thrown away; it is ignored because we put it there in the first place, by taking the 2's complement. Note that taking the 1's complement is the same as subtracting from all 1's; for a 6 bit adder,
0 0 1 1 0 12 → 1 1 0 0 1 02
is the same as
1 1 1 1 1 12 - 0 0 1 1 0 12.
When we took the 1's complement and then added 1, it was like adding the 7 bit value
1 0 0 0 0 0 02
to - 0 0 1 1 0 12. That seventh bit became the final carry that we ignored.
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, 27 - 13 can be computed by first finding the "9's complement" of 13, which is
99 - 13 = 86,
adding 1 to get the "10's complement" and adding that to 27:
cc
2 7
+ 8 7
- -
1 4
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 1B16 - 0D16, we first find the "15's complement" of 0D16:

F F
- 0 D
- -
F 2
add 1 to that to get F316, and add that to 1B16 to get:
c
1 B
+ F 3
- -
0 E
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:
1 B
- 0 D
- -
?
becomes
(1016)
0 B
- 0 D
- -
0 E
since 1016 + B16 - D16 is E16.

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.


Go to:Title PageTable of ContentsIndex

©2013, 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.