Welcome to the first installment of the JavaRanch Journal edition of the SCJP Tip Line, etc. This column was inspired by my blog. This month, our topic of choice is bit shifting.
In my experience, a lot of people are just too "frightened" of bit shifting to spend any time studying the operations. With just a little study, questions on bit shifting quickly become "gimme" questions on the SCJP exam, rather than the impossible questions that people make them out to be. Let's take a quick look into bit shifting.
First off, let's consider the bare basics. Every primitive data type in Java is made of a set number of bytes. For example, a byte is, oddly enough, one byte, a short is two bytes, and an int is 4 bytes. Of course, a byte is equivalent to 8 bits, so a byte is 8 bits long, a short is 16 bits long, and an int is 32 bits long.
Now, let's start thinking about shifting bits. What is bit shifting? Well, it's exactly what it sounds like; we're going to slide the bits left or right a certain number of positions. Basically, we're going to "shift" them down the line. Let's start with this simple line of code:
byte b = 13;If we convert b, which has a value of 13, to binary, it looks like this:
When it comes to bit shifting, we have a few options. Obviously, we can shift the bits either to the left or to the right. I like to think of the bits as if they're sitting on a table that's just big enough to hold them. For a byte, you'd have a table able to hold 8 bits while an int would sit on a larger table that is able to hold 32 bits. When we shift to the left or to the right, the number on the far end "falls off" the table, never to be heard from again. As a quick example, let's shift our variable, b, to the right one position.
b = (byte)(b >> 1); 00001101 becomes 00000110 (which is 6 in decimal)
Notice that the right-most bit, which was a 1, has "fallen off" the table. It's gone forever. Of course, a byte contains 8 bits so, now that we've pushed one off the right side, we need to fill something in on the left. The right shift operator that I used will insert the same value as the sign bit on the left side. In Java, remember that the left-most bit is known as the "sign bit." If that bit is a 0, the number is positive and, if it is a 1, the number is negative. So, if the original value was negative, we'd shift in a 1 and, if it was positive, as was the case here, we'd shift in a 0. This operator is known as the "signed right shift" operator. Of course, we can shift by more than 1 position at a time, like this:
b = (byte)(b >> 3); 00001101 becomes 00000001 (which is 1 in decimal)
You might notice that a right shift is basically an integer division by a power of 2. Shifting right 1 position is the same as dividing by two, shifting right 3 positions is the same as diving by 2^3, or 8.
Also, notice the casting that I'm doing. When you perform a shift operation, both operands, the value to be shifted and the amount to shift it by, must be an int or a long. If they aren't, they are promoted (if they can be – if not, you end up with a compiler error). The result of the operation is the type of the left hand operand, which will be an int or a long. As neither of those types are assignable to a byte, I must cast it as a byte or the compiler will complain.
That's really all there is to bit shifting. Now, we should probably look at the other bit shifting operations. We've already looked at the signed right shift operator (>>), but there are two more operations: the left shift operator (<<) and the unsigned right shift operator (>>>).
The left shift operator is identical to the right shift operator that we discussed previously except that it will shift the value to the left instead of to the right. For example:
b = (byte)(b << 2); 00001101 becomes 00110100 (which is 52 in decimal)
Again, notice that shifting to the left is just like multiplying by a power of two (whereas a right shift was a division by a power of two). In this case, we shifted left two positions, which is the same as multiplying by 2^2, or 4. Obviously 13 * 4 is 52, which is the same result we get from our bit shift operation. A left shift operation always inserts 0's to the right hand side.
Keep in mind, though, that a left shift can result in "overflow." Overflow occurs when we go beyond the limits of the range of the data type we're using. For a byte, our maximum value is 127. So what happens if we take 127 and shift it to the left? Well, let's look at that:
127 in binary is 01111111 Shifted left one position, it becomes 11111110.
Notice that, by shifting 127 to the left, we have turned a positive number into a negative number. Our result is –2. That result, -2, is certainly not equal to 127 * 2, which should be 254. The value 254, of course, doesn't fall within the range of a byte – this is overflow. When left shifting, you need to be aware of overflow.
The final shift operator, the unsigned right shift operator, is a right shift that behaves just like the left shift. This operator will always fill in zeros when shifting to the right. So, if we were to take a negative number, such as –32 (which is 11100000 in binary) and shift it to the right using our normal signed operator, we'd see this:
byte b = -32; b = (byte)(b >> 1); 11100000 becomes 11110000 (which is -16 in decimal)
Notice that, by right shifting a negative number, we push a one into the sign bit and the number remains negative. However, we now have this second option for shifting to the right, the unsigned right shift. The unsigned right shift operator ignores the sign bit and blindly pushes a zero into the left-most position. Let's do a couple quick examples with an unsigned right shift.
int i1 = -32; int i2 = 13; i1 = i1 >>> 1; i2 = i2 >>> 2; i1, which was 11111111 11111111 11111111 11100000, becomes 01111111 11111111 11111111 11110000 (which is 134217727 in decimal) i2, which was 00000000 00000000 00000000 00001101, becomes 00000000 00000000 00000000 00000011 (which is 3 in decimal)
That's really all there is to bit shifting. It's much simpler than many people make it out to be. However, before I wrap this article up, let's throw a wrench into things. The right hand operand of a shift operator must be an int. Well, in Java, ints are "signed" variables (they can be positive or negative), so this is a legal line of code:
byte b = 13; b = (byte)(b >> -6);
So now the question is, what does that do? Does it shift left instead of right? Does it give an error? Actually, it does neither. When performing a shift, only a portion of the right hand operand is used. If you're shifting an int, you'll use only the right-most 5 bits of the shift value. That means that the amount you shift by will always fall within the range of 0 and 31. If you're shifting a long, you'll use only the right-most 6 bits of the shift value. In that case, your shift distance falls within 0 and 63. Let's see how that works with our last example:
-6 in binary is 11111010
We're shifting an int (remember that anything smaller than an int is promoted to an int) so we use only the right-most 5 bits of that value. Therefore, we're shifting by 26 (11010 in binary is 26 in decimal). So, our previous line equates to this:
b = (byte)(b >> 26);
Of course, if we shift 13 to the right by 26 positions, we've managed to push all of the real data off the table and replaced it with zeros. So, in the end, we have b equal to 0.
Hopefully you've learned a few intricacies about bit shifting that you might not have known before. Be sure to check my blog, the SCJP Tip Line, for more similar tips and look for more articles like this in future editions of the JavaRanch Journal.
If you'd like to consult the Java Language Specification regarding bit shifting, check out §15.19 Shift Operators.