# NUM14-J. Use shift operators correctly

The shift operators in Java have the following properties, according to The Java Language Specification (JLS), §15.19, "Shift Operators" [JLS 2015]:

• The `>>` right shift is an arithmetic shift; the `>>>` right shift is a logical shift.
• The types `boolean`, `float`, and `double` cannot use the bit-shifting operators.
• When the value to be shifted is of type `int`, only the five lowest-order bits of the right-hand operand are used as the shift distance. That is, the shift distance is the value of the right-hand operand masked by 31 (0x1F). The shift distance actually used is consequently always in the range 0 to 31, inclusive.
• When the value to be shifted (left operand) is type `long`, only the last 6 bits of the right-hand operand are used to perform the shift. The shift distance is the value of the right-hand operand masked by 63 (0x3F). The shift distance actually used is consequently always in the range 0 to 63, inclusive.

The value to the right of a shift operation must be within the appropriate range for the type of the numeric value to the left of the shift operation. That is, if the left numeric type is a `long`, the right value must be within the range [0, 63]; otherwise, the right value must be within the range [0, 31].

## Arithmetic vs. Logical Shift

The JLS, §15.19 [JLS 2015], defines the behavior of the arithmetic shift operator as follows:

The value of n>>s is n right-shifted s bit positions with sign-extension. The resulting value is floor(n / 2s). For nonnegative values of n, this is equivalent to truncating integer division, as computed by the integer division operator /, by two to the power s.

The JLS also defines the behavior of the logical shift operator:

The value of n >>> s is n right-shifted s bit positions with zero-extension, where:

• If n is positive, then the result is the same as that of n >> s.

• If n is negative and the type of the left-hand operand is int, then the result is equal to that of the expression (n >> s) + (2 << ~s).

• If n is negative and the type of the left-hand operand is long, then the result is equal to that of the expression (n >> s) + (2L << ~s).

The added term (2 << ~s) or (2L << ~s) cancels out the propagated sign bit.

Note that, because of the implicit masking of the right-hand operand of a shift operator, ~s as a shift distance is equivalent to 31-s when shifting an `int` value and to 63-s when shifting a `long` value.

Never use the arithmetic shift operator when the logical shift operator is required.

### Noncompliant Code Example (Arithmetic vs. Logical)

In this noncompliant code example, method `countOneBits` loops forever on negative inputs because the `>>` operator performs an arithmetic shift rather than a logical shift:

```static int countOneBits(long value) {
int bits = 0;
while (value != 0) {
bits += value & 1L;
value >>= 1; // Signed right shift, by one
}
return bits;
}
```

### Compliant Solution (Arithmetic vs. Logical)

This compliant solution uses the logical shift operator `>>>`, which clears vacated bits (that is, shifts in zero-bits on the left):

```static int countOneBits( long value ) {
int bits = 0;
while (value != 0) {
bits += value & 1L;
value >>>= 1;
}
return bits;
}
```

## Promotion

Shift operands of type `byte`, `short`, or `char` are promoted to the type `int`. Operands of type `int` or `long` preserve their types. Unlike other arithmetic operators, promotion of the left operand of a shift operator is independent of the type of the right operand. Consequently, a left operand of type `byte` is promoted to type `int`, even when the shift distance (the right operand) is type `long`.

### Noncompliant Code Example (Promotion)

In this noncompliant code example, the programmer intends to shift a byte value two bits to the right (with zero fill). However, the JLS specifies that the left operand must be promoted to either type `int` or type `long` (`int`, in this case); this promotion performs sign extension. Because of the promotion, the result of the shift for negative input values will be a large positive number, and the programmer could find this result surprising.

```byte b = /* Initialize */;
int result = b >>> 2;
```

### Compliant Solution (Promotion)

This compliant solution uses a bitmask to clear the upper 24 bits (whose value was produced by sign extension), generating the intended result.

```byte b = /* Initialize */;
int result = ((int) b & 0xFF) >>> 2;
```

The explicit cast to type `int` is redundant, but it clarifies the expected type.

## Truncation of Shift Distance

When the left-hand operand is of type `int`, the right-hand operand (`exp`) is masked by 31 (0x1F). A left operand of type `long` causes the right operand (`exp`) to be masked by 63 (0x3F). Consequently, when the shift distance is greater than the number of bits in the left operand, the shift distance is interpreted as being `(distance % number_of_bits)`.

### Noncompliant Code Example (Truncation)

This noncompliant code example fails to perform explicit range-checking to avoid truncation of the shift distance:

```public int doOperation(int exp) {
// Compute 2^exp
int temp = 1 << exp;
// Do other processing
return temp;
}
```

### Compliant Solution (Truncation)

This compliant solution range checks the shift distance to avoid unexpected behavior:

```public int doOperation(int exp) throws ArithmeticException {
if ((exp < 0) || (exp >= 32)) {
throw new ArithmeticException("Exponent out of range");
}
// Safely compute 2^exp
int temp = 1 << exp;
// Do other processing
return temp;
}
```

Explicit range-checking for arithmetic operations is detailed in NUM00-J. Detect or prevent integer overflow.

### Noncompliant Code Example (Truncation Zeroing)

This noncompliant code example tries to shift the value `-1` by increasing the value of `i` until, after 32 iterations, the programmer believes the result would become 0. The loop actually never terminates because an attempt to shift a value of type `int` by 32 bits results in the original value (that is, −1) rather than the expected value 0 [Bloch 2005] because only the least significant 5 bits of `i` are considered when the shift occurs, and when `i` reaches the value 32, the 5 least significant bits have the value 0.

```int i = 0;
while ((-1 << i) != 0) {
i++;
}
```

### Compliant Solution (Truncation Zeroing)

This compliant solution does 32 shifts in succession, achieving the value 0 on the 32nd iteration:

```for (int val = -1; val != 0; val <<= 1) { /* ... */ }
```

## Risk Assessment

Incorrect use of shift operators can lead to unanticipated results, causing erratic control flow or unanticipated program behavior.

Rule

Severity

Likelihood

Remediation Cost

Priority

Level

NUM14-J

Low

Probable

Medium

P4

L3

Tool

Version

Checker

Description

PVS-Studio

7.32

V6034

## Related Guidelines

 CERT C Coding Standard INT34-C. Do not shift an expression by a negative number of bits or by greater than or equal to the number ofbits that exist in the operand

## Bibliography

 [Bloch 2005] [FindBugs 2008] ICAST_BAD_SHIFT_AMOUNT Shift Operators [JLS 2015]

## 2 Comments

1. I have a question about the example of `Compliant Solution (Arithmetic vs. Logical)`.

The logical shift operator `>>>` clears vacated bits so that the shift is correct. But the result of ``value >>>= ``1`` is not as expected.

We can do a simple experiment to test it. The code snippet is:

```    public static void main(String[] args) {
long value = -1;
value >>>= 1;
System.out.println(value);
}```

and the result is:

`9223372036854775807`

So the compliant code example seems to be a non-compliant example.

1. No, the compliant solution is good. When a negative number is shifted right by a logical shift, the sign bit becomes a magnitude bit, producing the large positive number you saw. But when a positive number is shifted right, it is divided by a power of 2. So the loop does eventually terminate after 64 iterations (64 being the number of bits in a long.)