Transcript Presentation

WEEK 4
ET2640
Logic and Numerical Methods
ET2640
1
Tokens in C
• String Literals
– A sequence of characters enclosed in double quotes as
“…”. For example “13” is a string literal and not number 13.
‘a’ and “a” are different.
• Operators
– Arithmetic operators like +, -, *, / ,% etc.
– Logical operators like ||, &&, ! etc. and so on.
• White Spaces
– Spaces, new lines, tabs, comments ( A sequence of
characters enclosed in /* and */ ) etc. These are used to
separate the adjacent identifiers, kewords and constants.
ET2640
2
Basic Data Types
• Integral Types
– Integers are stored in various sizes. They can
be signed or unsigned.
– Example
Suppose an integer is represented by a byte
(8 bits). Leftmost bit is sign bit. If the sign bit
is 0, the number is treated as positive.
Bit pattern 01001011 = 75 (decimal).
7–
The
largest
positive
number
is
01111111
=
2
ET2640
3
1 = 127.
Basic Data Types
• Integral Types
– char
255.
Stored as 8 bits. Unsigned 0 to
Signed -128 to 127.
– short int
Stored as 16 bits. Unsigned
0 to 65535.
Signed -32768 to 32767.
– int
Same as either short or long int.
– long int
Stored as 32 bits. Unsigned
ET2640
4
0 to 4294967295.
Basic Data Types
• Floating Point Numbers
– Floating point numbers are rational numbers.
Always signed numbers.
– floatApproximate precision of 6 decimal
digits .
• Typically stored in 4 bytes with 24 bits of signed
mantissa and 8 bits of signed exponent.
– double
Approximate precision of 14
decimal digits.
ET2640
• Typically stored in 8 bytes with 56 bits of signed
mantissa and 8 bits of5 signed exponent.
Constants
• Numerical Constants
– Constants like 12, 253 are stored as int type. No decimal
point.
– 12L or 12l are stored as long int.
– 12U or 12u are stored as unsigned int.
– 12UL or 12ul are stored as unsigned long int.
– Numbers with a decimal point (12.34) are stored as double.
– Numbers with exponent (12e-3 = 12 x 10-3 ) are stored as
double.
– 12.34f or 1.234e1f are stored as float.
– These are not valid constants:
25,000 7.1e 4
ET2640
$200
2.3e-3.4 etc.
6
Constants
Character and string constants
– ‘c’ , a single character in single quotes are stored as char.
Some special character are represented as two characters in single
quotes.
‘\n’ = newline, ‘\t’= tab, ‘\\’ = backlash, ‘\”’ = double quotes.
Char constants also can be written in terms of their ASCII code.
‘\060’ = ‘0’ (Decimal code is 48).
– A sequence of characters enclosed in double quotes is called a string
constant or string literal. For example
“Charu”
“A”
“3/9”
“x = 5”
ET2640
7
Variables
Naming a Variable
–
–
–
–
–
–
–
–
Must be a valid identifier.
Must not be a keyword
Names are case sensitive.
Variables are identified by only first 32 characters.
Library commonly uses names beginning with _.
Naming Styles: Uppercase style and Underscore style
lowerLimit lower_limit
incomeTax
income_tax
ET2640
8
Declarations
• Declaring a Variable
– Each variable used must be declared.
– A form of a declaration statement is
data-type var1, var2,…;
– Declaration announces the data type of a variable and allocates
appropriate memory location. No initial value (like 0 for integers) should be
assumed.
– It is possible to assign an initial value to a variable in the declaration itself.
data-type var = expression;
– Examples
int sum = 0;
char newLine = ‘\n’;
float epsilon = 1.0e-6;
ET2640
9
Global and Local Variables
• Global Variables
– These variables are
declared outside all
functions.
– Life time of a global
variable is the entire
execution period of the
program.
– Can be accessed by any
function defined below
the declaration, in a
file.
/* Compute Area and Perimeter of a circle
*/
#include <stdio.h>
float pi = 3.14159; /* Global */
main() {
float rad;
/* Local */
printf( “Enter the radius “ );
scanf(“%f” , &rad);
if ( rad > 0.0 ) {
float area = pi * rad * rad;
float peri = 2 * pi * rad;
printf( “Area = %f\n” , area );
printf( “Peri = %f\n” , peri );
}
else
printf( “Negative radius\n”);
printf( “Area = %f\n” , area );
}
ET2640
10
Global and Local Variables
/* Compute Area and Perimeter of a circle
*/
#include <stdio.h>
float pi = 3.14159; /* Global */
Local Variables
– These variables are
declared inside some
functions.
– Life time of a local
variable is the entire
execution period of the
function in which it is
defined.
– Cannot be accessed by any
other function.
– In general variables
declared inside a block
are accessible only in
that block.
main() {
float rad;
/* Local */
printf( “Enter the radius “ );
scanf(“%f” , &rad);
if ( rad > 0.0 ) {
float area = pi * rad * rad;
float peri = 2 * pi * rad;
printf( “Area = %f\n” , area );
printf( “Peri = %f\n” , peri );
}
else
printf( “Negative radius\n”);
printf( “Area = %f\n” , area );}
ET2640
11
PRECEDENCDE OF OPERATORS
OPERATOR
DESCRIPTION
ASSOCATIVITY
RANK
()
Function call
Left-to-right
1
[]
Array Element Call
Left-to-right
1
+
Plus
Right-to-left
2
-
Minus
Right-to-left
2
++
Increment
Right-to-left
2
--
Decrement
Right-to-left
2
!
Logical negation
Right-to-left
2
-
Ones Compliment
Right-to-left
2
*
Pointer
reference(indirection)
Right-to-left
2
&
Address
Right-to-left
2
Sizeof
Size of object
Right-to-left
2
(type)
Type cast conversion
Right-to-left
2
*
Multiplication
Left-to-right
3
/
Division
Left-to-right
3
%
Modulus
Left-to-right
3
Precedence and Order of Operations
Operat Descriptions
or
ET2640
<<
Shift Left
>>
Shift Right
<
Less than
<=
Less than or equal to
>
Greater than
>=
Great than or equal to
==
Equality
!=
Not equality
&
Bitwise AND
*
Bitwise XOR
|
Bitwise OR
&&
Logical AND
||
Logical OR
?:
Conditional Expression
13
Operators
• Arithmetic Operators
– +, - , *, / and the modulus operator %.
– + and – have the same precedence and associate left to right.
3 – 5 + 7 = ( 3 – 5 ) + 7  3 – ( 5 + 7 )
3 + 7 – 5 + 2 = ( ( 3 + 7 ) – 5 ) + 2
– *, /, % have the same precedence and associate left to right.
– The +, - group has lower precendence than the *, / % group.
3 – 5 * 7 / 8 + 6 / 2
3 – 35 / 8 + 6 / 2
3 – 4.375 + 6 / 2
3 – 4.375 + 3
-1.375 + 3
1.625
ET2640
14
Operators
• Arithmetic Operators
– % is a modulus operator. x % y results in the
remainder when x is divided by y and is zero
when x is divisible by y.
– Cannot be applied to float or double variables.
– Example
if ( num % 2 == 0 )
printf(“%d is an even number\n”, num)’;
else
ET2640
printf(“%d is an odd number\n”, num);
15
Type Conversions
– The operands of a binary operator must have a the same type
and the result is also of the same type.
– Integer division:
c = (9 / 5)*(f - 32)
The operands of the division are both int and hence the result also
would be int. For correct results, one may write
c = (9.0 / 5.0)*(f - 32)
– In case the two operands of a binary operator are different, but
compatible, then they are converted to the same type by the
compiler. The mechanism (set of rules) is called Automatic Type
Casting.
c = (9.0 / 5)*(f - 32)
– It is possible to force a conversion of an operand. This is called
Explicit Type casting.
c = ((float) 9 / 5)*(f - 32)
ET2640
16
Automatic Type Casting
Hierarchy
1. char and short operands are converted to
int
2. Lower data types are converted to the
higher data types and result is of higher
type.
3. The conversions between unsigned and
signed types may not yield intuitive results.
4. Example
float f; double d; long l;
int i; short s;
d + f f will be converted to double
i / s s will be converted to int
l / i i is converted to long; long result
ET2640
17
Double
float
long
Int
Short and
char
Explicit Type Casting
– The general form of a type casting operator is
– (type-name) expression
– It is generally a good practice to use explicit casts than to
rely on automatic type conversions.
– Example
C = (float)9 / 5 * ( f – 32 )
– float to int conversion causes truncation of fractional
part
– double to float conversion causes rounding of digits
– long int to int causes dropping of the higher order
bits.
ET2640
18
Binary Arithmetic
•
•
•
•
Binary addition
Binary subtraction
Binary multiplication
Binary division
ET2640
19
Complements of Binary
Numbers
• 1’s complements
• 2’s complements
ET2640
20
Complements of Binary
Numbers
• 1’s complement
• Change all 1s to 0s and all 0s to 1s
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
ET2640
21
Complements of Binary
Numbers
• 2’s complement
• Find 1’s complement and then add 1
1
1’s complement
2’s complement 0
0
0
1
1
1
0
1
0
1
0
1
0
1
Input bits
Adder
Output bits (sum)
0
1
ET2640
0
1
0
0
1
1
Carry
In
1
(add 1)
0
22
Signed Numbers
ET2640
23
Topics for Signed Numbers
• Signed-magnitude form
• 1’s and 2’s complement form
• Decimal value of signed numbers
(How to convert)
• Range of values (max and min)
• Floating-point numbers
ET2640
24
Signed Numbers
• Signed-magnitude form
– The sign bit is the left-most bit in a signed
binary number
– A 0 sign bit indicates a positive magnitude
– A 1 sign bit indicates a negative magnitude
ET2640
25
Signed Numbers
• 1’s complement form
– A negative value is the 1’s complement of
the corresponding positive value
• 2’s complement form
– A negative value is the 2’s complement of
the corresponding positive value
ET2640
26
Signed Numbers
• Decimal value of signed numbers
– Sign-magnitude
– 1’s complement
– 2’s complement
ET2640
27
Signed Numbers
• Range of Values
Total combinations = 2n
2’s complement form:
– (2n – 1) to + (2n – 1 – 1)
Range for 8 bit number:
n=8
-(28-1) = -27 = -128
minimum
+(28-1) – 1 = +27 - 1 = +127 maximum
Total combination of numbers is 28 = 256.
ET2640
28
Signed Numbers
Range for 16 bit number:
n = 16
-(216-1) = -215 = -32768
minimum
+(216-1) - 1 = +215 = +32767 maximum
Total combinations is 216 = 65536 (64K)
8 bit examples:
10000000 =
-128
11111111 =
-1
10000001 =
-127
01111111 =
+127
ET2640
29
Signed Numbers
• Floating-point numbers
– Can represent very large or very small numbers
based on scientific notation. Binary point “floats”.
• Two Parts
– Mantissa represents magnitude of number
– Exponent represents number of places that
binary point is to be moved
• Three forms
–
–
–
–
Single-precision (32 bits)
float
Double-precision (64 bits)
double
Extended-precision (80 bits)
long double
Also have Quadruple and Quadruple extended!
ET2640
30
Single Precision
32 bits
S
1 bit
Exponent (E)
8 bits
Mantissa (fraction, F)
23 bits
• IEEE 754 standard
– Mantissa (F) has hidden bit so actually has 24
bits. Gives 7 significant figures.
• 1st bit in mantissa is always a one
– Exponent (E) is biased by 127 called
Excess-127 Notation
• Add 127 to exponent so easier to compare
• Range of exponents is -126 to +128
– Sign (S) bit tells whether number is negative or
ET2640
31
positive
Single Precision
• Example: Convert 577710 to Floating Point
• 1st, convert to binary using divide by 2 method
• 577710 = 10110100100012
• Positive number, so sign bit (S) equals 0.
• 2nd, count number of places to move binary
point
10110100100012 = 1.011010010001 x 212
Add 127 to 12 = 13910 = 100010112
• Mantissa is fractional part, 011010010001
• Finally, put everything together
S
E
0
10001011
F
Fill in with trailing zeroes
ET2640
01101001000100000000000
32
Special Cases
• Zero and infinity are special cases
– Can have +0 or -0 depending on sign bit
– Can also have +∞ or -∞
• Not a Number (NaN)
– if underflow or overflow
Type
Exponent Mantissa
Zeroes
0
0
Denormalized numbers 0
non zero
e
Normalized numbers
1 to 2 − 2 any
Infinities
2 −1
NaNs
2 −1
e
e
ET2640
0
non zero
33
Examples
Type
Exponent
Mantissa
Zero
0000 0000
000 0000 0000 0000 0000 0000
0.0
One
0111 1111
000 0000 0000 0000 0000 0000
1.0
Denormalized
number
0000 0000
100 0000 0000 0000 0000 0000
5.9×10
Large normalized
number
1111 1110
111 1111 1111 1111 1111 1111
3.4×10
Small normalized
number
0000 0001
000 0000 0000 0000 0000 0000
1.18×10
Infinity
1111 1111
000 0000 0000 0000 0000 0000
Infinity
NaN
1111 1111
010 0000 0000 0000 0000 0000
NaN
ET2640
Value
-39
38
-38
34
Double Precision
• Exponent has 11 bits so uses
Excess-1023 Notation
• Mantissa has 53 bits (one hidden)
• 53 bits gives 16 significant figures
ET2640
35
Arithmetic Operations with
Signed Numbers
•
•
•
•
Addition
Subtraction
Multiplication
Division
ET2640
36
Arithmetic Operations with
Signed Numbers
Addition of Signed Numbers
• The parts of an addition function are:
– Augend
– Addend
– Sum
- The first number
- The second number
- The result
Numbers are always added two at a time.
ET2640
37
Arithmetic Operations with
Signed Numbers
Four conditions for adding numbers:
1. Both numbers are positive.
2. A positive number that is larger than a
negative number.
3. A negative number that is larger than
a positive number.
4. Both numbers are negative.
ET2640
38
Arithmetic Operations with
Signed Numbers
Signs for Addition
• When both numbers are positive, the
sum is positive.
• When the larger number is positive and
the smaller is negative, the sum is
positive. The carry is discarded.
ET2640
39
Arithmetic Operations with
Signed Numbers
Signs for Addition
• When the larger number is negative and
the smaller is positive, the sum is
negative (2’s complement form).
• When both numbers are negative, the
sum is negative (2’s complement form).
The carry bit is discarded.
ET2640
40
Examples (8 bit numbers)
• Add 7 and 4 (both positive)
00000111
+00000100
00001011
• Add 15 and -6 (positive > negative)
Discard carry
7
+4
11
00001111
+11111010
1 00001001
15
+ -6
9
00010000
+11101000
11111000
16
+ -24
-8
• Add 16 and -24 (negative > positive)
Sign bit is negative so negative
number in 2’s complement form
• Add -5 and -9 (both negative)
ET2640
Discard carry
11111011
+11110111
1 11110010
-5
+ -9
-14
41
Overflow
• Overflow occurs when number of bits in
sum exceeds number of bits in addend or
augend.
• Overflow is indicated by the wrong sign.
• Occurs only when both numbers are
positive or both numbers are negative
Sign Incorrect
Magnitude Incorrect
01111101
126
+ 00111010
_________
+ 58
____
10110111
183
ET2640
42
Arithmetic Operations with
Signed Numbers
Subtraction of Signed Numbers
• The parts of a subtraction function are:
– Minuend
- The first number
– Subtrahend - The second number
– Difference - The result
Subtraction is addition with the sign of the
subtrahend changed.
ET2640
43
Arithmetic Operations with
Signed Numbers
Subtraction
• The sign of a positive or negative binary
number is changed by taking its 2’s
complement
• To subtract two signed numbers, take
the 2’s complement of the subtrahend
and add. Discard any final carry bit.
ET2640
44
Subtraction Examples
• Find 8 minus 3.
00001000
+11111101
1 00000101
Discard carry
• Find 12 minus -9.
00001100
+00001001
00010101
• Find -25 minus 19.
11100111
+11101101
1 11010100
Discard carry
• Find -120 minus -30.
ET2640
10001000
+00011110
10100110
8
- 3
5
Minuend
Subtrahend
Difference
12
- -9
21
-25
- 19
-44
-120
- -30
-90
45
Arithmetic Operations with
Signed Numbers
Multiplication of Signed Numbers
• The parts of a multiplication function are:
– Multiplicand
– Multiplier
– Product
- First number
- Second number
- Result
Multiplication is equivalent to adding a
number to itself a number of times equal to
the multiplier.
ET2640
46
Arithmetic Operations with
Signed Numbers
There are two methods for multiplication:
• Direct addition
– add multiplicand multiple times equal to the
multiplier
– Can take a long time if multiplier is large
• Partial products
– Similar to long hand multiplication
ET2640
The method of partial products is the most
commonly used.
47
Arithmetic Operations with
Signed Numbers
Multiplication of Signed Numbers
• If the signs are the same, the product is
positive. (+ X + = + or - X - = +)
• If the signs are different, the product is
negative. (+ X - = - or - X + = -)
ET2640
48
Multiplication Example
• Both numbers must be in uncomplemented form
• Multiply 3 by -5.
Opposite signs, so product will be negative.
310 = 000000112
-510 = 111110112
2’s complement of -5
00000101
00000011
X 00000101
00000011
+ 0000000
00000011
+ 000011
00001111
Multiplicand
Multiplier
First partial product
Second partial product
Sum of 1st and 2nd
Third partial product
Sum and Final Product
Final result is negative, so take 2’s complement.
11110001 is the result which in decimal is -15.
ET2640
49
Arithmetic Operations with
Signed Numbers
Division of Signed Numbers
• The parts of a division operation are:
– Dividend
– Divisor
– Quotient
dividend
 quotient
