problem with bit shift >>>.

I have gone thru various books but all have made me confused about the operation and where can we use this operator.
can someone explain me this concept in a simplified manner i will be very thankful.

Herewith my attempt:
The >>> operator is a binary operator.This means that it requires two operands, one to the left and the other to the right.It is used ONLY with integer types, that is, byte,short,char,int, and long.If the left operand is narrower than an int, it is promoted to an int prior to the operation.The effect of this operator is, like the >> operator, to shift the BITS of the left operand right by a number equivalent to the right operand.Thus 3>>>2 will shift 3 to the right two times.This is called an unsigned right shift because it does not preserve the original sign of the number.Thus a negative number right shifted with this operator ends up being positive.This happens because all the shifted bits are filled with zeros(Contrast this with the signed right shift, where the shifted bits are filled with what was in the most significant bit prior to the op).
In my opinion, this op appears confusing especially when used with negative numbers.To understand this, you need to understand that integer types are represented in Java in a format called TWO's COMPLEMENT.To represent a -ve number in this format, do the following.
1.First, write the bit pattern of the equivalent +ve number.
(Let us use -3 as a case study) so we write +3 first
:0000 0000 0000 0000 0000 0000 0000 0011 (32 bits)
2.Invert all the bits, thus 0's become 1's and vice versa
:1111 1111 1111 1111 1111 1111 1111 1100
3.Add 1 to this result:
:1111 1111 1111 1111 1111 1111 1111 1101 //This is -3
in two's complement.

So let us shift -3 by 2. Thus evaluate -3>>>2
:_ _ 11 1111 1111 1111 1111 1111 1111 1111 (See, we just cut
off two bits from the right edge.)
The _ _ are used to indicate the shifted bits. Now we need to fill them. So with >>>, we fill them with 0's.
:0011 1111 1111 1111 1111 1111 1111 1111
Because the most significant bit is 0, then we convert this directly to get the decimal value 1073741823.Compare with -3>>2 where you get -1.
I hopw this helps. Others may check and correct where I am not accurate and I welcome more questions where you need further clarity.
Herbert

Hi Herbert,
That was a very nice explanation.

Because the most significant bit is 0, then we convert this directly to get the decimal value 1073741823.Compare with -3>>2 where you get -1.

So, what we do if the MSB is 1 ? Could you please explain how
-3<<<2 will be -1 ?
Thanks
ARS Kumar

and the code in action ....

Kumar:
there is no <<< operator in java.
Regds.
- satya

Hi Satya
That was a mistake

Once again
Hi Herbert,
That was a very nice explanation.

Because the most significant bit is 0, then we convert this directly to get the decimal value 1073741823.Compare with -3>>2 where you get -1.

So, what we do if the MSB is 1 ? Could you please explain how
-3>>2 will be -1 ?
Thanks
ARS Kumar

Allow me ......
-3 = 1111 1111 1111 1111 1111 1111 1111 1101
-3 >> 2 = _ _ 11 1111 1111 1111 1111 1111 1111 1111
Since this is a signed right shift, the _ 's are occupied
by what ever was existing at those locations prior to the
shift (1 in our case). SO we get
-3 >> 2 = 1111 1111 1111 1111 1111 1111 1111 1111
Which is -1 in decimal notation.
Regds.
- satya

Hi Satya
Thanks for your help. Little more !!!

-3 >> 2 = 1111 1111 1111 1111 1111 1111 1111 1111
Which is -1 in decimal notation.

You mean +1 is 0000 0000 0000 0000 0000 0000 0000 0001 and
two's complement of that is
1111 1111 1111 1111 1111 1111 1111 1110 + 1
i.e.,
1111 1111 1111 1111 1111 1111 1111 1111
and so is equal to -1 ... Is this true ?
Thanks
ARS Kumar

Kumar,
What Herbert said is as such correct. There is a small add-on to Herbert's post. I come back to that latter.

