While the idea of a number system with only two values may seem odd, it is actually very similar to the decimal system we are all familiar with, except that each digit is a bit containing a 0 or 1 rather than a number from 0 to 9. (The word ``bit'' itself is a contraction of the words ``binary digit'') For example, figure C.1 shows several binary numbers, and the equivalent decimal numbers.
Figure C.1: Binary and Decimal Numbers
In general, the binary representation of has a 1 in binary digit k (counting from the right, starting at 0) and a 0 in every other digit. (For notational convenience, the ith bit of a binary number A will be denoted as .)
The binary representation of a number that is not a power of 2 has the bits set corresponding to the powers of two that sum to the number: for example, the decimal number 6 can be expressed in terms of powers of 2 as , so it is written in binary as 110.
An eight-digit binary number is commonly called a byte. In this text, binary numbers will usually be written as bytes (i.e. as strings of eight binary digits). For example, the binary number 101 would usually be written as 00000101- a 101 padded on the left with five zeros, for a total of eight digits.
Whenever there is any possibility of ambiguity between decimal and binary notation, the base of the number system (which is 2 for binary, and 10 for decimal) is appended to the number as a subscript. Therefore, will always be interpreted as the binary representation for five, and never the decimal representation of one hundred and one (which would be written as ).
To convert an unsigned binary number to a decimal number, add up the decimal values of the powers of 2 corresponding to bits which are set to 1 in the binary number. Algorithm C.1 shows a method to do this. Some examples of conversions from binary to decimal are given in figure C.2.
Figure C.2: Examples of Conversion from Binary to Decimal
Since there are 
unique sequences of n bits,
if all the possible bit sequences of length n are used,
starting from zero, the largest number will be .
An algorithm for converting a decimal number to binary notation is given in algorithm C.2.
Addition of binary numbers can be done in exactly the same way as addition of decimal numbers, except that all of the operations are done in binary (base 2) rather than decimal (base 10). Algorithm C.3 gives a method which can be used to perform binary addition.
When algorithm C.3 terminates, if c is not 0, then an overflow has occurred- the resulting number is simply too large to be represented by an n-bit unsigned binary number.
The major flaw with the representation that we've used for unsigned binary numbers is that it doesn't include a way to represent negative numbers.
There are a number of ways to extend the unsigned representation to include negative numbers. One of the easiest is to add an additional bit to each number that is used to represent the sign of the number- if this bit is 1, then the number is negative; otherwise the number is positive (or vice versa). This is analogous to the way that we write negative numbers in decimal- if the first symbol of the number is a negative sign, then the number is negative, otherwise the number is positive.
Unfortunately, when we try to adapt the algorithm for addition to work properly with this representation, this apparently simple method turns out to cause some trouble. Instead of simply adding the numbers together as we do with unsigned numbers, we now need to consider whether the numbers being added are positive or negative. If one number is positive and the other negative, then we actually need to do subtraction instead of addition, so we'll need to find an algorithm for subtraction. Furthermore, once we've done the subtraction, we need to compare the the unsigned magnitudes of the numbers to determine whether the result is positive or negative!
Luckily, there is a representation that allows us to represent negative numbers in such a way that addition (or subtraction) can be done easily, using algorithms very similar to the ones that we already have. The representation that we will use is called two's complement notation.
To introduce two's complement, we'll start by defining, in algorithm C.4, the algorithm that is used to compute the negation of a two's complement number.
Figure C.3 shows the process of negating several numbers. Note that the negation of zero is zero.
Figure C.3: Examples of Negation Using Two's Complement
This representation has several important properties:
The same addition algorithm that was used for unsigned binary numbers also works properly for two's complement numbers.
Subtraction is also done in a similar way: to subtract A from B, take the two's complement of A and then add this number to B.
The conditions for detecting overflow are different for signed and unsigned numbers, however. If we use algorithm C.3 to add two unsigned numbers, then if c is 1 when the addition terminates, this indicates that the result has an absolute value too large to fit the number of bits allowed. With signed numbers, however, c is not relevant, and an overflow occurs when the signs of both numbers being added are the same but the sign of the result is opposite. If the two numbers being added have opposite signs, however, then an overflow cannot occur.
For example, consider the sum of 1 and -1:
In this case, the addition will overflow, but it is not an error, since the result that we get (without considering the overflow) is exactly correct.
On the other hand, if we compute the sum of 127 and 1, then a serious error occurs:
Therefore, we must be very careful when doing signed binary arithmetic that we take steps to detect bogus results. In general:
Another useful property of the two's complement notation is the ease with which numbers can be multiplied or divided by two. To multiply a number by two, simply shift the number ``up'' (to the left) by one bit, placing a 0 in the least significant bit. To divide a number in half, simply shift the the number ``down'' (to the right) by one bit (but do not change the sign bit).
Note that in the case of odd numbers, the effect of shifting to the right one bit is like dividing in half, rounded towards , so that 51 shifted to the right one bit becomes 25, while -51 shifted to the right one bit becomes -26.
Writing numbers in binary notation can soon get tedious, since even relatively small numbers require many binary digits to express. A more compact notation, called hexadecimal (base 16), is usually used to express large binary numbers. In hexadecimal, each digit represents four unsigned binary digits.
Another notation, which is not as common currently, is called octal and uses base eight to represent groups of three bits. Figure C.4 show examples of binary, decimal, octal, and hexadecimal numbers.
Figure C.4: Hexadecimal and Octal
For example, the number can be written as , , or .