divisor
Division is equivalent to subtracting the
divisor from the dividend a number of
times equal to the quotient.
ET2640
50
Arithmetic Operations with
Signed Numbers
Division of Signed Numbers
• If the signs are the same, the quotient is
positive.
(+ ÷ + = + or - ÷ - = +)
• If the signs are different, the quotient is
negative. (+ ÷ - = - or - ÷ + = -)
ET2640
51
Division Example
• Both numbers must be in uncomplemented form
• Divide 01100100 by 00110010.
Both numbers are positive so
quotient will be positive.
Set the quotient to zero initially.
Subtract the divisor from the
dividend by using 2’s complement
addition. (11001110)
Ignore the carry bit.
Subtract the divisor from the
1st partial remainder using 2’s
complement addition.
quotient: 00000000
01100100
+ 11001110
1 00110010
Dividend
2’s complement of Divisor
First partial remainder
Add 1 to quotient: 00000000 + 1 = 00000001
00110010
+ 11001110
1 00000000
First partial remainder
2’s complement of Divisor
zero remainder
Add 1 to quotient: 00000001 + 1 = 00000010
So final quotient is 00000010 and final remainder is 00000000
Logical, Shift and Rotate
Operations
 A particular bit, or set of bits, within the byte can be set to 1 or 0, depending
