1 of 40

CS111 – Fundamentals of CS�Lecture 12�Data Manipulation II

Mohammad El-Ramly, PhD

Fall 2021-2022

http://www.acadox.com/class/63592

6EQYX4

(Many Slides by Pearson Edu.)

2 of 40

Intelligent Design ☺

Random ☹

3 of 40

The Miracle of the Hand�https://cutt.ly/fUogc2Y

Marvelous Engineering ☺

Haphazardness ☹

4 of 40

What Will We Study?

1

أ ب ت

2

3

Programs

Algorithms

4

5

2

10001110111

5 of 40

Stored Program Concept

A program can be encoded as bit patterns and stored in main memory. From there, the CPU can then extract the instructions and execute them. In turn, the program to be executed can be altered easily.

2-5

6 of 40

Computer Architecture Influence

Well-known computer architecture: Von Neumann (Concept invented by Burks, Goldstine, and von Neumann, in 1947)

Data and programs stored in memory as 1101000111
Memory is separate from CPU
Instructions and data are piped

from memory to CPU

Memory

CPU

1-6

add 4+8

subtract

compare

12

7 of 40

Try FCI Machine Simulator

0-7

https://github.com/Megadardery/machine-language/releases

Developed to be used with this course on Windows

A good explanation video for von Neumann (Arabic) – numerous English ones exist

https://www.youtube.com/watch?v=wC6rfZaF3fM

8 of 40

Chapter 2: Data Manipulation

2.1 Computer Architecture
2.2 Machine Language
2.3 Program Execution
2.4 Arithmetic/Logic Instructions
2.5 Communicating with Other Devices
Not in Book: Adders

2-8

9 of 40

0-9

10 of 40

0-10

11 of 40

Exam Question

Give this piece of C language program:
X = 92_d;
Y = 90_d;
Z = X + Y;
Write the equivalent machine language program using the machine language at the last page. Show the steps equivalent to each of the three steps above.

0-11

12 of 40

What does this code do ?
Address Contents Address Contents Address Contents
0E 00 19 0F 24 20
0F 00 1A 20 25 01
10 20 1B 04 26 50
11 02 1C B1 27 01
12 30 1D 2C 28 30
13 0E 1E 12 29 0F
14 20 1F 0E 2A B0
15 01 20 50 2B 18
16 30 21 12 2C C0
17 0F 22 30 2D 00
18 11 23 0E

0-12

Another Exam Question

13 of 40

What does this code do ?
0E 00 00
10 20 02
12 30 0E
14 20 01
16 30 0F
18 11 0F
1A 20 04
1C B1 2C
1E 12 0E
20 50 12
22 30 0E
24 20 01
26 50 01
28 30 0F
2A B0 18
2C C0 00

0-13

14 of 40

Solution

C equivalent:

int x, y;

x = 2; y =1;

while (y != 4) {

x = x + y;

y = y + 1;

}

0-14

15 of 40

What does this code do ?
0E 00 00
10 20 02
12 30 0E
14 20 01
16 30 0F
18 11 0F
1A 20 04
1C B1 2C
1E 12 0E
20 50 12
22 30 0E
24 20 01
26 50 01
28 30 0F
2A B0 18
2C C0 00

0-15

x = 2

y = 1

Load y in R1 and 4 in R0

If y == 4 jump to end

If not load x in R2

Add x + y

store result in x (x = x+y)

Store 1 in R0, add it to y

Then store result in y

Jump to loop start

16 of 40

0-16

17 of 40

Boolean Operations

Boolean Operation: An operation that manipulates one or more true/false values
Specific operations

AND
OR
XOR (exclusive or)
NOT

1-17

18 of 40

Figure 1.1 The possible input and output values of Boolean operations AND, OR, and XOR (exclusive or)

1-18

The NOT operation

NOT 1 NOT 0

0 1

19 of 40

Figure 1.1 The possible input and output values of Boolean operations AND, OR, and XOR (exclusive or)

1-19

AND

OR

XOR

1 1 ▬► 1

1 0 ▬► 1

0 1 ▬► 1

1 0 ▬► 1

0 1 ▬► 1

20 of 40

0-20

21 of 40

0-21

22 of 40

0-22

23 of 40

IV. Arithmetic/Logic Operations

Bitwise Logic:

AND, OR, XOR

Representing “bit maps”
Masking

2-23

24 of 40

Arithmetic/Logic Operations

AND: Bit map masking

11111110
10100101
--------------
10100100

Filtering certain colors out of a digital image represented in the RGB format. E.g., remove red and keep blue and green.
We can mask the red component as image processing software does.

25 of 40

Exam Question - Even or Odd

Write a machine language program to check if a given number is even or odd.
The given number is stored in address F0 and the result will be

Writing ‘E’ to screen (ASCII 69) if even
Writing ‘O’ to screen (ASCII 79) if odd

0-25

26 of 40

Exam Question - Even or Odd Algo

Load memory F0 to R1
Load number 01 to R2
Load number 00 in R0
R3 = R1 AND R2
If (R3 == R0)

Print ‘E’
Jump to End

Else

Print ‘O’

0-26

27 of 40

0-27

28 of 40

Arithmetic/Logic Operations

Bit map masking

Turn off a bit / flag Get value of bit / flag

11111110 00000001
10100101 10100101
-------------- --------------
10100100 00000001

29 of 40

Arithmetic/Logic Operations

XOR forms the compliment

The XOR operation can be used to invert all of the bits of an RGB bitmap

image, resulting in an “inverted” color image in which light colors have been

replaced by dark colors, and vice versa.

30 of 40

Arithmetic/Logic Operations

XOR forms the compliment

31 of 40

Arithmetic/Logic Operations

OR can also force ones

32 of 40

Exam Question

Write a program to calculate the two’s complement of a given number stored in F0 and store it in F1.

0-32

33 of 40

0-33

34 of 40

Arithmetic/Logic Operations

Rotate and Shift: circular shift, logical shift, arithmetic shift
Shift left is like multiplying by 2
Shift right is like dividing by 2

Preserve the sign bit (arithmetic shift)

2-34

35 of 40

Arithmetic/Logic Operations

Circular shift (Rotation)

Put the falling bit in the last place

Logical shift

The falling bit disappears

Arithmetic shift

The falling bit disappears but sign bit stays in place.

2-35

36 of 40

Arithmetic/Logic Operations

A501 =. Rotate R5 to the right by 1 bit.”
If register 5 contains 65 (hexadecimal), then it would contain B2 after this.

0110 0101 - > 1011 0010
How other shift and rotate instructions can be produced with combinations of the instructions provided in the m/c language of Appendix C?

A right circular shift of 3 bits produces the same result as a left circular shift of 5 bits.

2-36

37 of 40

Figure 2.12 Rotating the bit pattern 65 (hexadecimal) one bit to the right

2-37

38 of 40

0-38

39 of 40

Arithmetic/Logic Operations

Logic: AND, OR, XOR

Masking

Rotate and Shift: circular shift, logical shift, arithmetic shift
Arithmetic: add, subtract, multiply, divide

Precise action depends on how the values are encoded (two’s complement versus floating-point).

2-39

40 of 40

Exam Question

Suppose you want to isolate the middle four bits of a byte by placing 0s in the other four bits without disturbing the middle four bits. What mask must you use together with what operation?
Suppose you want to complement the four middle bits of a byte while leaving the other four bits undisturbed. What mask must you use together with what operation?

0-40