Like everything else in computers and digital electronics, numbers are stored in a binary way - they appear as high and low voltages, which we denote as 1 and 0. How does binary arithmetic work? This is a very pragmatic introduction to an important branch of mathematics.
To see how binary arithmetic works, think first about decimal arithmetic. What does the number 749 mean? By convention, it means 9 units plus 4 tens plus 7 hundreds (ten squared, or to the power 2 is 100). The first column on the right is the number of units; the next column represents the number of tens, the next, the number of (10)2, and so on.
The base of the decimal system is the number 10; there are ten different symbols, for the ten different digits 0 - 9. To express a number in decimal, divide it by 10; the remainder is the number of units; divide the answer by 10; the remainder is the number of tens, and so on. So if the number n is represented by abcd, that means that n = d + 10(c+10(b+10a)) = d + 10 c + 102 b + 103 a.
In the binary system, the base is 2; there are only
two digits, 0 and 1; successive columns represent the number of
1's, the number of 2's, the number of 4's ((2)2),
the number of 8's ((2)3) and so on. So
a number n represented in binary as abcd means n = d
+ 2(c+2(b+2a))
= d + 2 c + (2)2b +
(2)3a.
(Point of interest; the Babylonians used a base of 60 in their calculations: which is why there are 60 seconds in a minute and 60 minutes in a hour, and 360 degrees in a circle.)
To convert a number into binary, successively divide it by
2;
e.g. 23/2 = 11 rem 1
11/2 = 5 rem 1
5/2 = 2 rem 1
2/2 = 1 rem 0
1/2 = 0 rem 1
So 23 is 10111,
or 1 x (2)4 + 0 x (2)3
+ 1 x (2)2 + 1x (2)1
+ 1 x (2)0
or 16 + 4 + 2 + 1
It is purely conventional that numbers to the right are less significant and those to the left are more significant. Some useful values to remember:
24 = 16; 26 = 64; 28 = 256; 210 = 1024 (1 "K")
212 = 4096; 216 = 64 K (65536)
220 = 1 "M" (1048576)
The largest number you can represent with two decimal digits is 99 - which is 1 less than 102, 999 is one less than 103
Similarly with 8 binary digits the largest number is 11111111 which is 1 less than 100000000 (28 or 256), and with 16 binary digits the largest is 65535 (1 less than 64K)
Computers use binary arithmetic because they use binary digital logic - two state circuits. We shall see later some of the algorithms which they can use.
Two other bases, apart from binary and decimal are in common use in computing: the most important is hexadecimal - base 16., the other is octal - base 8 which is less frequently used. For this system we need 16 symbols, to represent the values 0 up to 15; the symbols usually used are
0 1 2 3 4 5 6 7 8 9 A B C D E F
A Hex number with digits "pqrs means s + r x 16 + q x 162 + p x 163
For example 1C8 means 8 + (12 x 16) + 256 = 256 + 192 + 8 = 456
However hexadecimal arithmetic is not really used much;
rather hexadecimal numbers are used as a quick way of writing
down binary numbers. The reason is that one hex digit is equivalent
to four binary digits: the table is as follows:
0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 A 1010 B 1011 C 1100 D 1101 E 1110 F 1111
Thus you can write "binary coded hex" if you like, but the answer is just binary:
1C8 is 000111001000
On the one hand this is 8 + 12 x (16) + 1 x (16)2 = 456
on the other it is 8 + 64 + 128 + 256 = 456
Converting from binary to hex is easy, and converting from hex to binary is easy; just do it four bits at a time.
Examples:
1100 1011 0010 0001 = CB21
FE46 = 1111 1110 0100 0110
Hex is not usually used as a system of arithmetic, but as a means of writing binary numbers.
Nearly all computers now use patterns of bits either 4 long, 8 long, 16 long, 32 long or even 64 long. This being so, hex is more common than octal; 8 bits is one byte and can be represented by 2 hex digits; 16 bits is two bytes or 4 hex digits; 32 bits is 4 bytes or 8 hex digits, and so on.
A pattern of four bits is sometimes called a "nibble" (half a byte!)
One binary digit is called a "bit".
Conversion between binary and decimal
Converting between different bases will help to clarify how the base systems work.
To convert from binary to decimal:
each column is weighted: evaluate each column separately, and add the result:
e.g. convert 11011010 to decimal
= 0x1 + 1x2 + 0x4 + 1x8 + 1x16 + 0x32 + 1x64 + 1x128
= 2 + 8 + 16 + 64 + 128
= 26 + 192 = 218
Decimal to binary: successively divide by 2
218 /2 = 109 rem 0
109 /2 = 54 rem 1
54 /2 = 27 rem 0
27 /2 = 13 rem 1
13 /2 = 6 rem 1
6 /2 = 3 rem 0
3 /2 = 1 rem 1
1 /2 = 0 rem 1
starting from bottom and reading up-wards:11011010
Alternatively, subtract powers of 2:
218 - 128 = 90
90 - 64 = 26
26 is smaller than 32
26 - 16 = 10
10 - 8 = 2
So 218 = 128 + 64 + 16 + 8 + 2 = 11011010
Note that numbers with decimal points can be converted as well:
10.7510 = 1010.112
Signed numbers
Negative numbers can also be represented in binary. In fact, there are two common methods for doing this.
Signed numbers - One's Complement (sign-magnitude)
A computer can store only the value 0 or 1 (or high and low voltages) in a digit (bit); usually we may use "unsigned binary" which is the system described so far; but remember that that is purely conventional; we decide that the bit on the left will stand for the number of 128's and the bit on the right will stand for the number of 1's.
When we look into implementing binary arithmetic on computers we realise we cannot write a "-" sign, but one bit could stand for "+ or -". For example, with 8 bits, the first bit could be 0 for positive numbers, and 1 for negative numbers.
So 10011000 would be -24 and 00011000 would be +24
This is possible : it is called the "sign magnitude" representation.
There are two problems: doing sums with these numbers is difficult; you have to used different algorithms with positive and negative numbers. Second, there are two "zeros": 10000000 and 00000000; this can cause problems as well.
Signed numbers - Two's Complement
The usual method for storing negative numbers in computers, is called "2's complement" (for reasons that we will explain.)
To represent a negative number, write down the number which you would have to add to a positive number of the same magnitude to get zero (apart from a carry). N.B. you have to know how long the number is. The examples we use first will be for 4 bit numbers
e.g. -3: in binary
0011 the value of 3
+1101 add this value
____
0000 - i.e. Zero
so - 3 is 1101
Comparison: in decimal, with four digits, the number below 0 is 9999: 9999 + 1 = (1)0000; ignore the "carry" bit and 9999 behaves like -1.
This tells us what we are trying to do: but not how to do it.
Formula for getting the "2's complement" of a number:
change 0-1 and 1-0, (that's called the "1's complement")
then add 1
positive number: 0100 (4)
1's complement: 1011 +1 =
2's complement: 1100 (-4)check :
1100 (-4) +
0100 (4) =
0000 - actually there is a carry of 1, but this overflows the 4-bit value and is ignored.
The "2's complement system" is preferred for most computing applications because:
0110 = +6
1100 = 12 (unsigned 4-bit integer) = - 4 (signed 4-bit integer)
In two's complement we interpret the most significant bi in a special way, therefore it is very important to know whether a number is signed or unsigned when we look at a value with the most significant bit set to a logic 1. The point is that 12 is 16 - 4; so we use it to stand for - 4.
In eight bit signed numbers, numbers from 00000000 to 01111111 (127) are positive, while from 10000000 to 11111111
(-128 to -1) are negative.
In 16 bit signed numbers, numbers from 0000000000000000 - 0111111111111111
(32767) are positive, while numbers from 1000000000000000 (-32768)
- 1111111111111111 (-1) are negative.
We can write these numbers in hex if we wish: 0000 to 7FFF are
positive and 8000 to FFFF are negative; but note we are really
writing binary numbers in a kind of short-hand. The most significant
(left most) bit still serves as a "sign" bit. If the
value is '1' it indicates a negative number, as in 1's complement
arithmetic.
Note that you can use the same method to go back from negative numbers to positive numbers;
-6 is 1010: the "ones complement" is 0101: add 1 gives 0110, which is six. So taking the twos complement in this way always gives a number of the same magnitude and opposite sign.
Formula: take the ones complement (invert each bit) and add one.
Adding and subtracting signed numbers
Adding signed numbers - just the same as unsigned binary:
00111001 + 57
11000011 - 61
11111100 = -4
Note: problems can arise when we add two large positive numbers:
e.g. 100 + 100 = 200
01100100 +100
01100100 +100
11001000 = - (00110111 + 1) = - (00111000) = -56!
need more than 8 bits, since range is 127 to -128; we have an
overflow!!!!!
Subtracting signed numbers:
take two's complement of the second operand, then add
e.g 00011110 - 30 -
00001111 15
take two's complement of second number: 11110000 + 1 = 11110001, now add: 00011110 + 30
11110001 -15
001111 = +15
Floating point numbers
Many numbers we come across in the "real" world are
not integers (or whole numbers). In ordinary arithmetic we use
"scientific notation" to deal with very small and very
large numbers. We write 1.45 x 1023 or 0.56 x 10-20 instead of
trying to write huge integers or tiny fractions. The same can
be done with binary representation: we write a number as
p x 2q
p and q are usually signed integers; all we record is the binary numbers p and q. For example, one standard format uses 80 bits: the first 16 represent p and the next 64 represent q; this allows representation of a range of numbers from 104931 down to 10-4933 both positive and negative.
The course will not give any more detail; you should however know that the possibility exists. The logical formulae for working out the results of multiplication or addition are more complicated.
There are other systems of coding, apart from those described above. These include, Octal (to represent binary numbers using groups of 3 bits, and the digit values 0-7), BAD (to represent decimal digits using groups of 4 bit nybbles), the Gray code (useful for angular encoding) and ASCII (for representing characters stored in 7 or 8 bit values).
Octal uses base 8, and just uses the symbols 0 - 7:
0 1 2 3 4 5 6 7
This is easily converted to binary, by grouping bits in groups of 3:
0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111
so 356 in octal is 011 101 110 in binary
Computers convert a number to and from decimal, so as to be able to handle decimal numbers for input and output. For that purpose they can store decimal numbers as "BCD" or binary coded decimal; the binary numbers 0000 to 1001 represent the decimal numbers 0 to 9; but numbers larger than 9 are recorded as sets of BCD digits; e.g. 4096 in binary is 1 0000 0000 0000; in BCD it is 0100 0000 1001 0110.
Gray code
To emphasise that the significance of a pattern of 0's and 1's is entirely conventional, think about another binary code - the Gray code. This is no longer a positional code; each position is not weighted in the same way as for normal binary numbers.
In binary code, several digits change at once: e.g. from 7 to 8, 0111 goes to 1000; if a number was flickering from one to the other, you might get quite wrong values in between.
In Gray code, only one digit changes at a time. The formula for generating Gray code is "to get the next code, change the single least significant digit which will lead to a new code"
Four bit Gray code:
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
This code is used for shaft encoders: you can paint a pattern of stripes which can be picked up by a detector; if the output is uncertain, as you go from one number to another, you are only uncertain by one place at the most. Note that although the bits change less frequently in the columns on the left, no longer do the individual bits now stand for "the number of 1's" or "the number of 8's"
The significance of bits in a pattern depends on the context; we have to know whether the bits we are dealing with stand for an unsigned binary number, a signed binary number, a Gray code, or something else.
See also:
Author: Gorry Fairhurst (Email: G.Fairhurst@eng.abdn.ac.uk)