We need to use binary representations for every piece of data. Computers operate on binary values (as a result of being built from transistors).
There are 3 types of data we want to represent:
There are different binary representations for integers. Possible qualities:
While there are many representations, and all have been used at various times for various reasons, the ones surrounded by a * are the representations that we will use extensively.
Virtually all modern computers operate based on 2's complement representation. Why?
Did you notice that both reasons for using 2's complement representation are the same? Almost always, when discussing why something is done the way it is done, the answer is the same: "because it is faster."
the standard binary encoding already given
only 0 and positive values
range: 0 to (2^n) - 1, for n bits
example:
4 bits, values 0 to 15 n=4, 2^4 -1 is 15 binary decimal hex binary decimal hex 0000 0 0 1000 8 8 0001 1 1 1001 9 9 0010 2 2 1010 10 a 0011 3 3 1011 11 b 0100 4 4 1100 12 c 0101 5 5 1101 13 d 0110 6 6 1110 14 e 0111 7 7 1111 15 f
Historically important, and we use this representation to get 2's complement integers.
Now, nobody builds machines that are based on 1's comp. integers. In the past, early computers built by Semour Cray (while at CDC) were based on 1's comp. integers.
Positive integers use the same representation as unsigned.
00000 is 0
00111 is 7, etc.
Negation (finding an additive inverse) is done by taking a bitwise complement of the positive representation.
COMPLEMENT. INVERT. NOT. FLIP. NEGATE.
a logical operation done on a single bit
the complement of 1 is 0.
the complement of 0 is 1.
-1 --> take +1, 00001
complement each bit 11110
that is -1.
don't add or take away any bits.
EXAMPLE:
11100 this must be a negative number.
to find out which, find the additive inverse!
00011 is +3 by sight, so 11100 must be -3
things to notice:
A variation on 1's complement that does not have two representations for 0. This makes the hardware that does arithmetic (addition, really) faster than for the other representations.
a 3-bit example:
bit pattern: 100 101 110 111 000 001 010 011 1's comp: -3 -2 -1 0 0 1 2 3 2's comp.: -4 -3 -2 -1 0 1 2 3
The negative values are all "slid" down by one, eliminating the extra zero representation.
How to get an integer in 2's comp. representation:
use the positive value 00101 (+5)
take the 1's comp. 11010 (-5 in 1's comp)
add 1 + 1
------
11011 (-5 in 2's comp)
To get the additive inverse of a 2's comp integer,
To add 1 without really knowing how to add:
start at LSB, for each bit (working right to left)
while the bit is a 1, change it to a 0.
when a 0 is encountered, change it to a 1 and stop.
All other remaining bits are the same as before.
EXAMPLE:
What decimal value does the two's complement 110011 represent?
It must be a negative number, since the most significant bit (msb)
is a 1. Therefore, find the additive inverse:
110011 (2's comp. ?) 001100 (after taking the 1's complement) + 1 ------ 001101 (2's comp. +13) Therefore, its additive inverse (110011) must be -13.
We'll see how to really do this later, but here's a brief overview.
carry in a b sum carry out
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
a 0011
+b +0001
-- -----
sum 0100
It is really just like we do for decimal!
An integer representation that skews the bit patterns so as to look just like unsigned but actually represent negative numbers.
It represents a range of values (different from unsigned representation) using the unsigned representation. Another way of saying this: biased representation is a re-mapping of the unsigned integers.
visual example (of the re-mapping):
bit pattern: 000 001 010 011 100 101 110 111
unsigned value: 0 1 2 3 4 5 6 7
biased-2 value: -2 -1 0 1 2 3 4 5
This is biased-2. Note the dash character in the name
of this representation. It is not a negative sign.
EXAMPLES:
given 4 bits, we BIAS values by 2**3 (8)
(This choice of bias results in approximately half the
represented values being negative.)
TRUE VALUE to be represented 3 add in the bias +8 ---- unsigned value 11 so the biased-8 representation of the value 3 will be 1011
going the other way, suppose we were given a biased-8 representation as 0110 unsigned 0110 represents 6 subtract out the bias - 8 ---- TRUE VALUE represented -2
On choosing a bias:
The bias chosen is most often based on the number of bits
available for representing an integer. To get an approx.
equal distribution of values above and below 0,
the bias should be
2 ^ (n-1) or (2^(n-1)) - 1
This diagram is a standard one that is used to point out the differences between a bit pattern (a representation), and the values represented by the bit pattern. This version of the number wheel gives all possibilities of 4-bit representations. For each representation, it also gives (in the outer circles) the decimal value represented by the bit pattern. Notice that positive two's complement values are exactly the same as the unsigned values. It is the bit patterns that have a 1 in the most significant bit position where the values represented differ.
How to change an integer with a smaller number of bits into the same integer (same representation) with a larger number of bits.
This is commonly done on some architectures, so it is best to go over it.
by representation:
unsigned: xxxxx --> 000xxxxx
copy the original integer into the LSBs, and put 0's elsewhere
1's and 2's complement: called SIGN EXTENSION.
copy the original integer into the LSBs,
take the MSB of original integer and replicate it elsewhere.
example: 0010101 -> 000 0010101
^ ^^^
11110000 -> 11111111 11110000
^ ^^^^^^^^
Sometimes a value cannot be represented in the limited number of bits allowed. Examples:
unsigned, 3 bits: 8 would require at least 4 bits (1000)
2's comp., 4 bits: 8 would require at least 5 bits (01000)
When a value cannot be represented in the number of bits allowed, we say that overflow has occurred. Overflow occurs when doing arithmetic operations.
example: 3-bit unsigned representation
011 (3)
+ 110 (6)
---------
? (9) it would require 4 bits (1001) to represent
the value 9 in unsigned rep.
| Copyright © Karen Miller, 2006 |