Right >> Shift behavior

[Paul Salerno]

I'm a little fuzzy on Right shifts, and my notes contain wild definitions. If you could elaborate on the following cases, that would be a great help
Case 1:
bit value x = 00101011
X >> 2 --> 10101100 // an obvious error?
Case 2:
10101011 >> 2
11101010 // seems correct
Case 3:
10100000 >> 5
11111101 // seems correct
Case 4:
10110001 >> 2
results in positive // i believe incorrect!
11101100 // as zeros are positive
Case 5:
"unsigned Right Shift Operator causes negative number to change sign."
Can you please provide a code explanation?

[Rick Salsa]

Hi Paul,
Take a look at:
Marcus Green's site and java ranch camp fire story
If that doesn't help, let us know.
/rick

[Paul Salerno]

Rick,
I read the storybits, and it seems to make sense that cases 2 thru 4 would be correct.
What I'm really looking for is some kind of validation for the cases that I presented.
Thanks!

[Corey McGlone]

When I think about bit shifting, I try to visualize a window that I'm sliding bits through. Take this example:

byte b = 7;
b << 1;
b >> 2;
b >>> 1;

Let's try to follow what happens in each step. First, what does b look like in binary?
|00000111| // byte b in binary
I've added '|' characters to show the "edge of the window" that we'll be sliding our bits through. That window is the size of the data type, in this case, 8 bits. The binary representation between the two bars is what is actually stored in b.
Now, think about sliding the bits whichever direction the shift operator says to shift. In the first case, the shidt operator points to the left, so we'll shift left 1 space.
0|0000111?|
As you can see, to shift left, we simply moved all the bits one space to the left. That leaves a hole on the right side of the window. What do we fill that in with? When doing a left shift, we always fill with 0's. So, what does that give us?
0|00001110| = 14
Notice, shifting left 1 is equivalent to multiplying by 2.
Now, the next operator says that we should shift right two spaces. I'll show this in three steps, starting with what we had left from the last shift:
1. |00001110|
2. |?0000111|0
3. |??000011|10
As you can see, we're just moving the bits to the right. In this case, we moved the 10 on the right out of the window. Again, we're left with a hole on the left side of the window? What should we fill that with? This time, we need to make a decision. The operator used was '>>'. That's the right-shift with sign operator. That means we should keep the original sign of the number after the shift. The sign of the value is given by the leftmost bit. If it's a 0, the number is positive, if it's a 1, the number is negative. Since we started with a 0 as the leftmost bit, we'll shift in 0's (the leftmost bit shouldn't change when doing a right shift with sign). That gives us this:
|00000011| = 3
Just as left shifting by one bit is equivalent to multiplying by 2, right shifting by one is equivalent to dividing by 2. We shifted two places in this case, so we divided by 2*2 or 4. 14/4 = 3 (it's truncated, of course).
Now, for the final operation: v >>> 1. Let's start with what we had after the last operation and go from there:
|00000011|
|?0000001|1
Again, we slide the bits to the right, knocking that last 1 out of the window. Now, what shall we fill the hole on the left with? Well, this time the operator was '>>>'. That means that, no matter what, we're going to slide 0's in from the left. That means that, after a right shift without sign (assuming we don't shift by 0), the resulting value with always be positive. That leaves us with this:
00000001 = 1
The final value of b, after the three shifts, is 1.
I hope this explanation makes sense to you. It'd be a lot easier if I could just draw it for you. If you have any more questions, I can try to explain some more.
Corey

[Corey McGlone]

To give you a little feedback of the cases you've presented:

Case 1:
bit value x = 00101011
X >> 2 --> 10101100 // an obvious error?

This is wrong. It's a left shift, not a right shift.
Cases 2-4 are correct, except that the result of case 4 is negative (-20, I believe).

Case 5:
"unsigned Right Shift Operator causes negative number to change sign."

The unsigned right shift operator always makes the value positive (unless you right shift a negative value by 0). Therefore, any negative values are positive after being shifted and any positive values remain positive after being shifted.
I hope that helps,
Corey
[ February 21, 2002: Message edited by: Corey McGlone ]

[Paul Salerno]

The unsigned right shift operator always makes the value positive (unless you right shift a negative value by 0). Therefore, any negative values are positive after being shifted and any positive values remain positive after being shifted.

if this were the case then why our case 4 result is negative? Is there a difference w/ unsigned right shift operators?

[Paul Salerno]

Thanks Corey for your awesome explanation!

[Corey McGlone]

Originally posted by Paul Salerno:

if this were the case then why our case 4 result is negative? Is there a difference w/ unsigned right shift operators?

In case 4, you used a signed right shift operator (>> . This operator fills the left side with the value that the leftmost bit had prior to the shift. For example:

byte b = -100;
b >> 3;
b >>> 1;
b >> 1;

The binary representation of b (-100) is:
10011100 = -100
After right shifting 3 (using a signed right shift) we have this:
11110011 = -13
Notice that we shift in sign bits from the left. In this case, the initial value was negative, so we shift in 1's.
Now, we're going to execute the second shift using the unsigned right shift operator (>>> . This operator says that we always shift in 0's from the left. So we go from this:
11110011 = -13
to this:
01111001 = 121
Lastly, we're going to shift to the right once again using the signed right shift operator (>> . We need to shift in sign bits but, this time, the sign bit is positive (0), so we'll shift in 0's instead of 1's. So, we go from this:
0111001 = 121
to this:
0011100 = 28

Does that clear up the difference between the two right shift operators?
Corey

[Corey McGlone]

Bah - those smiley faces aren't all supposed to be there - they should be just right parenthesis. Sorry about that. I fogot to add spaces...
Corey

[Paul Salerno]

Corey,
Again I thank you. I was apparently confused with the terminology of unsigned right shift operator vs zero fill shift (theyre the same)
Thanks!

[Rick Salsa]

Ah, sorry, was away from the computer for a while, but Corey did a very good job explaining it. Probably better than I could have.
/rick