CS计算机代考程序代写 Arithmetic and Logical Operations

Arithmetic and Logical Operations

Midterm syllabus
■
Everything before Floating Point representation
Will announce a more formal syllabus soon
2 sample midterm exams already available on google drive
■
■
CSE 12 Fall 2020
2

Logical Operations
■ Operate on raw bits with 1 = true and 0 = false AND OR NAND NOR XOR XNOR
0
1
1
In2
1
0
1
0
0
1
|
1
1
1
~(&)
1
1
0
0
0
0
1
1
0
0
0
1
CSE 12 Fall 2020
In1
0
0
&
0
0
1
~(|)
1
^
0
~(^)
1
3

Logical Operations
■ “bit-wise” logical operations are done in parallel for corresponding bits
◆ Example & (AND): ★ X = 0011
★ Y = 1010
★ X AND Y = ?
CSE 12 Fall 2020
4

Logical Operations
■ “bit-wise” logical operations are done in parallel for corresponding bits
◆ Example & (AND): ★ X = 0011
★ Y = 1010
★X AND Y =X&Y=0010
CSE 12 Fall 2020
5

Logical Operations
■ “bit-wise” logical operations are done in parallel for corresponding bits
◆ Example (&) Reduction: ★ X = 0011
★&X=?
CSE 12 Fall 2020
6

Logical Operations
■ “bit-wise” logical operations are done in parallel for corresponding bits
◆ Example (&) Reduction: ★ X = 0011
★ & X = 0&0&1&1 = 0
CSE 12 Fall 2020
7

Shifts and Rotates: Logical Right
■ Logical right
• Move bits to the right, same order
• Throw away the bit that pops off the LSB
• Introduce a 0 into the MSB
CSE 12 Fall 2020
8

Shifts and Rotates: Logical Right Example
■ Logical right
• Move bits to the right, same order
• Throw away the bit that pops off the LSB
• Introduce a 0 into the MSB ◆ 00110101
Shift right by 1
CSE 12 Fall 2020
9

Shifts and Rotates: Logical Right Example
■ Logical right
• Move bits to the right, same order
• Throw away the bit that pops off the LSB
• Introduce a 0 into the MSB ◆ 00110101
◆
CSE 12 Fall 2020
00110101
10

Shifts and Rotates: Logical Right Example
■ Logical right
• Move bits to the right, same order
• Throw away the bit that pops off the LSB
• Introduce a 0 into the MSB ◆ 00110101
◆ 00110101
CSE 12 Fall 2020
11

Shifts and Rotates: Logical Right Example
■ Logical right
• Move bits to the right, same order
• Throw away the bit that pops off the LSB
• Introduce a 0 into the MSB ◆ 00110101
◆ 00011010
CSE 12 Fall 2020
13

Shifts and Rotates: Logical Right Example
■ Logical right
• Move bits to the right, same order
• Throw away the bit that pops off the LSB
• Introduce a 0 into the MSB
◆ 00110101 shift right by 1 -> 00011010
CSE 12 Fall 2020
14

Shifts and Rotates: Logical Left
■ Logical left
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce a 0 into the LSB
CSE 12 Fall 2020
15

Shifts and Rotates: Logical Left Example
■ Logical left
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce a 0 into the LSB
00110101
Shift left by 2
CSE 12 Fall 2020
16

Shifts and Rotates: Logical Left Example
■ Logical left
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce 0s into the LSB
00110101
CSE 12 Fall 2020
00110101
17

Shifts and Rotates: Logical Left Example
■ Logical left
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce 0s into the LSB
00110101
00110101
CSE 12 Fall 2020
18

Shifts and Rotates: Logical Left Example
■ Logical left
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce 0s into the LSB
00110101
110101
CSE 12 Fall 2020
19

Shifts and Rotates: Logical Left Example
■ Logical left
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce 0s into the LSB
00110101
11010100
CSE 12 Fall 2020
20

Shifts and Rotates: Logical Left Example
■ Logical left
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce 0s into the LSB
00110101 shift left by 2 -> 11010100
Note: Logical Shift left by 1 = Multiply by 2 Note: Logical Shift left by 2 = Multiply by 4 Note: Logical Shift left by 3 = Multiply by 8
CSE 12 Fall 2020
21

Shifts and Rotates: Arithmetic Right
■ Arithmetic right shift
• Move bits to the right, same order
• Throw away the bit that pops off the LSB
• Reproduce the original MSB into the new MSB (preserve the sign!!!)
CSE 12 Fall 2020
22

