posted 21 years ago
In case it isn't clear, I just want to add to Thomas' explanation that int is 32 bits...since all bitshift operations are promoted to ints (for the operators (or numbers), that is), the MAXIMUM number of shifts would be 31 (like he said, 32 mod 32 (32 % 32 in Java) = 0 (the remainder is 0).
Remember the signed and unsigned shifting!!!
if you shift x >> 2 (I hope I don't get this backwards!), the sign goes along and you get this for x = 15:
0000 0000 0000 0000 0000 0000 0000 1111
becomes
0000 0000 0000 0000 0000 0000 0000 0011 (note all the numbers shift 2 to the right and thus two "1" symbols fall off.
So 15 >> 2 = 3
But for x = -15, you have this representation
First...to reverse, you'll be flipping the bit representation of 15 - 1 (since to get the value of a negative number, you flip all bits and add 1...so I'm doing the reverse to create -15)
14 is
0000 0000 0000 0000 0000 0000 0000 1110
(so if you had flipped bits and added 1, it would end in 1111 which = 15)
Now, flip the bits to get the representation of -15 as stored in the int variable:
1111 1111 1111 1111 1111 1111 1111 0001
When you shift -15 >> 2, that is a signed shift...so the 1 bit stays a 1 bit even though you are shifting right...the net result is that bits keep being added to the left while those on the right may drop off...the first shift results in:
1111 1111 1111 1111 1111 1111 1111 1000 (note everything shifted right, but then the leftmost bit was turned back into a 1)
The second shift becomes
1111 1111 1111 1111 1111 1111 1111 1100
Now reverse it:
0000 0000 0000 0000 0000 0000 0000 0011
add 1
0000 0000 0000 0000 0000 0000 0000 0100
And -15 >> 2 = 4
Now throw the sign back on: -4
That's two's complement...somewhat confusing, but once you understand the basic formula of flip, add 1, put the negative sign back in, it isn't so bad.
Now....there is also the unsigned RIGHT shift (no left one as that leftmost bit would fall off and thus becomes irrelevant)....the difference is that instead of the sign bit being turned back on if negative after a shift, in this case, the sign bit is not turned back on and you have a shift that looks the same as it would for a positive number.
Therefore, with x = 15:
0000 0000 0000 0000 0000 0000 0000 1111
you get 3 again (ends in 0011)
but with x = -15:
1111 1111 1111 1111 1111 1111 1111 0001
you get
0011 1111 1111 1111 1111 1111 1111 1100
Note that this becomes a very big POSITIVE number of 1073741820 (thus, unsigned)....but there is one case where an unsigned shift does NOT become positive...
if it is shifted by a multiple of 32 digits, nothing happens (remember the x % 32 = 0?).
BTW, I learned nearly all of this from Head First Java...if you can afford at least a 1 week detour, this book is well worth it for the incredibly solid foundation it lays. Actually, now that I think about it, it may have been in the cert book, but I'm fairly certain it was in the HFJ. Both are must-reads, IMHO.
Ross