Representing
Binary Numbers
(revised
01/28/2008)
Decimal versus Binary Notation:
In decimal notation there are ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 which are to represent the quantities zero thru nine. In binary notation there are only two digits, 0 and 1. Larger quantities are represented using positional notation where the position of a digit determines its weight or value as a power of the base.
For example, using decimal positional notation
1432 = 1 x 10 3 + 4 x 10 2
+ 3 x 10 1 + 2 x 10 0
where the weight or value given to each digit is a power of 10. The powers of 10 begin with 10 0 (one) on the right and increase moving to the left (10 1 = tens, 10 2 = hundreds, 10 3 = thousands etc).
With binary notation, the weight of each bit (bit is contraction of binary digit) is a power of two.
For example
10111 = 1 x 2 4 + 0 x 2 3
+ 1 x 2 2 + 1 x 2 1
+ 1 x 2 0 = 16 + 4 + 2 + 1 = 23
Converting Binary to Decimal: Adding Powers of Two
A simple technique for converting binary to decimal is to rewrite the binary expression in terms of powers of two then add the terms. Starting from the right most bit, the weight of each bit is 1, 2, 4, 8, etc doubling the value for each bit.
Example: Convert 01011011 to decimal
01011011 = 0 x 128 + 1 x 64 + 0 x 32 + 1 x 16
+ 1 x 8 + 0 x 4 + 1 x 2 + 1 x 1 = 64 + 16 + 8 + 2 + 1 = 91
Converting Decimal To Binary: Subtracting Powers of Two
The technique for converting binary to decimal can be "reversed" to obtain a technique for converting decimal to binary. The idea is to subtract out powers of two from the decimal expansion while keeping track of which powers of two can be subtracted out.
Do the following
1. List the powers of two right to left until you reach the first power of two that exceeds the decimal number being converted.
2. Put a 0 over the first power of two that exceeds the decimal number (indicating that the decimal value is too small to contain this power of two). The next lower power of two (to the right) will be smaller than the decimal value. Put a 1 over this power of two and subtract the power of two from the decimal value.
3. Move right to the next smaller power of two. If this value is larger than the remainder, put a 0 it; otherwise put a 1 over the power of two and subtract it from the reminder.
4. Continue until all powers of two have a 0 or 1 over them. This binary integer equals the decimal number
Example: Convert 91 to binary
1. First we list the powers of two right to left until we exceed 91 (128 > 91). Put a 0 over 128
0
128 64
32 16 8
4 2 1
2. Since 64 is less than 91 we put a 1 over the 64 and subtract it from 91
0 1
128 64
32 16 8
4 2 1
91 - 64 = 27
3. Continue with the remainder 27. Since 32 is larger than 27, it gets a 0. 16 is less than 27 so we put a 1 over the 16 and subtract it from 27
0 1
0 1
128 64 32
16 8 4
2 1
27
- 16 = 11
4. Continue. From 11 we can subtract 8, 2, and 1.
0 1 0
1 1
0 1 1
128 64 32
16 8 4
2 1
11
- 8 = 3; 3 - 2
= 1; 1 - 1 = 0
Therefore 01011011 binary equals 91 decimal. You can check your work by using addition of powers of two to convert 01011011 to 91 decimal.
Converting Decimal to Binary Using Integer Division
An alternate method to convert decimal to binary is to divide the decimal number by 2 getting the quotient and remainder (which will be 0 or 1). Repeat with the quotient, again dividing by 2 to get the quotient and remainder (0 or 1) until the quotient is 0. The remainders give you the binary representation in reverse order
Example: Convert 91 decimal to binary
91 / 2 = 45 r 1
45 / 2 = 22 r 1
22 / 2 = 11 r 0
11
/ 2 = 5 r 1
5 / 2 = 2 r 1
2 / 2 = 1 r 0
1 / 2 = 0 r 1
Therefore 91 decimal = 1011011 binary
Hexadecimal Numbers
Binary numbers are awkward to use because many "bits" (a contraction
of BInary digiT) are needed
to represent even small values. Consequently octal (base 8) and hexadecimal
(base 16) notation is used because it's easy to convert these notations into
binary and back.
Hexadecimal notation or base 16 needs 16 digits (decimal has only ten: 0 -
9). We use 0 through 9 to represent the values zero nine but to represent the
values ten through fifteen we use the letters A (ten), B (eleven), C (twelve),
D (thirteen), E, (fourteen) and F (fifteen). Hexadecimal 10 (written as 10h
with a post-fixed h or 0x10 a prefixed 0x) equals 1 x 161 + 0 x 160
= sixteen!
Therefore to count from 1 to 0x10 in hexadecimal we count 0, 1, 2, 3, 4, 5, 6,
7, 8, 9, A, B, C, D, E, F, 0x10!
Using positional notation it's easy to convert from hexadecimal to decimal -
just expand by powers of 16 remembering that the digits A through F have
decimal value 10 through 15
Example
0xACE = A x 162 + C x 161
+ E x 160 = 10 x 256 + 12 x 16 + 14 x 1 = 2766
Converting decimal to hexadecimal can be done by subtracting out multiple
powers of 16 in a manner similar to subtracting non-multiple powers
of 2 to convert decimal to binary
The real advantage to hexadecimal notation is the ease which one can convert it
to and from binary using the "Rule of Four".
Rule
of Four: Any
hexadecimal digit can be converted to a four bit binary number and any four bit
binary number can be converted to a hexadecimal digit using the following
table.
0 0000
4 0100
8 1000
C 1100
1 0001
5 0101
9 1001
D 1101
2 0010
6 0110
A 1010
E 1110
3 0011
7 0111
B 1011
F 1111
There is a pattern here - do you see it? Hint: The positional values for the
four bits are 8, 4, 2, 1.
Examples:
0xACE = 1010 1100 1110
0100 1101 1001 = 0x4D9
Since decimal to binary conversions are easily done by subtracting powers of
two and binary to hexadecimal conversions are easily done using the Rule of
Four, these methods are combined to convert decimal to hexadecimal
Representing Binary Integers on the Computer
The units of storage (memory cells) in a computer's main memory are fixed length, usually 8 bits which by definition equals one byte. Thus all binary integers are at least 8 bits long. For example, 00000000 is zero , 00000001 is one, 00000010 is two, 00000011 is three, 00000100 is four etc. A good exercise is to be able to "count" in binary from 0 to 10 (00001010 is 10 decimal).
Eight bits does not allows for very large integers (11111111 is 255 - why?) so generally multiple bytes are used to store an integer. Some computers use 16-bit integers (2 bytes) which allows a range of values from 0 and 65,535. Others use 32-bit integers (4 bytes) for a range of 0 to 4,294,967,295.
Binary Arithmetic - Addition
Binary arithmetic, particularly binary addition is very simple: there are only four rules, one of which results in a carry out to the left
0 0 1 1
+0 +1
+0 +1
-- --
-- --
0
1 1 10
<- note the carry out
However, if there is a carry in from the right, we need to consider four more rules
+1
+1 +1 +1
<- carry in from right
0 0 1 1
+0 +1
+0 +1
-- --
-- --
1
10 10 11
Observe that in three of the four cases where there is a carry in from the right, there is a carry out to the left. In summary eight rules are needed for binary addition!
Binary Arithmetic – Subtraction, Multiplication, Division
Once you see binary addition, you can figure out the eight rules for binary subtraction. Instead of carry in from the right and carry outs to the left, you have borrows from the right and borrows to the left; this makes binary subtraction complicated.
Binary multiplication has only four rules
0 0 1 1
×0 ×1
×0 ×1
-- --
-- --
0 0 0 1
And as for division, see if you can figure this one out (17 divided by 5 is 3 remainder 2)
11 <- quotient
-------
101 / 10001
- 101
----
111
-101
----
10 <- remainder
Representing Signed Binary Integers – Four Methods:
The above only considered the case of representing unsigned binary integers. There are a number of techniques to represent signed binary integers. We mention four techniques but only consider the details of two. Below are simple four bit examples of the four signed representations being with a four bit unsigned representation example.
Unsigned Representation
Four Bit Example: range 0 to 15
+0
+1 +2 +3
+4 +5 +6
+7 +8 +9
+10 +11 +12
+13 +14 +15
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
1101 1110 1111
Sign-Magnitude: Here the left most bit is used for the sign (0 for positive, 1 for negative) and the other bits represent the magnitude. Note how the positive representations for integers are the same as the unsigned representations above. This is true for three of the four signed representations.
Four Bit Example: range -7 to +7; note two zeros
-7
-6 -5 -4
-3 -2 -1
-0 +0 +1
+2 +3 +4
+5 +6 +7
1111
1110 1101 1100 1011 1010 1001 1000 0000 0001 0010 0011 0100 0101 0110 0111
Two’s Complement: Like sign-magnitude, the left most bit is also used for the sign but unlike sign-magnitude, it actually has a negative value or weight. This is the most common technique used today to represent signed binary integers.
Four Bit Example: range -8 to +7; weight of left most (sign) bit is -23 = -8
-8
-7 -6 -5 -4
-3 -2 -1
+0 +1 +2
+3 +4 +5
+6 +7
1000
1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111
One’s Complement: Here a negative number is indicated by complementing all the bits (i.e. 0 becomes a 1 and a 1 becomes a 0). Like sign-magnitude and two’s complement representation, if the left most bit is 1, the number is negative; if it’s 0 it’s positive. One’s complement is seldom used anymore
Four Bit Example: range -7 to +7; note two zeros; each negative representation is the binary complement of its positive representation
-7
-6 -5 -4
-3 -2 -1
-0 +0 +1
+2 +3 +4
+5 +6 +7
1000
1001 1010 1011 1100 1101 1001 1111 0000 0001 0010 0011 0100 0101 0110 0111
Biased Representation: Here an offset (bias) is added to obtain the representation.
Four Bit Excess 0111 Example: range -7 to +8. The representations for the positive integers are different from the unsigned representations.
-7
-6 -5 -4
-3 -2 -1
+0 +1 +2
+3 +4 +5
+6 +7 +8
0000
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Signed Binary Integers - Sign Magnitude Notation
One method to represent signed binary integers on the computer is to use the left-most bit to represent the sign of the integer and the remaining bits on the right to represent the magnitude. For the sign, a 1 represents a minus and a 0 represents a plus. Hence -23 would be 10010111 (observe the right most 7 bits, 0010111 is 23). Of course +23 is 00010111.
8-bit signed magnitude binary representation gives a range of -127 (11111111) to +127 (01111111). Remember the left-most bit is the sign bit while the remaining seven bits is the magnitude (verify that 1111111 equals 127 decimal). The major drawback to sign-magnitude notation is the presence of two zeros: 10000000 for -0 and 00000000 for +0.
Signed Binary Integers - Two's Complement Representation
An alternate representation used by most computers to represent signed binary integers is two's complement representation. In two's complement representation the left-most bit (also called the sign-bit) is given a negative weight or value. For example, in an 8-bit number, the weight of the left-most bit is -128, i.e. – (27), while the other bits have the usual positive weights.
Example: 11101001 equals -23. This is easily shown by adding powers of two remembering the left-most bit has negative weight.
11101001 = 1 x -(27)
+ 1 x 2 6 + 1 x 2 5 + 0 x 2 4 + 1 x 2 3
+ 0 x 2 2 + 0 x 2 1 + 1 x 2 0
= -128 + 64 + 32 + 8 + 1 = -23
Example: 00010111 equals +23.
As in sign-magnitude representation, negative integers in two's complement have a 1 as the left most bit; positive integers have a 0 as the left-most bit. Unlike sign-magnitude notation, two's complement numbers have only one zero, 00000000; the representation 10000000 is equal to -128.
One reason twos complement notation is used to represent signed binary integer is that there is a simple "trick" to negate any two's complement integer: complement (or invert) each bit and add 1. That is, convert 0 bits to 1 bits and 1 bits to 0 bits (complement) then add 1 to the result.
Example: Convert 00010111 (+23) to negative 23
00010111 <- +23
11101000 <- complement each bit
+ 1 <- add 1
--------
11101001
<- -23
The technique also converts negative integers to positive integers
Example: Convert 11101001 (-23) to positive 23
11101001 <- -23
00010110 <- complement each bit
1 <- add 1
--------
00010111
<- + 23
A Small Example: 4-Bit Twos Complement Representation
The integer values from -8 to +7 can be represented using 4-bit twos complement
representation. Consider the number line below which starts at -8 and continues
up to +7. Note the bit patterns as the twos complement representations
"increase" from -8 up to +7. Use this we can demonstrate the binary
addition "works" for twos complement representations.
1000 1001 1010 1011 1100 1101 1110
1111 0000 0001 0010 0011 0100
0101 0110 0111
-8 -7 -6 -5 -4 -3 -2 -1 0 1 2
3 4 5 6 7
Since the left-most sign bit has weight -8, it is very easy to convert
between 4-bit twos complement representation and signed decimal values. More
important, it is easy to see that ordinary unsigned binary addition works with
twos complement representation. For example, try adding -3 and +5 and +3 and
-5. Note that in both cases the correct result is obtained!
-3
1101 +3
0011
+5
+0101 +-5 +1011
--- ----
--- -----
0010 = +2
1110 = -2
If we add normally twos complement representation (throwing away the bit
if there is a carry out of the left most bit position which happened in the
first example) we see that unsigned binary addition still works. Subtract can
be done by adding the negative value!
Numbers with Decimal Points - Floating Point Representations
Representing numbers with decimal points (e.g. 5.75) requires a different type of 0/1 encoding. One such encoding is called floating point representation. First we represent the value in binary using a binary point (e.g. 5.75 = 101.11) with bits below the binary point having weights which are negative powers of two (e.g. 2 -1 = halves, 2 -2 = fourths, 2 -3 = eights etc). This is referred to as fixed point notation. Then we shift the binary point so that the binary point to the immediate left of the leading 1 while multiplying by the proper power of two to compensate (e.g. 101.11 = 0.10111 x 2 3 or 0.10111 x 2 11). The string of digits without the binary point (which is implied) is referred to as the fraction (i.e. 10111) while the power of two (e.g. 11) is called the exponent. The fraction and the exponent are stored in separate fields within the floating point representation. Actually it gets a bit more complicated since both the fraction can have a sign (we need to account for +5.75 as well as -5.75) and the exponent can have a sign (0.125 decimal is 0.001 = 0.1 x 2 -2 or 0.1 x 2 -10) .
The process of shifting the binary point and multiplying by a power of two is called normalization. Generally when we normalize a floating point number we shift the binary point so that it is to the immediate left of the leading 1; i.e. 101.11 becomes 0.10111 x 2 11. You can also normalize so that the binary point is to the immediate right of the leading 1; e.g. 101.11 becomes 1.0111 x 2 10. This latter type of normalization (the binary point is to the right of the leading 1) is used by the IEEE 754 standard discussed below.
In summary, floating point representation doesn't look anything like binary integer representation
Floating point representation allows for a larger range of values but there is a precision problem. That is floating point can only store a limited number of significant digits. For example pi is approximated by 3.141592654 to ten significant digits. Standard floating point representation is only good for 7 digits of precision - so it would store pi as 3.141593.
Integers are exact so there is no precision problem.
Example: A Simple 8-Bit Floating Point Representation
To demonstrate how the sign, exponent, and fraction values of a floating point number are "packed" into one or more bytes in memory, consider the following (very unrealistic) 8-bit example. If we number the bits from 0 to 7 from right to left, bit 7 is the sign bit (0 for plus, 1 for minus), bits 4 - 6 are the exponent, and bits 0 - 3 are the fraction.
sign exponent
fraction
|__|__ __ __|__ __ __ __|
7 6 5 4 3 2 1
0
^
assumed
binary point
Hence 5.75 which equals 101.11 = 1.0111 x 2 10 (in this case we normalize by shifting the binary point to the immediate right of the leading 1 following the IEEE 754 standard) would be represented by
sign exponent
fraction
| 0 | 1 0 1 |
0 1 1 1 |
7 6
5 4 3 2 1 0 <- bit number
^
assumed binary
point
0 101 0111
If you've been paying attention might ask, why isn't the representation 0 | 010 | 1011 instead of 0 | 101 | 0111 ?
First the exponent field: To represent positive and negative exponents we use Biased/ Excess 3 (011) notation where we add 011 to the exponent value. Thus 10 + 011 = 101. (Note that if the exponent were -10 then -10 + 011 = 001 for the exponent field).
Next the fraction field: Since the bit above the binary point is always 1, we don't have to store it! So instead of trying to store 1.0111 in the 4 bit fraction field (we'd have to drop the last 1) we just store the fraction bits instead .0111. In this way we get 1 extra bit of precision!
By the way - the largest normalized floating point number we can represent this way is 0 | 111 | 1111 = 1.1111 x 24 = 11111 = 31. The smallest non-zero value is 0 | 001 | 0000 = 1.0000 x 2-2 = 0.01 = 1/4 = 0.25. 0 | 000 | 00000 is reserved for 0.0 - the convention being that an exponent of 000 represents 0. Can you figure out the next smallest and next largest numbers? (Answer: 30 and 0.265625 = 1/4 + 1/64)
How Floating Point Representation is Really Done - IEEE 32-bit Floating Point Representation
The IEEE 754 standard for floating point representation normalizes the number so that the binary point is to the immediate right of the leading 1 bit while adjusting the exponent, then stores the sign, exponent and fraction in that order. "Biased" or "excess notation" is used to represent the signed exponent as a single quantity; extra precision in the fraction is obtained by not storing the 1 bit above the binary point.
A possible 16-bit floating point representation is given below. The left-most bit (bit15) stores the sign of the fraction. Next comes the exponent (bits 9 - 14) using excess 011111 notation. Finally the fraction is stored in bits 0 - 8. Since the leading 1 bit above the binary point is not stored, 10 bits of precision is obtained (about 3 decimal digits).
sign
exponent
fraction
|__ |__ __ __ __ __ __|__
__ __ __ __ __ __ __ __|
15 14 13 12
11 10 9 8 7 6 5 4 3 2
1 0 <- bit number
^
assumed binary point
16 bits is too small to represent a floating point number with any degree of precision so we use a 32-bit representation. Numbering the bits right to left from 0 to 31 we have the following format
sign
exponent
fraction
|
|__ __ __ __ __ __ __ __|__ __ __ __ ... __ __ __ __ __|
31 30 29 28 27 26
25 24 23 22 21 20 19 ... 4 3 2 1 0
<- bit number
^
assumed binary point
where the exponent biased by 01111111. Thus 101.11 is represented by 0 10000001 01110000000000000000000. There is also a 64-bit representation for floating point number is referred to a type double since at 64 bits, it’s double the length of the 32-bit float type,.
Characters and ASCII Codes
Characters, things like 'A', 'z', '+', or '2' (digits) are encoded using a standard code called ASCII (American Standard Code for Information Interchange). ASCII codes are 8 bits (1 byte) long. We refer to the ASCII codes for characters by their corresponding integer values. For example, the pattern 01000001 is the ASCII code for 'A'. Since 01000001 is the binary integer 65 (check this out yourself), we say ASCII code 65 is 'A'
The ASCII codes from 0 to 31 are technically "non-printable" characters. For example, ASCII code 13 (00001101) is a "carriage return", the character used for the (Enter) key. ASCII 27 (00011011) is the (Esc) key. ASCII code 0 (00000000) is called the Null Character.
Beginning at ASCII 32 (00100000) a blank, the codes up to 127 are standardized and printable. For example
ASCII codes 48 (00110000) thru 57 (00111001) are the digits '0' through '9'
'0' is 48 '1' is 49 '2' is
50 '3' is 51 '4' is 52
'5' is 53 '6' is 54 '7' is
55 '8' is 56 '9' is 57
ASCII codes 65 (01000001) thru 90 (01011010) are the capital letters 'A' through 'Z'
'A' is 65 'B' is 66 'C' is 67 'D' is 68 'E' is 69 ...
'U' is 85 'V' is 86 'W' is 87 'X' is 88 'Y' is 89 'Z' is 90
ASCII codes 97 (01100001) thru 122 (01111010) are the lower case letters 'a' through 'z'
'a' is 97 'b' is 98 'c' is 99 'd' is 100 'e' is 101 ...etc
Special symbols like '+', '=', '}' etc are found between the codes for digits, capital letters and lower case letters
ASCII codes
128 - 255 are non-standard.
Integer, Signed Integer, Floating Point, ASCII codes - How does the computer keep them straight?
In one word - it doesn't. The hardware of the computer cannot distinguish between integer, floating point and ASCII codes. To the computer it's all strings of 0's and 1's. The software distinguishes between the different types. That's the programmer’s responsibility!
Why Binary? Simple! Electronic components that can maintain one of two states (off/on, low voltage/high voltage, 0/1) are inexpensive and reliable (very reliable). While it is possible to build electronic circuits that maintain one of ten states (some early computer were decimal machines), such circuits are very expensive and might not be reliable. This is especially important for circuits that make up the computer's main memory. The circuits must be inexpensive (since a lot of memory is needed to store information) and reliable (you don't want the computer losing information).
For a more complete description of this material you may view the .pdf file The
Representation of Number on the Computer - Brief Version.