Shifts and Rotates: Arithmetic Right Examples
■ Arithmetic right shift
• Move bits to the right, same order
• Throw away the bit that pops off the LSB
• Reproduce the original MSB into the new MSB
00110101
1100
Shift right by 2
CSE 12 Fall 2020
23

Shifts and Rotates: Arithmetic Left
■ Arithmetic left shift
◆ Move bits to the left, same order
◆ Throw away the bit that pops off the MSB ◆ Introduce a 0 into the LSB
CSE 12 Fall 2020
29

Shifts and Rotates: Arithmetic Left Example
■ Arithmetic left shift
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce a 0 into the LSB
00110101
Shift left by 2
CSE 12 Fall 2020
30

Shifts and Rotates: Arithmetic Left Example
■ Arithmetic left shift
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce a 0 into the LSB
00110101
CSE 12 Fall 2020
00110101
31

Shifts and Rotates: Arithmetic Left Example
■ Arithmetic left shift
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce a 0 into the LSB
00110101
00110101
CSE 12 Fall 2020
32

Shifts and Rotates: Arithmetic Left Example
■ Arithmetic left shift
• Move bits to the left, same order
• Throw away the bit that pops off the MSB
• Introduce a 0 into the LSB
00110101
110101
CSE 12 Fall 2020
33

Shifts and Rotates: Arithmetic Left Example
■ Arithmetic left shift
• • •
Move bits to the left, same order
Throw away the bit that pops off the MSB Introduce a 0 into the LSB
00110101 arithmetic shift left by 2 -> 11010100
CSE 12 Fall 2020
35

Shifts and Rotates: Rotate Left
■ Rotate left
◆ Move bits to the left, same order
◆ Put the bit(s) that pop off the MSB into the LSB ◆ No bits are thrown away or lost
CSE 12 Fall 2020
36

Shifts and Rotates: Rotate Left Examples
■ Rotate left
◆ Move bits to the left, same order
◆ Put the bit(s) that pop off the MSB into the LSB ◆ No bits are thrown away or lost
00110101 1100 Rotate left 1
CSE 12 Fall 2020
37

Shifts and Rotates: Rotate Left Examples
■ Rotate left ◆
◆ Put the bit(s) that pop off the MSB into the LSB ◆ No bits are thrown away or lost
Move bits to the left, same order
00110101 1100 Rotate left 1
00110101 1100
CSE 12 Fall 2020
38

Shifts and Rotates: Rotate Left Examples
■ Rotate left
◆ Move bits to the left, same order
◆
◆ No bits are hrown away or lost
00110101 1100 00110101 1100
CSE 12 Fall 2020
Put the bit(s) that pop off the MSB into the LSB
39
t

Shifts and Rotates: Rotate Left Examples
■ Rotate left
◆ Move bits to the left, same order
◆
◆ No bits are hrown away or lost
00110101 1100 01101010 1001
CSE 12 Fall 2020
Put the bit(s) that pop off the MSB into the LSB
40
t

Shifts and Rotates: Rotate Left Examples
■ Rotate left (Rotate left 1)
◆ Move bits to the left, same order
◆ Put the bit(s) that pop off the MSB into the LSB ◆ No bits are thrown away or lost
00110101 rotate left by 1 -> 01101010 1100 rotate left by 1 -> 1001
CSE 12 Fall 2020
41

Shifts and Rotates: Rotate Right
■ Rotate right
◆ Move bits to the right, same order
◆ Put the bit that pops off the LSB into the MSB ◆ No bits are thrown away or lost
CSE 12 Fall 2020
42

Shifts and Rotates: Rotate Right Examples
■ Rotate right (rotate right 2)
◆ Move bits to the right, same order
◆ Put the bit that pops off the LSB into the MSB ◆ No bits are thrown away or lost
00110101 1101
CSE 12 Fall 2020
43

Shifts and Rotates: Rotate Right Examples
■ Rotate right (rotate right 2)
◆ Move bits to the right, same order
◆
◆ No bits are hrown away or lost
00110101 1101 001101 1101
CSE 12 Fall 2020
Put the bit that pops off the LSB into the MSB
01
45
t