I assume you now know how to represent a -ve number in 2's complement form as Herbert explained ( first write the +ve number in binary / invert all bits / add 1 ).
For >>> (unsigned right shift) operator we fill the leftmost _ _ bits with 0 (zeros) bits. For >> (signed right shift) operator we fill the left most _ _ bits with the type of bit at the MSB (Most Significant bit) position.
So now for -3
Step1 : 1111 1111 1111 1111 1111 1111 1111 1101 (-3)
Step2 : __11 1111 1111 1111 1111 1111 1111 1111 (>> 2 bits)
Step3 : 1111 1111 1111 1111 1111 1111 1111 1111
(Since in step1 the MSB was 1 we fill with 1's for the _ _ postions)
Now here comes your doubt

. To know what is
Step3 : 1111 1111 1111 1111 1111 1111 1111 1111 , You have to do the reverse of what we do to represent a -ve no. Logically thinking, if you look at any binary representation with the MSB set to 1 then it represents a -ve number. (provided this binary representation type has a -ve range) Why I am saying this is the char type in Java is ALL POSITIVE , NO NEGATIVE range. So if this binary rep , is for a char var then, it represents a +ve no.
Assuming your example of -3 is an byte/short/int/long which are all have the NEGATIVE range also apart from a zero and a POSITIVE RANGE, now the final result in Step3 has a MSB set to 1, implies it is a -ve number in decimal, to find out what the -ve no is , do the reverse, which is (substract 1, invert all bits).
Reverse operation
Step3 : 1111 1111 1111 1111 1111 1111 1111 1111
Step2 : 1111 1111 1111 1111 1111 1111 1111 1111
: 0000 0000 0000 0000 0000 0000 0000 0001 (subtract 1)
Step1 : 1111 1111 1111 1111 1111 1111 1111 1110 (after sub1)
Step0 : 0000 0000 0000 0000 0000 0000 0000 0001 (invert all bits VALUE=1)
After Step 0 we know that the result represents a decimal val 1. So the original no at step 3 was indeed -ve of this Step0 result which is -1.
Herbert,
leftoprnd >> / >>> / << rghtOprnd
The point I wanted to add is if the righthand operand is greater than 32 or greater than 64 then what happens ? We all know that all bit shift operations are done either on int/long type left hand operand. If the left hand operand is 'int' type then only the last 5 bits of right hand operand is used for determining how many bits we have to shift on LHS. Simillarly if the LHS is 'long' then
last 6 bits of right hand operand is used to determine the total no. of bits to be shifted oh LHS operand. This is the only point I wanted to make it clear. Otherwise what you said are all correct.

regds
maha anna

[This message has been edited by maha anna (edited May 31, 2000).]

ARS Kumar,
When the most significant bit is 1, we DO NOT convert directly to get the decimal equivalent.
1.We Invert the bits again.
: so 1111 1111 1111 1111 1111 1111 1111 1111 becomes
0000 0000 0000 0000 0000 0000 0000 0000
2. We add 1. This becomes
0000 0000 0000 0000 0000 0000 0000 0001
This becomes the MAGNITUDE of our result, but we keep in mind that the sign is -ve. So the answer is -1.
I hope this helps.
Herbert.

Hi Maha/Herbert
I did cover bit manipulation two weeks ago and was under the impression that I knew everything about that

Thanks for your detailed explanation, Maha/Herbert it really helps.
ARS Kumar

Kumar,
I understand what you say. Understanding of bit shift operations needs a LOTS OF PRACTICE. We did it looooong back during Engg 1st to 8th semesters here and there always. Now it helps. Not to worry. Do some hands-on experiments with -ve and +ve nos and >>/>>>/<< shifting. This really helps.
regds
maha anna

Hi All,
I am confused with how to evaluate the expression for example -25>>>3,I have already gone through the link but i am still confused as to how you would represent -25>>>3 in decimal notation,for -25>>2 i have applied the technique and got the result but for -25>>>3 we will get the answer as
536870908.These are the steps i followed
-25 in Binary
1111 1111 1111 1111 1111 1111 1110 0111
-25>>>3 Will give
0001 1111 1111 1111 1111 1111 1111 1100
Now how do you evaluate this?.Do we need to write 0*2+0*(2*2)+1(0*2*2)+......(1*(2 raised to 29))
and then calculate.Please explain this to me.
Surya

-25>>>3 Will give
0001 1111 1111 1111 1111 1111 1111 1100
=
2^2+2^3+2^4+2^5+...+2^28+2^29;
do u think there was a catch or something ?
Regds.

- satya

Hi Satya
There is no catch,if this kind of question comes in the exam and if we are given choices like

536870908
123234443
454566757
245466456
Then how can we calculate 2^29+2^28....etc in the exam.
To Moderators,i posted the same question as a new topic since no one was answering it,since i got a response here,its ok if you can close the thread.Sorry for the duplication.

Hi
This is the question asked by Surya..........I also can't understand this ..if some one can explain clearly
Sonali
I am confused with how to evaluate the expression for example -25>>>3,I have already gone through the link but i am still confused as to how you would represent -25>>>3 in decimal notation,for -25>>2 i have applied the technique and got the result but for -25>>>3 we will get the answer as
536870908.These are the steps i followed
-25 in Binary
1111 1111 1111 1111 1111 1111 1110 0111
-25>>>3 Will give
0001 1111 1111 1111 1111 1111 1111 1100
Now how do you evaluate this?.Do we need to write 0*2+0*(2*2)+1(0*2*2)+......(1*(2 raised to 29))
and then calculate.Please explain this to me.

I can almost (except that I am not authorised) gaurentee
that Sun will not ask such qstns in the exam At the most I would
expect the choices to be like this:
a. 536870908
b. 123234443
c. 454566757
d. 245466459
where in you have only one even number and that would be the
answer. Since in this case the the 2^0 bit is not 1.
I am almost positive that such qstns will not appear. What
is being tested is your concept of ">>", "<<" ">>>" and may
be "<<<". Not how to eveluate 2^29.
ps: "<<<" doesnot exist. However if a qstn on this one appears
your answer may include a choice for "compile error" or
"none of the above" something like that.
Stop thinking abt how to evaluate complex thing and
concentrate on the essential concepts. All the best.
Hope this helps.
Regds.

- satya

Thanks for your reply Satya
Sonali

Hi,
Ok Satya,i go by your word,if at all such a question appears in the exam then i am going to take the equivalent marks from your score,what do you say...just joking

.Anyway thanks for the answer.Bye.

if at all such a question appears in the exam then i am going to take the equivalent marks from your score,what do you say.
Well, I don't mind if you want to take some of my marks,
but before that, I would be intrested in knowing how you
are sure that this ans of your is wrong?
I wanted to see if I could get a feedback from Sun/Prometric
as to what ans I got wrong....
Regds.

- satya

I get all of what you guys said but for these few lines of maha anna.....
maha can you clarify why only the last 5 bits of an int variable and last 6 bits of a long variable is used. suppose:
int i=12343;
i=i>>20;
won't this shift the value by 20 bits? pardon if am wrong in understanding this..
Thanx in advance. Ganesh
*****
The point I wanted to add is if the righthand operand is greater than 32 or greater than 64 then what happens ? We all know that all bit shift operations are done either on int/long type left hand operand. If the left hand operand is 'int' type then only the last 5 bits of right hand operand is used for determining how many bits we have to shift on LHS. Simillarly if the LHS is 'long' then last 6 bits of right hand operand is used to determine the total no. of bits to be shifted oh LHS operand.

seems you have answered your qstn.....

i=i>>20;
won't this shift the value by 20 bits? pardon if am wrong in
understanding this..
write 20 in terms of bits and then see what you get
when you truncate this bit value to th 5 right most bits.
Use that value to shift the int i. 5 bits since i is
an int. IMO, You got the point right.
Regds.

- satya

Originally posted by satya5:
write 20 in terms of bits and then see what you get
when you truncate this bit value to th 5 right most bits.
Use that value to shift the int i. 5 bits since i is
an int. IMO, You got the point right.
Regds.
- satya[/B]

Satya,
Could you please elaborate on this. I am not able to understand this part
Thanks,
Anand

I had one more qstn:
For -ve integers (e.g. -64), we talked about adding 1 after the binary representation of the postive part (64)
Is binary addition an "or" addition.
Step (1) for 64
0000 0000 0000 0000 0000 0000 0100 0000
Step (2) Invert the bits
1111 1111 1111 1111 1111 1111 1011 1111
Step (3) Add 1
What will I get here?
The answer is
1111 1111 1111 1111 1111 1111 1100 0000

I am not able to understand how adding 1 gives this
final result. Could some please help me.
Thank You,
Anand

Originally posted by Anand Iyer:
Satya,
Could you please elaborate on this. I am not able to understand this part
Thanks,
Anand

Originally posted by satya5:
write 20 in terms of bits and then see what you get
when you truncate this bit value to th 5 right most bits.
Use that value to shift the int i. 5 bits since i is
an int. IMO, You got the point right.
Boy, I feel this is too much to ask...

What I mean here is:
20 = 0001 0100 (last eight bits of bin rep of 20)
Use the last five bits to determine by how many digits
we should bit shifting. Using the last 5 digits (since the
LHS is an int) we get the value of 20. So we shift the LHS
by 20 bits.
This rule can be more clear when you use a number something
like 123456 for the RHS. I prefer not to explain it. Please
wouk it out. You do not have to take the number 123456, please
take a number which is greater than 2^7.
It will be more clear then. Actually, I remember posting
such a bit shift example, please search if you are more
intrested.

Just trying to force you to do some homework

Regds.

- satya

Hie Nganesh,
You wrote :
-----------------------------------------------------------------
I get all of what you guys said but for these few lines of maha anna.....
maha can you clarify why only the last 5 bits of an int variable and last 6 bits of a long variable is used. suppose:
int i=12343;
i=i>>20;
won't this shift the value by 20 bits? pardon if am wrong in understanding this..
Thanx in advance. Ganesh
-----------------------------------------------------------------
Let me try to clarify abit.When the left hand operand is an int, then only 5 bits of the right hand operand are used to do the shift.This is the case because an int can only be shifted 0 through 31 times, that is 32 times in total.Consequently we need only 5 bits of the right operand because that is the greatest number of bits we need to represent 32, i,e binary 100000.The same rationale applies for the case when the LHS is a long.In this case we know that we can shift a long 0 through 63 times, a total of 64.Therefore we only need that number of bits that is just sufficient enough to accomodate 64 shifts. Apparently 64 will fit in 6 bits, thus binary 1000000.
Infact the technic of performing modulo operator can be applied generally, that is even if the RHS<32 for an int shift or RHS<64 for a long shift.<br /> To take your example:<br /> int i = 12343;<br /> i>>20.
You can do the modulo operator here to determine how many times to shift. So you do 20%32, and you get 20. so you will shift 20 times indeed.
If you want to try counting the bits, just for the sake of practice then you can write 20 in binary :
0000 0000 0000 0000 0000 0000 0001 0100.
Then if you count 5 bits(low level) you get 10100 which is 20 so you shift 20 times.
Regards,
Herbert

Originally posted by Anand Iyer:
I had one more qstn:
For -ve integers (e.g. -64), we talked about adding 1 after the binary representation of the postive part (64)
Is binary addition an "or" addition.
Step (1) for 64
0000 0000 0000 0000 0000 0000 0100 0000
Step (2) Invert the bits
1111 1111 1111 1111 1111 1111 1011 1111
Step (3) Add 1
What will I get here?
The answer is
1111 1111 1111 1111 1111 1111 1100 0000

I am not able to understand how adding 1 gives this
final result. Could some please help me.
Thank You,
Anand

Anand:
Please use this link to follow how to convert negative decimal
numbers to binary form and back. IMO, it is very clearly
explained.
Regds.

- satya

another question on shift operators:-
for a primitive data type long if I want to left shift(<<) more than 63 times(say 64 times) how can I get a result. I tried it and it gives a -ve number.

Know of anything like a tutorial or calculator on the web that one can mess around with? For me it's about like counting on my fingers at a snail's pace. LOL
appreciatively, Steve

Satya
I think you mistook Anand's question. He wants to know how to move from Step(2) to Step(3) i.e. adding 1 to a binary number.
Anand
Adding 1 to a binary number exactly behaves like adding 1 to 9 in decimal base. i.e if you add 1 to 9 (in decimals) you would place 0 in the last digit and carry forward a 1 so that your answer is 10. Similarly in binary base, if you add 1 to, say, 10101, following the same convention, it will be 10110. Important thing to note that if you add 1 to, say, 1111 then it would be 10000 and NOT 0000.
I have not read this anywhere but have ingrained it by trial & error. Would appreciate if somebody feels otherwise or if someone can 'throw' exceptions to this thumb rule

.

Shiny:
Good explanation. You are correct in explaining the
addition of 1 to a binary number.

I might have gotten Anand wrong

Regds.

- satya

Thanks Satya and Shiny... very much