Rekha Anand

Ranch Hand

Posts: 36

posted 9 years ago

Hello All.

I have started giving mock tests available on the internet. One problem that I see is that I get stuck in the questions involving shift operators. While learning about shift operators I used calculators to get to the right answer. But calculators are not allowed in the final exam. I get nervous when I come across big numbers carrying only 0's and 1's. Is there any short cut method of solving questions involving shift operators? For example: -4 >>> 3. Could someone tell me all the steps in solving this problem?

Thanks & Regards,

Rekha

I have started giving mock tests available on the internet. One problem that I see is that I get stuck in the questions involving shift operators. While learning about shift operators I used calculators to get to the right answer. But calculators are not allowed in the final exam. I get nervous when I come across big numbers carrying only 0's and 1's. Is there any short cut method of solving questions involving shift operators? For example: -4 >>> 3. Could someone tell me all the steps in solving this problem?

Thanks & Regards,

Rekha

Campbell Ritchie

Sheriff

Posts: 53760

127

posted 9 years ago

Take it easy. If you look in the Java™ Tutorial, you find this:

You usually use them on ints mainly because ints are the most popular type of number, but I shall show you how they work on bytes, mainly because it is quicker to write 8 1s than 32!

1: The left-shift operator. <<

This moves the whole thing

21 = 00010101 Two to the left = 010101-- Fill in the 0s = 01010100 Convert to decimal = 84. 84 / 21 = 4, and 4 = 2². There's your 2 back. Left-shift 1 bit is equivalent to multiplying by 2, two bits is multiplying by 4, and three bits is multiplying by 8.

The normal rules about overflow errors apply; 21 << 3 in 32 bits is 168 but in 8 bits it's -88. -33 << 2 in 32 bits is -132, in 8 bits it's +124.

2: The right-shift operator >>

This moves the whole thing21 = 00010101 2 to the right gives --000101 Fill in with 0 gives 00000101 and that's 5 21 / 5 in integer arithmetic is 4, 4 = 2^2, and there's your 2 back. Not 168, but -88 is 10101000. 2 to the right gives --101010 Fill in with 1s this time gives 11101010 11101010 is -22. -88 / -22 is 4, and 4 is 2². So right-shift by 1 is the same as dividing by 2, two bits to the right is the same as dividing by 4, three bits is dividing by 8, etc. Note that the sign is always maintained and there is no risk of overflow, but if you shift too many places you will always get -1 from negative numbers and 0 from positive numbers.

Both the right-shift and left-shift operators are usually described as being "signed."

3: The unsigned right shift >>>

This is the most complicated of the three. It moves the bits

For a negative number, eg -88 >>> 2, this is what happens-88 is 10101000 Two to the right gives --101010 Fill in with ZEROES from the left: 00101010 00101010 is 42.

Remember that is you multiply 42 by 4 in 8 bits you get -88. I am afraid I can't think of a simple way to calculate the values you get from a >>> operator.

I hope this is of some help to you And it was a nice interesting question to answer, too.

[edit]Correct 84 / 2 = 5 to 84 / 21 = 5 and change ^2 to superscript 2 twice.[/edit]

So you needn't expect to find lots of questions about shift operators.Certain operators tend to appear more frequently than others; for example, the assignment operator "=" is far more common than the unsigned right shift operator ">>>".

You usually use them on ints mainly because ints are the most popular type of number, but I shall show you how they work on bytes, mainly because it is quicker to write 8 1s than 32!

1: The left-shift operator. <<

*n*This moves the whole thing

*n*bits to the left; any bits which pass the most significant bits disappear into cyber-limbo and any gaps on the right are filled with 0s. So 21 << 2 isThe normal rules about overflow errors apply; 21 << 3 in 32 bits is 168 but in 8 bits it's -88. -33 << 2 in 32 bits is -132, in 8 bits it's +124.

2: The right-shift operator >>

*n*This moves the whole thing

*n*bits to the right; any bits which pass the least significant bit fall off the edge of the world and it fills in from the left with**the same bit that the original most significant bit was.**21 >> 2 isBoth the right-shift and left-shift operators are usually described as being "signed."

3: The unsigned right shift >>>

*n*This is the most complicated of the three. It moves the bits

*n*places to the right, and any bits which pass the least significant bit float off into the wild blue yonder, but it fills in from the left with 0s. So it**always**returns a positive answer, whether the original answer was positive or negative. For positive numbers it has exactly the same effect as the ordinary signed right-shift, so I won't draw itFor a negative number, eg -88 >>> 2, this is what happens

Remember that is you multiply 42 by 4 in 8 bits you get -88. I am afraid I can't think of a simple way to calculate the values you get from a >>> operator.

I hope this is of some help to you And it was a nice interesting question to answer, too.

[edit]Correct 84 / 2 = 5 to 84 / 21 = 5 and change ^2 to superscript 2 twice.[/edit]