Shifts and Rotates: Rotate Right Examples
■ Rotate right (rotate right 2)
◆ Move bits to the right, same order
◆
◆ No bits are hrown away or lost
00110101 1101 01001101 0111
CSE 12 Fall 2020
Put the bit that pops off the LSB into the MSB
46
t

Binary Addition
CSE 12 Fall 2020
x 00 +y 00
Carry In
0
0
0
0
1
1
1
1
11 01
Or in tabular form…
A
0
0
1
1
0
0
1
1
B
0
1
0
1
0
1
0
1
Sum
0
1
1
0
1
0
0
1
Carry Out
0
0
0
1
0
1
1
1
48

Binary Addition
011
x 00 +y 00 sum 01
Carry In
0
0
0
0
1
1
1
1
A
0
0
1
1
0
0
1
1
B
0
1
0
1
0
1
0
1
Sum
0
1
1
0
1
0
0
1
Carry Out
0
0
0
1
0
1
1
1
CSE 12 Fall 2020
11 01 00
Or in tabular form…
49

Binary Addition
■ And as a full adder…
ab
co ci sum
■ 4-bit Ripple-Carry “adder”:
◆ Carry values propagate from bit to bit
◆ Like pencil-and-paper addition
◆ Time proportional to number of bits
◆ “Lookahead-carry” can propagate carry proportional to log(n) with more space.
CSE 12 Fall 2020
ab
co ci sum
ab
co ci sum
ab
co ci sum
ab
co ci sum
50

Addition: unsigned
■ Just like the simple addition given earlier.
■ Examples: (we are ignoring overflow for now)
100001 (33) 00001010 (10)
+011101 (29) + 00001110 (14)
CSE 12 Fall 2020
51

Addition: unsigned
■ Just like the simple addition given earlier.
■ Examples: (we are ignoring overflow for now)
00001 01110
100001 (33)
+011101 (29) +
00001010 (10)
00001110 (14)
111110 (62)
00011000 (24)
CSE 12 Fall 2020
52

Addition: 2’s complement
■ ■
Just like unsigned addition
Assume 6-bit and observe:
◆ Ignore carry-outs (overflow)
◆ Sign bit is in the 2n-1 bit position
◆ What does this mean for adding different signs?
000011 (3) 101000 (-24) 111111 (-1) +111100 (-4) +010000 (16) +001000 (8)
CSE 12 Fall 2020
53

Addition: 2’s complement
■ ■
Just like unsigned addition
Assume 6-bit and observe:
◆ Ignore carry-outs (overflow)
◆ Sign bit is in the 2n-1 bit position
◆ What does this mean for adding different signs?
000011 (3) 101000 (-24) +111100 (-4) +010000 (16)
111111 (-1) 111000 (-8)
111
111111 (-1)
+001000 (8)
000111 (7)
CSE 12 Fall 2020
54

More examples: Convert to 2SC and do the addition
-20 + 15 5 + 12 -12 + -25
Do at HOME!!!
CSE 12 Fall 2020
55

Subtraction: 2’s complement
■ Don’t. Just use addition:
◆ x–y->x+(-y)->x+y’+1
Example:
10110 (-10) – 00011 (3)
CSE 12 Fall 2020
56

Subtraction: 2’s complement
■ Don’t. Just use addition:
◆ x–y->x+(-y)->x+y’+1
Example:
10110 (-10) – 00011 (3)
10110 (-10)
+11100 (-3)
+1
CSE 12 Fall 2020
57

Subtraction: 2’s complement
■ Don’t. Just use addition:
◆ x–y->x+(-y)->x+y’+1
Example:
10110 (-10) – 00011 (3)
1 1 10110 (-10) +11100 (-3) +1
1 10011
CSE 12 Fall 2020
58

Subtraction: 2’s complement
■ Addition and subtraction are simple in 2’s complement,
just need an adder and inverters.
■ Can also flip bits of bottom # and add an LSB carry in, so for -10 – 3 we get:
■
1 10110 + 11100
“add 1”
“flip bits of bottom number”
(throw away carry out)
CSE 12 Fall 2020
59

Overflow in Addition
■ Unsigned: When there is a carry out of the
MSB
1000 (8) +1001 (9)
1 0001 (1)
CSE 12 Fall 2020
60

Overflow in Addition
■ 2’s complement: When the signs of the addends are the same, but the sign of the result is different
■ Adding 2 numbers of opposite signs never overflows.
0011 (3) + 0110 (6)
1001 (-7)
CSE 12 Fall 2020
61

Related Posts