This week's book giveaway is in the Servlets forum. We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line! See this thread for details.

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, 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!

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

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

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
Ranch Hand

Joined: Jan 17, 2002
Posts: 172

posted

0

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
Ranch Hand

Joined: Jan 17, 2002
Posts: 172

posted

0

Thanks Corey for your awesome explanation!

Corey McGlone
Ranch Hand

Joined: Dec 20, 2001
Posts: 3271

posted

0

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:

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
Ranch Hand

Joined: Dec 20, 2001
Posts: 3271

posted

0

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
Ranch Hand

Joined: Jan 17, 2002
Posts: 172

posted

0

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
Ranch Hand

Joined: Jul 17, 2001
Posts: 173

posted

0

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