How Do Shift Operators Work in Java

How do shift operators work in Java?

System.out.println(Integer.toBinaryString(2 << 11));

Shifts binary 2(10) by 11 times to the left. Hence: 1000000000000

System.out.println(Integer.toBinaryString(2 << 22));

Shifts binary 2(10) by 22 times to the left. Hence : 100000000000000000000000

System.out.println(Integer.toBinaryString(2 << 33));

Now, int is of 4 bytes,hence 32 bits. So when you do shift by 33, it's equivalent to shift by 1. Hence : 100

Why do we need to use shift operators in java?

Division and multiplication are not really a use of bit-shift operators. They're an outdated 'optimization' some like to apply.

They are bit operations, and completely necessary when working at the level of bits within an integer value.

For example, say I have two bytes that are the high-order and low-order bytes of a two-byte (16-bit) unsigned value. Say you need to construct that value. In Java, that's:

int high = ...;
int low = ...;
int twoByteValue = (high << 8) | low;

You couldn't otherwise do this without a shift operator.

To answer your questions: you use them where you need to use them! and nowhere else.

What are bitwise shift (bit-shift) operators and how do they work?

The bit shifting operators do exactly what their name implies. They shift bits. Here's a brief (or not-so-brief) introduction to the different shift operators.

The Operators

>> is the arithmetic (or signed) right shift operator.
>>> is the logical (or unsigned) right shift operator.
<< is the left shift operator, and meets the needs of both logical and arithmetic shifts.

All of these operators can be applied to integer values (int, long, possibly short and byte or char). In some languages, applying the shift operators to any datatype smaller than int automatically resizes the operand to be an int.

Note that <<< is not an operator, because it would be redundant.

Also note that C and C++ do not distinguish between the right shift operators. They provide only the >> operator, and the right-shifting behavior is implementation defined for signed types. The rest of the answer uses the C# / Java operators.

