The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 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
  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$?

asked in CO & Architecture by Veteran (59.7k points)
edited by | 1.2k views
For R1 = 5, then R3 will be incremented because content of R1=4 and R2=5, Comparison of R1 and R5 will result into nonzero value.

For R1=1, R3 will be incremented again, because R1 will have 0 after shift operations and R2 will have 1, again Comparison of R1 and R5 will result into nonzero value.

$Remark$: every time if the LSB of the binary number stored in R1 is 1, R3 will be incremented.

this program counts the number of 1's in the binary representation of the value stored in R1.
could u plz explain how the comparision of R1 and R2 will result a non-zero value

I have doubt, if both are not equal then they must result Zero...

plz explain the comparision process>

@Arjun sir and @Manu sir

1 Answer

+16 votes
Best answer
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.$
answered by Veteran (367k points)
edited by

 sir could u please elaborate a little more...?

clear now?
sir I know about left and right shift , but i am facing problem in approaching the question? when i am trying to traverse the code, i am never reaching to Z..could u plz explain it with the help of an example

That is the second line. See now..

JZ  Z;   Jump if zero to target Z
Can we consider arithmetic right shift instead of logical right shift?
The register R2 will always have value 1 at the end of the program execution.Is it true? Please verify!
@Satyam, No I don't think we can use Arithmetic Shift Right (ASR) here because

Suppose we have::

100 >> ASR >> 110 (sign bit is copied to right and no zero padding)

So, if we do ASR our program may not terminate.
size of registers R1 ,R2, R3 (8-bit or 16-bit) will not matter..?
no, because initial values were already given and question is about modifying them.

although initial values are given but those can be stored in either 8-bit or 16-bit .

for eg. 15 can be written as  ( 1111 ) or ( 0000 1111 ) or  ( 0000 0000 0000 1111 )

now when shifting will be done on each of them then it will act i wrong then pls correct.!!


8-bit value 0000 1111 -> Right Shift by 1 place -> 0000 0111 = 7

16-bit value 0000 0000 0000 1111 -> Right Shift by 1 place -> 0000 0000 0000 0111 =7 

Marked bit shows what is extended when shift took place.

do you see any change in value?

@Arjun Sir when the value in R1 is even I think register R3 will never be incremented as everytime it would be equal to R2, so can the answer be no of 1's in the binary equivalent of n, when n is odd otherwise $0$.
nice explanation @Arjun sir

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,059 questions
49,580 answers
65,775 users