Adding two binary numbers works in the same way as adding decimal numbers. Let us first consider the sum of two bits  and . In general, the sum of two bits is two bits long, because the addition can cause a carry. Bit 0 of the sum is given by the xor of both bits: . The carry  of that position is 1 if and only if , i.e. .

When adding entire bit strings not just single digits, the carry at a position needs to be propagated into the next higher position. So, if  denotes the carry bit position  generates, the sum bit at position  is given as

The carry bit of position  may also influence the carry bit out of position . For example, if , then . The carry bit position  generates is defined as

The following lemma proves that indeed is the sum of , , and .

Figure 1.3.2: The bits in the dashed box represent the right-hand side of Lemma 1.3.1 and the digits in the solid box the ones on the left-hand side.

Now, consider two bit strings  and  of equal length . When adding  and  we assume that there flows no carry into the least-significant digit, i.e. .

The following lemma shows that this definition is sound, i.e. the bit operations by which we defined the addition really produce a bit string that represents the natural number of the sum of the natural numbers that are represented by the individual bit strings.

Note that the sum contains  bits. If the carry bit out of the last position is , Lemma 1.3.5 tell us that the lower  bits are accurate, i.e. . If the carry out of the last position is , the lower  bits are not accurate and the sum is greater or equal . In this case an overflow happened and we would need all  bits to accurately represent the result. Since computers internally operate on bit strings of fixed size, there is no space to store this additional bit directly in-place with the result. If we are only interested in the least significant bits when adding, we write shortly

to indicate that we ignore the carry out of the most significant place.

Let us now turn to subtraction. Instead of inventing a new algorithm for subtracting, we are going to use a trick to express subtraction by addition. This trick hinges on the fact that we are only interested in subtracting words of  bits and not bit strings of arbitrary length. Let us first understand the overall idea using an example in base 10 arithmetic:

Assume we want to subtract base 10 numbers of length 3, and more concretely suppose we want to compute .

What essentially happens here is that we, instead of subtracting , we added  and just considered the result modulo  which is , the desired result. This of course only works if we limit the digit sequences to a certain length before (here 3).

We use the same trick to subtract two bit strings of length  and therefore define subtraction to fulfill the following specification:

So, instead of subtracting  from  we are adding to . Let us first observe that the result is equivalent to modulo  analogously to the example above. This means that the lower  bits of and lower  bits of the true difference are equal which is exactly what we wanted. The number is called the two’s complement of .

Using Lemma 1.1.6 we see that we can easily compute the two’s complement of  by flipping all bits of  and adding . The latter can easily be achieved by setting the carry into the least significant position () to . Additionally, if (i.e. the result of the subtraction is defined), will be greater than . Hence, the carry out of the most significant bit is set if the result of the subtraction is valid and is clear when the subtraction overflowed.