(In all mainstream C and C++ implementations including GCC and Clang/LLVM, >> on signed types is arithmetic. Some code assumes this, but it isn't something the standard guarantees. It's not undefined, though; the standard requires implementations to define it one way or another. However, left shifts of negative signed numbers is undefined behaviour (signed integer overflow). So unless you need arithmetic right shift, it's usually a good idea to do your bit-shifting with unsigned types.)

Left shift (<<)

Integers are stored, in memory, as a series of bits. For example, the number 6 stored as a 32-bit int would be:

00000000 00000000 00000000 00000110

Shifting this bit pattern to the left one position (6 << 1) would result in the number 12:

00000000 00000000 00000000 00001100

As you can see, the digits have shifted to the left by one position, and the last digit on the right is filled with a zero. You might also note that shifting left is equivalent to multiplication by powers of 2. So 6 << 1 is equivalent to 6 * 2, and 6 << 3 is equivalent to 6 * 8. A good optimizing compiler will replace multiplications with shifts when possible.

Non-circular shifting

Please note that these are not circular shifts. Shifting this value to the left by one position (3,758,096,384 << 1):

11100000 00000000 00000000 00000000

results in 3,221,225,472:

11000000 00000000 00000000 00000000

The digit that gets shifted "off the end" is lost. It does not wrap around.

Logical right shift (>>>)

A logical right shift is the converse to the left shift. Rather than moving bits to the left, they simply move to the right. For example, shifting the number 12:

00000000 00000000 00000000 00001100

to the right by one position (12 >>> 1) will get back our original 6:

00000000 00000000 00000000 00000110

So we see that shifting to the right is equivalent to division by powers of 2.

Lost bits are gone

However, a shift cannot reclaim "lost" bits. For example, if we shift this pattern:

00111000 00000000 00000000 00000110

to the left 4 positions (939,524,102 << 4), we get 2,147,483,744:

10000000 00000000 00000000 01100000

and then shifting back ((939,524,102 << 4) >>> 4) we get 134,217,734:

00001000 00000000 00000000 00000110

We cannot get back our original value once we have lost bits.

Arithmetic right shift (>>)

The arithmetic right shift is exactly like the logical right shift, except instead of padding with zero, it pads with the most significant bit. This is because the most significant bit is the sign bit, or the bit that distinguishes positive and negative numbers. By padding with the most significant bit, the arithmetic right shift is sign-preserving.

For example, if we interpret this bit pattern as a negative number:

10000000 00000000 00000000 01100000

we have the number -2,147,483,552. Shifting this to the right 4 positions with the arithmetic shift (-2,147,483,552 >> 4) would give us:

11111000 00000000 00000000 00000110

or the number -134,217,722.

So we see that we have preserved the sign of our negative numbers by using the arithmetic right shift, rather than the logical right shift. And once again, we see that we are performing division by powers of 2.

Shift Operator () Explanation

Binary representation of 1 is 00000000000000000000000000000001

1 << 17 will move the last 1 in the binary representation 17 places left, which will result in 0000000000000100000000000000000, which when converted back to decimal results is 131072

What does the symbol mean in Java?

12 is 1100 in binary. A right shift (>> is the bitwise right shift operator) by one bit produces

1100 -> 0110

which comes out to be 6.

Thus we have that,

6 - 1 = 5

How does bitshifting work in Java?

Firstly, you can not shift a byte in java, you can only shift an int or a long. So the byte will undergo promotion first, e.g.

00101011 -> 00000000000000000000000000101011

11010100 -> 11111111111111111111111111010100

Now, x >> N means (if you view it as a string of binary digits):

The rightmost N bits are discarded
The leftmost bit is replicated as many times as necessary to pad the result to the original size (32 or 64 bits), e.g.

00000000000000000000000000101011 >> 2 -> 00000000000000000000000000001010

11111111111111111111111111010100 >> 2 -> 11111111111111111111111111110101

Shift Operator in Java

When you shift an integer with the << or >> operator and the shift distance is greater than or equal to 32, you take the shift distance mod 32 (in other words, you mask off all but the low order 5 bits of the shift distance).

This can be very counterintuitive. For example (i >> 32) == i, for every integer i. You might expect it to shift the entire number off to the right, returning 0 for positive inputs and -1 for negative inputs, but it doesn't; it simply returns i, because
(i << (32 & 0x1f)) == (i << 0) == i.

Getting back to your original problem, (i << 33) == (i << (33 & 0x1f))
== (i << 1). You can do the whole thing in binary if you like. 270 in binary is : 0000 0000 0000 0000 0000 0001 0000 1110 Shifting right by 1,
you get: 0000 0000 0000 0000 0000 0000 1000 0111 which is 135.

But a better way to do this problem in your head is to dispense with the binary entirely.
The value of i >> s is floor(i / 2<sup>s</sup>) (where s has already been masked off so it's less than 32). So, 270 << 1 = floor(270/2) = 135.

http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.19

Java Shift Operator and auto promotion

I feel that the other answers are a bit incomplete.

It's true that an int is 32 bits, and the language doesn't let you shift more than 32 bits. What's gotten left out is that if you tell it to shift more than 32 bits, the shift amount will be taken modulo 32. That is, if x is an int, x >> 32 is the same as x >> 0 (i.e. just x), x >> 33 is the same as x >> 1, x >> 66 is the same as x >> 2, etc. Using only the low-order 5 bits of the right argument is the same as taking the argument modulo 32 (using the mathematical definition, so that -1 mod 32 == 31, -2 mod 32 == 30, etc.).

Similarly, long is 64 bits, which means that the right argument is computed modulo 64, which is the same as using only the low-order 6 bits of the right argument.

Why Java did it this way, I don't know. In my opinion, it would be more consistent if it simply let you shift by a large amount, shifting all the bits out of the integer and resulting in 0 (except that >> sign-extends, so the result would be 0 or -1). It would be consistent mathematically, because for positive x and y, x >> y would always be equal to x / (2^y) truncated down to an integer, even if y >= 32. Java's way of handling shift amounts that are >= 32 or >= 64 isn't useful in any way I can see.

What if a cast operator is used in shift operators

The Java 8 JLS also states in §5.6.1:

5.6.1. Unary Numeric Promotion
Some operators apply unary numeric promotion to a single operand, which must produce a value of a numeric type:
...
Otherwise, if the operand is of compile-time type byte, short, or char, it is promoted to a value of type int by a widening primitive conversion (§5.1.2).
...

Thus, if we take the following expression:

int i = ...
short s = (short) i << 2;

Will result in a compiler error:

Main.java:4: error: incompatible types: possible lossy conversion from int to short
short s = (short) i << 2;

Ideone demo

This is due to the fact that the cast binds to the first argument of the shift, not the whole expression. Here is the whole expression with explicit parenthesis:

short s = ((byte) i) << 2;

Whereas

int i = ...;
int j = (short) i << 2;

Will successfully compile.

Ideone demo

So the effective bits to use for anything < int is the same as for int (5 bits) since they are upcasted to int automatically.

If you cast the result of the whole expression to, e.g. short (short s = (short) (i << 2), then there is no automatism that takes place in the compiler. But Bohemian's answer gives a logical bound as to what bits of the right hand operator will effectively influence the value after the cast.

In newer JLS versions, the section has been reworded. For example, in Java 14 JLS, §5.6 we find (the section is shortened for breviety, I recommend reading the whole paragraph to get the full context):

5.6. Numeric Contexts
Numeric contexts apply to the operands of arithmetic operators, array creation and access expressions, conditional expressions, and the result expressions of switch expressions.
An expression appears in a numeric arithmetic context if the expression is one of the following:
...
An operand of a shift operator <<, >>, or >>> (§15.19). Operands of these shift operators are treated separately rather than as a group. A long shift distance (right operand) does not promote the value being shifted (left operand) to long.
...
Numeric promotion determines the promoted type of all the expressions in a numeric context. The promoted type is chosen such that each expression can be converted to the promoted type, and, in the case of an arithmetic operation, the operation is defined for values of the promoted type. The order of expressions in a numeric context is not significant for numeric promotion. The rules are as follows:
...

Next, widening primitive conversion (§5.1.2) and narrowing primitive conversion (§5.1.3) are applied to some expressions, according to the following rules:
...
Otherwise, none of the expressions are of type double, float, or long. In this case, the kind of context determines how the promoted type is chosen.
In a numeric arithmetic context or a numeric array context, the promoted type is int, and any expressions that are not of type int undergo widening primitive conversion to int.
In a numeric choice context, the following rules apply:
...
Otherwise, the promoted type is int, and all the expressions that are not of type int undergo widening primitive conversion to int.
...

How Do Shift Operators Work in Java