The computer lives in a world where absolutely everything is made up of either Zero's and One's. This is not so limiting as long as there are plenty of zero's and one's to work with.
Suppose we are allowed 8-bits, that is, 8 empty boxes in a row and in each box we must place either a 0 or a 1. This is called a byte. There are 256 different ways of placing zero's and one's into the byte. Hence, we can use these different patterns to represent the numbers 0 through 255.
For arithmetic, however, we would rather represent the numbers -128 through 127.
In both the unsigned representation of number 0 through 255 and the signed representation of numbers -128 through 127, we would like the representation to give simple rules for doing elementary arithmetic: addition, subtraction and multiplication. If we just arbitarily assigned each pattern of bits to a number, it might be just a big mess to try to do addition.
The binary number system representation and modular arithmetic are the solution to this problem. The binary number system uses represents a number by expressing it as the sum of pure powers of two, each power used at must once. For instance,
6 = 4 + 2 = 2^2 + 2^1,
5 = 4 + 1 = 2^2 + 2^0,
4 = 2^2,
3 = 2 + 1 = 2^1 + 2^0,
2 = 2^1,
1 = 2^0,
We conveniently write down the decomposition by writing a 1
i places to the left if 2^i is in the sum, 0 otherwise.
For emphasis, we will write _b after the number if it is in base 2.
For instance:
6 = 2^2 + 2^1 = 110_b,
5 = 2^2 + 2^0 = 101_b,
4 = 2^2 = 100_b,
3 = 2^1 + 2^0 = 11_b,
2 = 2^1 = 10_b,
1 = 2^0 = 1_b,
0 = 0 = 0_b.
Adding numbers in this form follows the usual algorithm for addition learned in childhood: there is a table of 1 bit additions which is memorized, and addition proceeds right to left, with carries brought to the top of the next column to the left if the 1 bit sum requires 2 bits. The table is easy:
0 + 0 = 0,
0 + 1 = 1,
1 + 0 = 1,
1 + 1 = 10_b,
Here's an example of 23 = 10111_b plus 17 = 10001_b:
carry -> 10111
17 -> 10001
23 -> 10111
--- ------
40 101000
Computers use a trick to represent and work with negative integers. Because the computer allocates just so many bits for an integer, when a number becomes too large to fit within that number of bits, it wraps around to zero. This is exactly like hours which go from 12 back to 1. For a byte, the wrap around goes from 255, the maximum positive value, to 0.
Hence, counting backwards can be achieved by counting forwards: subtraction can be accomplished using addition. For a byte, 256 steps forward return you to the original location, so 255 steps forward bring you to one before the original location. So adding 255 is like subtracting 1. In general, adding 256-i is like subtracting i.
Calculating from i the number 256-i is easy when done in binary:
17 = 00010001_b,
-17 = 11101111_b.
Let's try 23 - 17 in binary, using addition and the two's complement of 17,
carry -> 11111111
23 -> 10111
- 17 -> 11101111
--- ---------
6 100000110
Since only 8 bits are available, the carry-out of the
last bit is lost, and we end up with 110_b.
A single byte gives a range of 0 to 255 unsigned or -128 to 127 signed. This is a bit too small for practical work. Arithmetic is generally done not on single bytes, but on collections of bytes. The standard word is 4 bytes, giving 32 bits of integer precision. An unsigned word uses this range as 0 up to about 4 billion, a signed word uses this range as -2 billion up to 2 billion.
Half words of 16 bits and double words of 64 bits are also used. The 16 bit word is a bit inconvenient because it is possible to overflow a 16 bit word by going too positive or too negative. If you go too positive and the word is signed, you will wrap around and have a small negative.
Larger integers, using hundreds of bytes, are possible using special software. Integers of these sizes are useful for data security, where encryption and decryption are actually arithmetic computations done on very large integers.