Logical Shift right

[NickJoe]

So after many hours of mulling this over and now missing several hairs that used to populate my head, I decided to seek outside help.

In my introduction to computer systems class, we have been tasked to do things that are built into the language without using them. I understand that its an exercise of the mind, and not really a useful implementation, but I'm stuck on the logical shift left. The '>>' operator does arithmetic shift left.I am not allowed to cast anything, so changing the ints to unsigned isn't allowed.

I'm using emacs on Ubuntu 10.1.something, if this changes anything.
given info:
logicalShift - shift x to the right by n, using a logical shift
Can assume that 1 <= n <= 31
Examples: logicalShift(0x87654321,4) = 0x08765432
Legal ops: ~ & ^ | + << >>
Max ops: 16

My attempt at the solution:

int
logicalShift(int x, int n) {
  int z = ~x+1; /* 2's complement*/
  int q = z>>n;
  
  int result= q;
  return result;
    }

this works for positive ints, but not negative ints (keep in mind that they are signed integers). I could do it easily if I could find a way to make a number (in binary) with n 1's followed by 32-n 0's, but I'm not allowed to multiply, and I can't think of another way. Any hints would be greatly appreciated.

[gerard4143]

The reason it fails for negative numbers is, your shifting the signed bit off. Try masking and saving the signed bit and then shift and then mask the signed bit back on.

[NickJoe]

The reason it fails for negative numbers is, your shifting the signed bit off. Try masking and saving the signed bit and then shift and then mask the signed bit back on.

I'm not sure you understand. I'm supposed to change the sign. lets say the number is 110001000100 and n is 2. (followed by 0's to fill out 32 bits.) I need the number to become 001100010001 (again with 0's.). Also, I'm not sure what you mean by masking, but I am limited to the operations told in the given info.

[nezachem]

> lets say the number is 110001000100 and n is 2...
... so after the shift it becomes 111100010001, and you need to get rid of the 2 leading ones, right? Hint: what happens if you shift 100000000000 right by one (that is, by n - 1)?
I didn't see a subtraction among the legal operation. If it is the case, shift it right by n, and then left by one.

[gerard4143]

Are you trying to toggle the signed bit and shift? Meaning, if the signed bit 0 then toggle it to 1 and if the signed bit is 1 then toggle it to 0.

[nezachem]

> Are you trying to toggle the signed bit and shift?

If the question is for me, the answer is no. I am shifting the sign bit alone. It is the first step to get the right mask.

[NickJoe]

> lets say the number is 110001000100 and n is 2...
... so after the shift it becomes 111100010001, and you need to get rid of the 2 leading ones, right? Hint: what happens if you shift 100000000000 left by one (that is, by n - 1)?
I didn't see a subtraction among the legal operation. If it is the case, shift it left by n, and then right by one.

I had thought of that, but unfortunately im not allowed to use any ints larger tan 0xFF, I forgot to mention that. And not knowing what n will be makes things all the more difficult. Unless, would shifting 0x01 to the left (which always adds 0's on the right if im not mistaken) and then shifting it to the right n work?

[gerard4143]

Why don't you give a complete example of what you want...

If you pass a signed value, what's the value before and after the shift.
If you pass an unsigned value, what's the value before and after the shift.

[nezachem]

> would shifting 0x01 to the left

Very solid approach.

[NickJoe]

Why don't you give a complete example of what you want...

If you pass a signed value, what's the value before and after the shift.
If you pass an unsigned value, what's the value before and after the shift.

Alright, but i have to stress that i wont be getting any unsigned values, and can't cast to them (if i could the assignment would be easy.)

a signed number:
1100100. shifting left by 2, normally, would get the return of 1111001.
the desired output, is the same for the output of an unsigned number
1100100 shifting left by 2 logically would get the desired return of 0011001.

[gerard4143]

What I want to know is, what are you doing with the signed bit? Are you truncating it, are you toggling it? What are doing with it? If your truncating it then your function should be returning an unsigned int.

If you pass -64, 0 what's the result? If you pass 64, 0 what's the result?