Binary Vs Decimal
Computers use binary, or base 2, to represent numbers. Binary numbers have only 2 symbols, 0 and 1, to represent numbers. Decimal, or base 10, is the number representation system you learned as a child that has 10 symbols, 0 through 9, to represent numbers. People probably adopted the decimal number system because it was convenient to count using 10 fingers. Although there are some cultures that count using the gaps between fingers so they use octal, or base 8, to represent numbers. Computers, however, use binary because it is easier to build computers that only represent two symbols. Although there have been computers built that use decimal, including the first electronic programmable computer ENIAC.
Digits
In decimal numbers, a digit is a single symbol, from 0 to 9. Decimal numbers require multiple digits to represent numbers larger than 9. When representing numbers larger than 9, the location, or place, of a digit determines how much it represents. For example, in the number \(123\) the digit 1 represents a hundred while the digit 2 represents twenty. Therefore, the decimal number 123 can be rewritten in the following way.
\(123 = 1 \cdot 100 + 2 \cdot 10 + 3 \cdot 1\)
Note that the multipliers in the above equation can be rewritten using exponents as follows:
\(123 = 1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0\)
This equation is useful because it makes it clear how the base, 10, is expressed in this definition of a decimal number.
Bits
In binary numbers, a bit is a single symbol, 0 or 1. Binary numbers require multiple digits to represent numbers larger than 1. When representing numbers larger than 1, the location, or place, of a bit determines how much it represents. Just as with decimal numbers, binary numbers can be rewritten using an equation that utilizes multipliers of the base, 2, raised to sequentially decreasing powers. For example, the binary number \(101\) can be rewritten in the following way.
\(101 = 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0\)
Note that in the right side of the above equation all numbers are in decimal. Therefore, the decimal value of the binary number \(101\) can be computed by evaluating the right side of the above equation.
\(101 = 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0\)
\(101 = 1 \times 4 + 0 \times 2 + 1 \times 1\)
\(101 = 4 + 0 + 1\)
\(101 = 5\)
The above equation can be generalized to convert any positive integer in binary to decimal.
\(bit_0 \times 2^0 + bit_1 \times 2^1 + ... + bit_{n-1} \times 2^{n-1}\)
Note that the bits in a binary number are indexed from right to left from \(0\) to \(n - 1\)
Decimal to Binary
Converting a number from binary to decimal is the sum of a series of powers of two. Converting a number from decimal to binary can be accomplished by finding the unique powers of two that sum to the decimal number from largest to smallest. Another more algorithmic way of converting decimal numbers to binary is as follows.
- The remainder of the decimal number divided by two is a bit in the binary number.
- The decimal number is changed to the floor of half the decimal number.
- If the decimal number is greater than 0, go back to step 1.
- The bits generated in step 1 from right to left are the equivalent binary number.
For example, the decimal number \(123\) would be converted to binary using this algorithm as follows:
\(123 / 2 = 61\) remainder \(1\)
\(61 / 2 = 30\) remainder \(1\)
\(30 / 2 = 15\) remainder \(0\)
\(15 / 2 = 7\) remainder \(1\)
\(7 / 2 = 3\) remainder \(1\)
\(3 / 2 = 1\) remainder \(1\)
\(1 / 2 = 0\) remainder \(1\)
Therefore, the decimal number \(123\) is equal to the binary number \(1111011\). This can be verified by converting the binary number \(1111011\) to decimal.
\(1111011 = 1 \times 2^6 + 1 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0\)
\(1111011 = 1 \times 64 + 1 \times 32 + 1 \times 16 + 1 \times 8 + 0 \times 4 + 1 \times 2 + 1 \times 1\)
\(1111011 = 64 + 32 + 16 + 8 + 2 + 1\)
\(1111011 = 123\)
Signed Binary
The leftmost bit in the representation of a signed integer is always the sign bit. A sign bit of 0 indicates a positive number; a sign bit of 1 indicates a negative number. There are several different schemes for representing negative numbers. The first that may come to mind is to find the base two representation of the absolute value of the number then put a 1 in the sign bit if the number is negative. Thus, the number -89 on a 16-bit machine would be represented as 1000000001011001 (89 is 1011001 in base 2). This is called the sign and magnitude representation of the number. While it seems straightforward it really isn’t the best scheme. The problem comes in performing addition and subtraction on such numbers. Remember all the rules about adding signed numbers? There would need to be lots of tests of the sign bits to determine if the numbers were the same sign or not, then if they weren’t a test would need to be done to determine which number was larger in absolute value. Too much work!! A much better representation scheme, and the most common one, is called two’s complement. Two’s complement representation uses an idea fundamental to basic arithmetic: the sum of a number and its negative is 0. In computer arithmetic, the sum of the two’s complement representation of a number and the two’s complement representation of its negative is 0 (in the computer).
The n-bit two’s complement representation of a positive integer is the base 2 representation of the integer with 0s added to the left to give a total of n-bits.
Example: To find the 10-bit two’s complement representation of 52 (base 10), first convert 52 to base 2 (you get 110100) then fill out on the left with 0’s to get a 10-bit number. So the 10-bit two’s complement representation of 52 is 0000110100.
The n-bit two’s complement representation of a negative integer is based on two basic properties: the way computers add and the fact that -x (negative x) is the number you must add to x to get 0 (if x is 3, then -x is -3 because 3 + (-3) = 0 and if x is -4 then -x is 4 because -4 + 4 = 0).
Observe that if a 10-bit computer adds 0000110100 and 1111001100 it gets 0…
0 0 0 0 1 1 0 1 0 0 (52)
+ 1 1 1 1 0 0 1 1 0 0
-------------------
0 0 0 0 0 0 0 0 0 0The 1 carried out of the leftmost bit is dropped - there is no room for it in 10 bits so the result is just 0. Thus the bit pattern 1111001100 is the 10-bit two’s complement representation of -52.
Now we need to see where this comes from. One way to look at it is to think about how we add: we start on the right, adding bits and, if necessary, carrying to the next position to the left. So, if we start with one bit pattern (a number!) and want to find the two’s complement representation of the negation of the number we just figure out what bit pattern added to the first one will give 0.
To find the n-bit two’s complement representation of -m (where m is positive):
- Find the base 2 (binary) representation of m.
- Add the appropriate number of 0s to the left to get n bits total.
- Complement each bit to the left of the rightmost 1. (Complement means change 0 to 1 and 1 to 0).
If you take the two’s complement bit pattern of any integer (positive or negative) and complement each bit to the left of the rightmost 1, you get the negation of the integer. For example, if we start with 1111001100 (which is -52) and complement each bit to the left of the rightmost 1 we get 0000110100 (which is 52 - the negation of -52).
Fixed Point
In decimal, real numbers are numbers that can be represented, not always precisely, with numbers that contain a decimal place. For example, the number \(1/4\) is a real number that can be represented exactly by \(0.25\). The number \(\pi\), however, can only be approximated with a finite number of digits such as \(3.14159\). The decimal place signifies how much each of the digits in a number represent. For example, in the number \(12.34\) the 1 represents ten because it is two places to the left of the decimal place and the 3 represents three tenths because it is immediately to the right of the decimal place. Therefore, the decimal number \(12.34\) can be rewritten in the following way.
\(12.34 = 1 \cdot 10 + 2 \cdot 1 + 3 \cdot 1 / 10 + 4 \cdot 1 / 100\)
Note that the multipliers in the above equation can be rewritten using exponents as follows:
\(12.34 = 1 \times 10^1 + 2 \times 10^0 + 3 \times 10^{-1} + 4 \times 10^{-2}\)
In binary, real numbers are numbers that can be represented with numbers that contain a binary point. For example, the binary number \(10.01\) is a real number. Just as with decimal real numbers, binary real numbers can be rewritten using an equation that utilizes multipliers of powers of 2. For example, the binary number \(10.01\) can be rewritten in the following way.
\(10.01 = 1 \times 2^1 + 0 \times 2^0 + 0 \times 2^{-1} + 1 \times 2^{-2}\)
All of the numbers on the right side of the above equation are decimal numbers, therefore, the decimal value of the binary number \(10.01\) can be computed by evaluating the right side of the above equation.
\(10.01 = 1 \times 2^1 + 0 \times 2^0 + 0 \times 2^{-1} + 1 \times 2^{-2}\)
\(10.01 = 1 \times 2^1 + 0 \times 2^0 + 0 \times 1 / 2^1 + 1 \times 1 / 2^2\)
\(10.01 = 1 \times 2 + 0 \times 1 + 0 \times 1 / 2 + 1 \times 1 / 4\)
\(10.01 = 2 + 0 + 0 + 1 / 4\)
\(10.01 = 2.25\)
A practical consequence of using a decimal point to represent real numbers is that not all real numbers can be represented exactly. The number \(1/3\), for example, can not be represented with a finite number of decimal places because only numbers that are a sum of powers of 10 can be represented exactly. The number \(1/3\) must be approximated with a number such as \(0.33333333333\). Binary numbers can only represent numbers that are a sum of powers of 2. As a consequence, there are real numbers that can be represented exactly in decimal that must be approximated in binary, such as the decimal number \(0.1\). The decimal number \(0.1\) can be approximated by the binary number \(0.00011001100110011\) which is equivalent to the decimal number \(0.9999847412\).
Floating Point
Representing very large or small numbers using decimal points can be tedious. Scientific notation utilizes powers of 10 to to simplify these numbers. For example \(1200000000000\), is written as \(1.2 \times 10^12\) in scientific notation. This same approach can be used with binary, but is instead called floating point representation, because the binary point floats to different locations depending on the exponent. The fixed point binary number \(1000000000000000.0\) is equivalent to the floating point number \(1.0 \times 10^1111\). The binary number \(1.0 \times 10^1111\) can be converted to decimal in two different ways. The first is to convert all the binary numbers to decimal and then evaluate the equations. For example:
\(1.0 \times 10^1111 = 1.0 \times 10^1111\)
\(1.0 \times 10^1111 = 1.0 \times 2^15\)
\(1.0 \times 10^1111 = 1.0 \times 32768\)
\(1.0 \times 10^1111 = 32768.0\)
The second way to convert binary number to decimal is to shift the binary place by the number of times specified by the exponent and covert the resulting fixed point binary number to decimal. For example.
\(1.0 \times 10^1111 = 1.0 \times 10^1111\)
\(1.0 \times 10^1111 = 1000000000000000.0\)
\(1.0 \times 10^1111 = 32768.0\)
Computers often use floating point numbers to represent real numbers because they can represent a larger range of values with the same number of bits. For example the largest number that can be represented with a 64-bit fixed point number is approximately \(10^18\). The largest number that can be represented with a 64-bit floating point number is approximately \(10^308\).
Floating point numbers can not, however, represent more numbers than fixed point numbers with the same number of bits. This is because there are \(2^64\) different permutations of 64 bits, and each permutation represents a number in floating point and in fixed point. As a result, floating point numbers have a limited number of significant digits. For example a 64-bit number with a 11 bit exponent has 53 bits to represent the significant digits. A 53-bit number can only represent \(9.0 \times 10^15\) different values, which means the 64-bit floating point number has 15 significant digits. This means that the number \(1234567890123456.0\), which has 16 significant digits, can not be represented with a 64-bit binary number even though it is well below the maximum value of \(10^308\).