0
\$\begingroup\$

Which of the following computation will take minimum no of clock cycles, if implemented on 8051 micro controller? following variabe declaration is in c-code:

unsigned int a,b;

A) b=a*a

B) b =a*3

C) b=a/3

D) b=a/4

This question was asked in ISRO Recruitment exam 2014. ans given is option D can you explain how to solve this and why the option is correct?

\$\endgroup\$
2
  • \$\begingroup\$ A competent teacher would have included some disclaimer like "generally" or "in most modern implementations" or whatever. The compiler is not required to produce the most obvious implementation (using shifts, as in Ignacio's answer). \$\endgroup\$ Jun 8, 2016 at 6:54
  • \$\begingroup\$ To be fair it only says that the declaration is in C. The implementation could be whatever, even hand-tuned assembly. \$\endgroup\$ Jun 8, 2016 at 7:10

2 Answers 2

1
\$\begingroup\$

A simple CPU like 8051 knows how to do addition, subtraction, left bit shifts to the left, and bit shifts to the right. Sometimes the CPU knows how to do multiplication and division (this is the case for 8051), but these operations always take a bigger number of cycles to complete.

So, when you need to multiply a number by a power of two, you better have to shift its bits to the left, and when you need to divide it by a power of two, you shift its bits to the right. This is the same as what you do, mentally, when using decimal, to multiply a number by 10 or 100 or by any power of 10: just add the required number of zeroes to the right.

Now, for the fun, have a look at the 8051 user manual and we'll check this in detail:

  • The timing of the ADD/ADDC (addition without/with carry) operations are 1 cycle.
  • The timing for the left/right shifts (actually rotate one bit left/right with carry: RLC or RRC) are 1 cycles.
  • The timings for MUL and DIV are each 4 cycles.

How would you implement each of the operations decribed in the exercise ?

  • A) a*a: you have to use MUL, you have no choice -> 4 cycles
  • B) a*3: you can do it with two additions: a+a+a -> 2 cycles
  • C) a/3: you have to use DIV -> 4 cycles
  • D) a/4: you can use RRC twice -> 2 cycles

But before you use RRC, you'd better clear the carry flag or you may end up with wrong results. So the code for D is actually:

CLR C
RRC
CLR C
RRC

Now, this is 4 cycles.

Whaaaaat ??? The B) operation now actually takes less cycles ! I have triple checked this, but I'm not an expert of 8051, so I may be wrong; but the D) answer, although it clearly stands out as the fastest at the first glance ("it's just a bit shift"), is actually not the correct one, from my point of view.

Conclusion

If you failed the exam just because of this question, you may well sue ISRO. The official answer is, at best, litigious. (And at worst, the whole question is a nonsense, because it completely depends on how the compiler optimizes things and the context in which these statements are used.)

\$\endgroup\$
7
  • \$\begingroup\$ unsigned int means that they are 2- or 4-byte numbers, which requires more complex operations than you have shown. \$\endgroup\$ Jun 8, 2016 at 7:37
  • \$\begingroup\$ That's right, I didn't account for this. Still, let's say it's 16 bits, a+a+a is ADD+ADC for the first addition, then ADD+ADC again -> 4 cycles, whereas you need to do CLR C, RRC, RRC, CLR C, RRC, RRC for divide by four -> 6 cycles. \$\endgroup\$
    – dim
    Jun 8, 2016 at 7:43
  • 1
    \$\begingroup\$ But that's not accounting for the fetches in memory (and we don't know where the variables are stored)... Well, actually, this whole exercise is a mess, no ? \$\endgroup\$
    – dim
    Jun 8, 2016 at 7:44
  • \$\begingroup\$ how does RRC work in division? \$\endgroup\$
    – Aparna B
    Jun 10, 2016 at 7:50
  • \$\begingroup\$ @user113374 Look at it that way: In decimal, how do you divide 52683 by 10 ? You remove the last digit (which becomes the rest, by the way) and it gives 5268. In binary, how can you simply divide by 2 ? You shift all binary digits to the right and drop the last one. It is the same. How do you divide by 4 ? You do this twice. \$\endgroup\$
    – dim
    Jun 10, 2016 at 7:55
6
\$\begingroup\$

Division of an integer by a power of 2 is a right shift, which on many architectures is a single operation. Likewise, multiplication by a power of 2 is a left shift.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.