edited by
5,838 views
22 votes
22 votes

Consider the following program fragment in the assembly language of a certain hypothetical processor. The processor has three general purpose registers $R1, R2$and $R3$. The meanings of the instructions are shown by comments (starting with ;) after the instructions.

X:  CMP R1, 0;  Compare R1 and 0, set flags appropriately in status register
    JZ  Z;   Jump if zero to target Z
    MOV R2, R1; Copy contents of R1 to R2
    SHR R1; Shift right R1 by 1 bit
    SHL R1; Shift left R1 by 1 bit
    CMP R2, R1; Compare R2 and R1 and set flag in status register
    JZ  Y;    Jump if zero to target Y
    INC R3; Increment R3 by 1;
Y:  SHR R1; Shift right R1 by 1 bit
    JMP X;  Jump to target X
Z:...
  1. Initially $R1, R2$ and $R3$ contain the values $5$,$0$ and $0$ respectively, what are the final values of $R1$ and $R3$ when control reaches Z?

  2. In general, if $R1, R2$ and $R3$ initially contain the values n, 0, and 0 respectively. What is the final value of $R3$ when control reaches $Z$?

edited by

3 Answers

Best answer
30 votes
30 votes
SHR R1 (Lower bit is lost and upper bit becomes $0$ and all other bits shift right by $1$)
SHL R1 (Upper bit is lost and lower bit becomes $0$ and all other bits shift left by $1$)

These two operations change the value of $R1$ if its lower bit is $1$. So, the given program checks the lowest bit of $R1$ in each iteration and if its $1$ then only increment $R3$ and loop terminates when $R1$ becomes $0$. Thus at end, $R3$ will have the count of the number of bits set to $1$ in $R1$.

a. $R1 = 0$, $R3 = 2$ as $101$ has two $1$'s

b. $R3 =$ #$1$ in $R1.$
edited by
9 votes
9 votes
Generally we have 4 status flags- Carry flag (C), Zero flag (Ze), Sign flag (S) and Overflow flag (V).

We will consider the given values are unsigned. For unsigned number comparison 2 flags are needed- Zero flag (Ze) and Carry flag (C).

I have used 'Ze' flag to distinguish between Z mentioned in code and Zero flag.

(A)

R1= 5= 101

R2=000

R3=000

Going step by step-

CMP R1,0; means 101-000= 101. Set the flags as Ze=0 and C=0.

JZ Z; means if Ze true then jump to Z. Since Ze is 0 ie false so don't jump.

MOV R2,R1; means R2= 101

SHR R1; R1 becomes 010

SHL R1; R1 becomes 100

CMP R2,R1; means 101-100= 001, set the flags as Ze=0 and C=0

JZ Y; means if Ze is 1 then jump to Y. Since Ze is 0 so don't jump.

INC R3; means R3 becomes 001.

SHR R1; R1 becomes 010

JMP X; go to X

Again start
CMP R1,0; 010-000=010,  Set Ze= 0 and C =0

JZ Z; false

MOV R1, R2; R2 becomes 010

SHR R1; R1 becomes 001

SHL R1; R1 becomes 010

CMP R2,R1; means 010-010= 000 , set Ze=1 and C= 0

JZ Y; Ze is 1 so true, so jump to Y

SHR R1; R1 becomes 001

JMP X; Jump to X

Again start

CMP R1,0; 001-000= 001. Set Ze= 0

JZ Z; Ze= 0 so don't jump.

MOV R2,R1; R2 becomes 001

SHR R1; R1 is 000

SHL R1; R1 is 000

CMP R2,R1; 001-000 = 001 and set Ze=0 and C =0

JZ Y; false

INC R3; R3 becomes 010

SHR R1; R1 becomes 000

JMP X; go to X

Again

CMP R1 ,0; 000-000 = 000 Set flags Ze=1, C= 0.

JZ Z; Since Ze flag is true so jump to Z

So final values of R1= 0 and R3= 010= 2.

(B)  Following the code carefully we see that R3 is incremented if R1 is not 0 or if the shift right and shift left operations make R1 different from R2. It is only possible when LSB of R1 had 1. So R3 is able to count number of 1's in R1.
edited by
0 votes
0 votes

When $R1$ is 5, after SHR $R1$ the value would be 2, After SHL $R1$, the value would be 4. Since $R1$ contains 4 and $R2$ contains 5, CMP $R2$ $R1$ will not set zero flag to $1$, so the loop will not be executed, program will skip JMP to set $R3$  to $1$ and program will exit. Whenever $R1$ contains an even number, the program would loop and $R3$ will remain $0$ when program exists. This program checks whether the given value in $R1$ is odd or even. 

$A$: $R1$: 4 and $R3$: 1 

$B$: $R1$ will contain $n-1$ if n is odd and 0 if n is even. If value at $R1$ is odd, $R3$ is set to $1$ else $0$.

Related questions

34 votes
34 votes
3 answers
1
54 votes
54 votes
3 answers
2
Kathleen asked Sep 23, 2014
15,413 views
A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this proces...
35 votes
35 votes
4 answers
3
Kathleen asked Sep 23, 2014
8,962 views
The main difference(s) between a CISC and a RISC processor is/are that a RISC processor typicallyhas fewer instructionshas fewer addressing modeshas more registersis easi...