Campbell Ritchie

Sheriff

Posts: 53760

127

Gitesh Ramchandani

Ranch Hand

Posts: 274

posted 9 years ago

OR

For example:

***********************************************************************

OR

For example:

and so on...

Regards,

Gitesh

[ March 20, 2008: Message edited by: Gitesh Ramchandani ]

left-shift << is equivalent to multiplying the number by 2,4,8...respectively for shifting by 1,2,3....positions

OR

Or stating more simply left-shifting a value by n positions, is the same as multiplying it by 2^n

For example:

***********************************************************************

right-shift >>/>>> is equivalent to dividing the number by 2,4,8...respectively for shifting by 1,2,3....positions

OR

Or stating more simply right-shifting a value by n positions, is the same as dividing it by 2^n

For example:

and so on...

**But in case of right-shift [>>] for a negative number, the above shortcuts do not apply.**

Regards,

Gitesh

[ March 20, 2008: Message edited by: Gitesh Ramchandani ]

Rekha Anand

Ranch Hand

Posts: 36

posted 9 years ago

Hello All,

I am sorry I took long to reply. I appreciate from the bottom of my heart the effort you all have put in to help me understand shifting. I tried some questions manually and was able to solve. There is still slight problem with >>> for negative numbers such as -16>>>3, the 32 bits are over-whelming. For instance...

-16>>>3

-16 : 11111111 11111111 11111111 11110000

-16>>>3 : 11111 11111111 11111111 11111110000

0 Fill: 00011111 11111111 11111111 11111110

Now that I have done the shifting " HOW DO I CONVERT THIS BIG BINARY NUMBER INTO DECIMAL DURING THE EXAM..?" It will take up a lot of time.

Thanks & Regards

Rekha

I am sorry I took long to reply. I appreciate from the bottom of my heart the effort you all have put in to help me understand shifting. I tried some questions manually and was able to solve. There is still slight problem with >>> for negative numbers such as -16>>>3, the 32 bits are over-whelming. For instance...

-16>>>3

-16 : 11111111 11111111 11111111 11110000

-16>>>3 : 11111 11111111 11111111 11111110000

0 Fill: 00011111 11111111 11111111 11111110

Now that I have done the shifting " HOW DO I CONVERT THIS BIG BINARY NUMBER INTO DECIMAL DURING THE EXAM..?" It will take up a lot of time.

Thanks & Regards

Rekha

posted 9 years ago

Well, unless you are taking the SCJP 1.4 exam, you will not need to perform any bitshifting operations.

Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.

Shivit Agarwal

Ranch Hand

Posts: 82

posted 9 years ago

Simple, use A.P series most of the calculation can be done in my mind if one is good with mathematics in very few seconds.

say your bits look like ,

11111111 1111111 11111100

As per your convinience take From either right to left or vice versa.

Say from right,

Count the no. of 1's until zero is encountered.Therefore consecutive 1's is 22. So, the above case A.P series can be written as

2^23 + 2^22 +.....2^2+ 0 + 0

---------------------

22's 1 (but mind it all are 1's are consecutive)

just apply the formula for sum= n/2(2*a+(n-1)/d)

PS: you may have to work little bit more if alternately bits are there but this method is still very fast.

[ March 23, 2008: Message edited by: Shivit Agarwal ]

say your bits look like ,

11111111 1111111 11111100

As per your convinience take From either right to left or vice versa.

Say from right,

Count the no. of 1's until zero is encountered.Therefore consecutive 1's is 22. So, the above case A.P series can be written as

2^23 + 2^22 +.....2^2+ 0 + 0

---------------------

22's 1 (but mind it all are 1's are consecutive)

just apply the formula for sum= n/2(2*a+(n-1)/d)

PS: you may have to work little bit more if alternately bits are there but this method is still very fast.

[ March 23, 2008: Message edited by: Shivit Agarwal ]

Have the determination of mirror which never fails to reflect in spite of being broken into pieces.<br /> <br />Kiss the hands you cannot bite.<br /> <br />An Optimist is one who starts taking a bath when he accidentally falls into the water.

Ali Khalfan

Ranch Hand

Posts: 129

Bert Bates

author

Sheriff

Sheriff

Posts: 8945

17

Campbell Ritchie

Sheriff

Posts: 53760

127

posted 2 years ago

… Are all exactly equal to the original value of i. So is

As long as the right operand is not 0. Remember the right operand is reduced to a few bits on its right (e.g. 5 bits for anA few years ago, I wrote: . . . unsigned right shift >>> . . .alwaysreturns a positive answer . . .

`int`which has 32 bits and 32 = 2⁵). If after that reduction the right operand is 0, then you might get a negative result. Remember

`i << 0`

i >> 0

i >>> 0

i >> 0

i >>> 0

… Are all exactly equal to the original value of i. So is

`i << 128`.

It is sorta covered in the JavaRanch Style Guide. |