Paul Salerno

Ranch Hand

Posts: 172

posted 15 years ago

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?

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

Ranch Hand

Posts: 173

posted 15 years ago

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

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

Ranch Hand

Posts: 172

Corey McGlone

Ranch Hand

Posts: 3271

posted 15 years ago

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?

I've added '

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

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

0

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.

2.

3.

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:

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:

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

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

Let's try to follow what happens in each step. First, what does b look like in binary?

**|**00000111**|**// byte b in binaryI'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**|**= 14Notice, 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**|**03.

**|**??000011**|**10As 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**|**= 3Just 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**|**1Again, 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

Ranch Hand

Posts: 3271

posted 15 years ago

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

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).

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 ]

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

Posts: 172

posted 15 years ago

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

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?

Corey McGlone

Ranch Hand

Posts: 3271

posted 15 years ago

In case 4, you used a

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

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

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

Posts: 3271

Paul Salerno

Ranch Hand

Posts: 172