3
$\begingroup$

I want a shift operator for an architecture that implements boxing. Basically, the high-level constructs represent integers as 31 bits followed by 1 bit set to one as a tag (so to represent binary int i I use instead 2i+1). Let's denote the box representation as $[[\cdot]]$, then I was able to make the following deductions. Consider x the number to be the shifted value and y the shift value (read the following to understand the whole process):

$[[\text{shift} \, x \, y]] = 2*{\text{shift} \big[\frac{[[x]]-1}{2} \, \frac{[[y]]-1}{2}}\big] + 1 = 2*{\text{shift} \big[\frac{[[x]]-1}{2} \, \frac{[[y]]}{2}}\big] + 1 = $

$= {\big[\text{shift} \; [[x]]-1 \, \frac{[[y]]}{2}}\big] + 1$

Here we can use $\frac{[[x]]-1}{2}$ or $\frac{[[x]]}{2}$ because $[[x]]$ always ends with a one however in the last step we remove the division by two and for $[[x]]$ we have to keep $-1$ but not for $[[y]]$. Please note that this translation is meant for left shifts where the bit structure of $x$ is important, namely if we have $x_1 x_2 x_3 1$ the last bit will be actually used in contrast with the right shift case.

The following is the version for the right shift (again read what follows to understand the process):

$[[\text{shift} \, x \, y]] = 2*{\text{shift} \big[\frac{[[x-1]]}{2} \, \frac{[[y-1]]}{2}}\big] + 1 = 2*{\text{shift} \big[\frac{[[x]]}{2} \, \frac{[[y]]}{2}}\big] + 1 = $

$= {\big[\text{shift} \; [[x]] \, \frac{[[y]]}{2}}\big] + 1$

Here the point is that the last bit is no longer useful and can be ignored.

I wonder if me scheme is correct and efficient in the sense that it may exist other procedure that is more efficient than mine. I would appreaciate as well that you clarify the intuitive ideas I gave for my procedure (if it is correct) reelaborating my assertions with possibly more accurate ones. Also I would appreciate ideas that suggest how to mix this two implementations.

$\endgroup$
  • $\begingroup$ You ask if it is correct. Sure, it appears you just proved it is correct. Why do you need to ask? Do you have some doubts? Have you tried writing test cases and testing it on many carefully selected test cases and many random test cases? $\endgroup$ – D.W. Mar 21 '17 at 16:50
  • $\begingroup$ You ask how to mix the two implementations. What do you mean by that? $\endgroup$ – D.W. Mar 21 '17 at 16:52
  • $\begingroup$ You ask for elaboration of your assertions. Do you have any specific uncertainty? The site works better when you can ask a focused, specific technical question, rather than an open-ended invitation to review and feedback. $\endgroup$ – D.W. Mar 21 '17 at 16:52
  • $\begingroup$ Related (Next question): cs.stackexchange.com/questions/72541/… $\endgroup$ – nekketsuuu Apr 6 '17 at 1:26
1
$\begingroup$

Yes, it is correct. Yes, it is efficient: your implementation for left-shift requires only four basic operations (i.e., about four instructions), and your implementation for right-shift requires only three basic operations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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