ECE 190 Lecture 02 January 20, 2011 1 V. Kindratenko Bits and Operations on Bits Lecture Topics - Unsigned and signed integer representations - Conversion between binary and decimal representations - Arithmetic and logical operations on binary numbers - Floating-point data representation - Other representations Lecture materials Textbook Chapter 2 Homework Posted on the course website (http://courses.engr.illinois.edu/ece190/) Due Wednesday January 26 at 5pm in the ECE190 drop box located in the basement of Everitt LabECE 190 Lecture 02 January 20, 2011 2 V. Kindratenko Unsigned and signed integer representations Signed-magnitude - So far we defined a way to write positive (unsigned) integer numbers using 0 and 1 bits, but how about writing negative numbers? o We can use half of the distinct patterns made of k bits to represent positive values and the other half to represent negative values  Example: with 3 bits we can represent integer numbers from -3 to +3; this leaves us with one 3-bit code not assigned  We still need to decide what distinct patterns we should use for representing positive numbers vs. negative numbers o One way, called signed-magnitude, is to use the leading digit to indicate if the number is positive or negative  Positive numbers will have 0 as the leading digit  Negative numbers will have 1 as the leading digit Binary notation Signed magnitude 000 0 001 1 010 2 011 3 100 -0 101 -1 110 -2 111 -3  The largest positive number is this example is 0112=310  The smallest negative number in this notation is 1112=-310  We still are not using one representation efficiently: 1002 1’s complement - Another way to represent both positive and negative integers, called 1’s complement, is based on the idea that all negative numbers can be represented by flipping digits in the positive numbers o Example: 0102=210. 1012=-210 o In this case, we still are not using one representation efficiently: 1112 o This representation was actually used in some early computers, e.g., CDC 6600 Binary notation Signed magnitude 1’s complement 000 0 0 001 1 1 010 2 2 011 3 3 100 -0 -3 101 -1 -2 110 -2 -1 111 -3 -0ECE 190 Lecture 02 January 20, 2011 3 V. Kindratenko 2’s complement The schema that is actually used in today’s computers is called 2’s complement - Positive numbers are represented in a straightforward way, with leading digit set to 0 o With k bits, 2k-1-1 positive numbers (from 1 to 2k-1-1) can be represented this way - The negative integers are represented by counting backward and wrapping around o Example: 1112=-110, 1102=-210,… o The default rule is that all negative numbers have a leading bit set to 1 - Negative numbers are defined in such a way that when added to the positive numbers with the same magnitude, 0 is obtained o This makes implementing digital logic particularly simpler than using any other binary representation Binary notation Signed magnitude 1’s complement 2’s complement 000 0 0 0 001 1 1 1 010 2 2 2 011 3 3 3 100 -0 -3 -4 101 -1 -2 -3 110 -2 -1 -2 111 -3 -0 -1 - With such annotation, using k bits, we can define 2k-1-1 positive numbers, 0, and 2k-1-1 negative numbers, or 2*(2k-1-1) + 1= 2k-1 numbers altogether. What do we do with the unused representation, 1002 in our example? o We note that when we continue counting backward, the next value after 1012=-310 is 1002, and thus it is logical to assume that 1002=-410. - Thus, 2’s complement annotation allows us to define numbers in the range from -(2)k-1 to 2k-1-1 o Example: k=3: the smallest number represented in 2’s complement using 3 bits is -(2)3-1=-410, the largest number is 23-1-1=310. How exactly do we get 2’s complement representation for negative numbers? - Take the positive number A2, flip all its bits (this gives us the complement of A2), and add 1 to the complement of A2; the result is -A2: -A2 = complement(A2)+12 - Example: 2’s complements representation for -1310 o Start with the positive number that has the same magnitude: 1310=011012 o Find its complement by flipping every bit: complement(011012)=100102 o Add 1 to the complement: 100102 + 12 = 100112 o Verify that the number we got is really -1310  This should hold: 1310+(-1310) = 010, let’s verify it: 011012 + 100112 01101 10011 100000ECE 190 Lecture 02 January 20, 2011 4 V. Kindratenko  Note that a carry out of five bits is produced, that is the sum is really 1000002.  This carry out bit is always ignored in 2’s complement representation In mathematics, radix complement is the number which, added to the given n-digit number in radix r, results in r0. When using binary numbers, r=2, thus the name of 2’s complement. 1’s complement is the diminished radix complement for r=2. Relation to C - In C language, integer numbers are stored using 2’s complement representation o Examples of literal values: 2, -5, 128, -10000 o Examples of an expression using integer literal values: 10+20 - C allows the programmer to refer to values symbolically, by name. Such symbol names are called variables - A variable declaration requires variable type and name - To declare a variable of an integer type, we use int keyword o Example: int a; <- we declared a variable of type int; it will be stored in computer memory in 2’s complement representation - unsigned modifier put in front of int keyword can be used to indicate that the leftmost bit should not be treated as a sign bit, instead it should be treated as part of the magnitude o Example: unsigned int b; <- we declared a variable b that will be stored in computer memory using (unsigned) magnitude representation - If unsigned modifier is not used, signed modifier is implied o int a is the same as signed int a - The size of type int (number of bits allocated in computer memory to store a variable of type int) is architecture-dependent. E.g., on a 32-bit architecture, size of int is 32 bits. - C allows to specify types of integer numbers that occupy a pre-defined number of bits in memory. This is done with the help of short and long type modifiers: Type Bytes Bits Range short int 2 16 -(2)15 to 215-1, or -32,768 -> +32,767 unsigned short int 2 16 0 to 216-1, or 0 -> +65,535 long int 4 32 -2,147,483,648 -> +2,147,483,647 unsigned int 4 32 0 -> +4,294,967,295 long long int 8 64 unsigned long long int 8 64 Conversion between binary and decimal representations Binary to decimal