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
, anddouble
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 / 2^{s}). 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 along
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) { /* ... */ }
Multiplication and Division
See NUM01-J. Do not perform bitwise and arithmetic operations on the same data.
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 |
Automated Detection
Automatic detection of shift operators is straightforward. Sound determination of whether the usage of those shift operators correctly reflects the intent of the programmer is infeasible in the general case. Heuristic warnings could be useful.
Related Guidelines
Bibliography
2 Comments
Henry Wang
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:
and the result is:
So the compliant code example seems to be a non-compliant example.
David Svoboda
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.)