on conditions encountered during the execution of a program.
 When so used, these bits are often called "flags".
 Frequently, the programmer must manipulate these individual bits - an
activity sometimes known as "bit twiddling".
 The logical, shift, and rotate operations provide the means for
manipulating the bits.
ET2640
53
Logical OR Rules
OR Operations
• OR Results in 1 if either or both of the
operands are 1.
•
OR Table
0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1
ET2640
54
Logical OR Operation
To perform the OR operation, take one
column at a time and perform the OR
operation using the OR table.
Ex 1:
10010011
OR 0 0 0 0 1 1 1 1
10011111
ET2640
55
Logical OR Examples
Ex 2:
11001001
OR 0 0 0 0 1 0 1 0
11001011
Ex 3:
0111
OR 0 0 1 0
0111
ET2640
56
Logical XOR Rules
XOR Operations
• The exclusive OR. Similar to OR except that
it now gives 0 when both its operands are 1.
Rules.
0
0
1
1
ET2640
XOR
XOR
XOR
XOR
0=0
1=1
0=1
1=0
57
Logical XOR Examples
Ex 1:
Ex 2:
10011001
XOR 0 0 0 0 1 1 1 1
10010110
0111
XOR 0 0 1 0
0101
ET2640
58
Logical AND Rules
AND Operations
• AND yields 1 only if both its operands are 1.
Rules.
0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1
ET2640
59
Logical AND Examples
Ex 1:
11010011
AND 0 0 0 0 1 1 1 1
00000011
Ex 2:
0111
AND 1 0 0 1
0001
ET2640
60
Logical NOT
NOT Operations
• NOT is a separate operator for flipping the bits.
Rules.
NOT 0 = 1
NOT 1 = 0
Example.
NOT 1 0 1 0 = 0 1 0 1
ET2640
61
Shift and Rotate operations
Whereas logical operations allow the
changing of bit values in place,
SHIFT and ROTATE operations allow bits
to be moved left or right without
changing their values.
ET2640
62
Shift Left operation
SHL
SHL (shift left) shifts each bit one place to the left.
The original leftmost bit is lost and a 0 is shifted into
the rightmost position.
Ex 1.
SHL
1101
1 11 01 10 1 0
Ex 2.
SHL
1100
= 1 0 0 0ET2640
=1010
63
Shift Left - Multiple Bits
• SHL # bits means to shift left # times
Ex 1:
SHL 3
10011100
1 0 0 1 01 01 10 10 10 00 00 = 1 1 1 0 0 0 0 0
Ex 2:
SHL 2
11100110
=10011000
ET2640
64
Shift Right operation
SHR
SHR (shift right) shifts each bit one place to
the right. The original rightmost bit is lost and
a 0 is shifted into the leftmost position.
Ex 1.
Ex 2.
SHR 1 0 1 1
0101 1
SHR 0 0 1 1
= 0 0 0 1ET2640
=0101
65
Shift Right – Multiple Bits
• SHR # bits means to shift right # times
Ex 1:
SHR 3
Ex 2:
SHR 2
10011100
00010011 100 =00010011
11100110
=00111001
ET2640
66
Arithmetic Shift Right operation
ASR (retains rightmost sign bit)
Shifts each bit one place to the right. The original
rightmost bit is lost and a the value of the most significant
bit (leftmost bit) is shifted into the new leftmost position.
Ex 1.
ASR 1 0 1 1
1101 1
Ex 2.
=1101
ASR 0 0 1 1
=0001
ET2640
67
Arithmetic Shift Right – Multiple
Bits
• ASR # bits means to arithmetic shift right # times
Ex 1:
ASR 3
Ex 2:
ASR 2
10011100
11110011 100 =11110011
01100110
=00011001
ET2640
68
Rotate Left operation
ROL
ROL (rotate left) shifts each bit one place to the left.
The original leftmost bit is shifted into the rightmost
position. No bits are lost.
Ex 1.
ROL 1 1 0 1
101
Ex 2.
ROL
1
1100
=1001
ET2640
69
Rotate Left – Multiple Bits
• ROL # bits means to rotate left # times
Ex 1:
ROL 3
10011100
=11100100
Ex 2:
ROL 2
11100110
=10011011
ET2640
70
Rotate Right operation
ROR
ROR (rotate right) shifts each bit one place to the right.
The original rightmost bit is shifted into the leftmost
position. No bits are lost.
Ex 1.
ROR 1 0 1 1
1 101
Ex 2.
ROR 0 0 1 1
=1001
ET2640
71
Rotate Right – Multiple Bits
• ROR # bits means to rotate right # times
Ex 1:
ROR 3
10011100
=10010011
Ex 2:
ROR 2 1 1 1 0 0 1 1 0
=10111001
ET2640
72
Hexadecimal Numbers
ET2640
73
Hexadecimal Numbers
• Decimal, binary, and hexadecimal
numbers
• 4 bits is a nibble
• FF16 = 25510
ET2640
74
Hexadecimal Numbers
• Binary-to-hexadecimal conversion
• Hexadecimal-to-decimal conversion
• Decimal-to-hexadecimal conversion
ET2640
75
Hexadecimal Numbers
•
Binary-to-hexadecimal conversion
1. Break the binary number into 4-bit
groups
2. Replace each group with the
hexadecimal equivalent
•
Convert 1100101001010111 to Hex
C
•
A
5
7
= CA5716
Convert 10A416 to binary
0001
0000 1010 0100
ET2640 = 0001000010100100
76
Hexadecimal Numbers
•
Hexadecimal-to-decimal conversion
1. Convert the hexadecimal to groups of 4-bit
binary
2. Convert the binary to decimal
ET2640
77