Implementing logical right shift using only "~ & ^ | + << >> =" operators and 20 operations

Question

So I have an assignment that I have to code a function in c that uses only the bitwise operations of ~ , & , ^ , | , + , << , >> , and =. I have to use only 20 operations. And I am not allowed to use control structures such as, if-else , for, while, switch, or anything else that excutes code in conditional blocks. Also type casting is also out and the bytes that are not declared in the function header (which is given to me), are limited to 1 byte or 8 bit values; so I have hex 0 through FF.

The function I have to code is a logical right shift. So instead of the bits filling up with the sign bit they should fill up with 0's

This is what I have done:

int logicalShift(int x, int n) {
    int op=0xFFFFFFFF;
    int tcn=(~n+1);
    int sizeshift=0x20 & tcn;
    op=(op<<sizeshift);
    return ((x>>n) + (op));
}

This is what I expect to get ( for an x=0x80000000, and n=0x01) I expect to get 0x40000000 which is 1073741824 in decimal. This is what I get. However (for an x=0x80000000, and n=0x0 I expect to get 0x80000000, however I get 0x7fffffff which is my answer minus a bit. I could add a bit, but it messes up the first answer. So What am I doing wrong that I have one case but not the other. I have also tried.

int logicalShift(int x, int n) {
    int op=0xFFFFFFFF;
    int tcn=(~n+1);
    int sizeshift=0x20 & tcn;
    op=(op<<sizeshift);
    return ((x>>n) + (op  ^ ~n));
}

I thought that if I XOR the set of bits zeroing out the sign bits with all 1's for the 0 case I would end up with something that was not negative (aka) 0x7fffffff when it went through the compilers conversion to 2's complement. It ended up making it worse. Please set me in the right direction what should I consider and why?

Maybe `>>` shouldn't be allowed? Otherwise, "how to program logical right shift using only “~ & ^ | + << >> =” operators" is trivial: you just do `x >> y`. — , Oct 05 '13 at 22:00
how would simple code for logical shift look like if you were allowed to use full C language? — jev, Oct 05 '13 at 22:00
@HeathHunnicutt I disagree. This question comes with two attempts and an exhaustive explanation of what the author was thinking about, and it's asking for a nudge in the right direction instead of a full solution. — us2012, Oct 05 '13 at 22:05
@HeathHunnicutt Don't do that. Homework questions are perfectly fine, as long as they're well-written and show effort (like any other question). — John Kugelman, Oct 05 '13 at 22:06
I've bolded the "type casting is also out" restriction because that seems to be key. In other words, the OP must implement **logical** (unsigned) right shift but is only allowed to use **arithmetic** (signed) right shift. — John Kugelman, Oct 05 '13 at 22:12
@John Kugelman - "Homework questions are perfectly fine,..." No, they are not. We have no idea if the professor wants us assisting the student and whether we are complicit in an activity which could get the student expelled from many fine schools. — Heath Hunnicutt, Oct 05 '13 at 22:13
@HeathHunnicutt Yes, they are. See: [How do I ask and answer homework questions?](http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions). — John Kugelman, Oct 05 '13 at 22:16
[Perform logical shift using arithmetic shift operator in C](https://stackoverflow.com/q/17893901/995714), [Implementing Logical Right Shift in C](https://stackoverflow.com/q/5253194/995714) — phuclv, Jan 26 '19 at 01:33

John Kugelman · Answer 1 · 2013-10-05T22:59:19.693

The difference between logical and arithmetic shift are the bits shifted in from the left. To implement logical shift in terms of arithmetic you can do the arithmetic shift and then clear the new bits. In pseudo-code:

Generate a mask that will clear the leftmost n bits when ANDed with the result.
Shift right by n bits.
AND the mask.

Using AND means you don't have to care what bits are shifted in. You just want to unconditionally set them to 0.

The question then is how to generate the mask. I'll leave that as an exercise for you.

usr · Answer 2 · 2013-10-05T22:24:40.843

If the sign bit is not set, (x >> n) == (x >>> n). If the sign bit is set, we mask it off before doing the shift, then add it back: (x & 0x7FFFFFFF) >> n | (0x40000000 >> (n - 1)).

If we know, which of the two cases we have, the computation becomes easier. If we could use if, we could combine the two cases. We have to emulate a conditional.

int signBit1 = (x & 0x7FFFFFFF) >> n | (0x40000000 >> (n - 1));
int signBit0 = x >> n;
var signBitIsolated = x & 0x80000000; // either 0 or 0x80000000
var signMask = signBitIsolated >> 31; //either 0 or 0xFFFFFFFF
var combined = (signBit0 & ~signMask) | (signBit1 & signMask);
return combined;

We simulate a conditional by generating an all-zeros or all-ones mask, and or-ing the two cases.

I think you said that the input domain is restricted to one byte. The same idea applies, but with different constants.

Implementing logical right shift using only "~ & ^ | + << >> =" operators and 20 operations

2 Answers2

Linked