Bit shift operators in Java

Above and beyond bitwise operators, JLS provides 3 bit shift operators for bit manipulation in Java.
Namely:

Left Shift Operator (<<)
Signed Right Shift Operator (>>)
Unsigned Right Shift Operator (>>>)

Syntax: Left-hand operand SHIFT OPERATOR Right-hand operand
Here,
Left-hand Operand $\rightarrow$ is the value to be shifted, i.e., shifting of it's binary value.
Right-hand Operand $\rightarrow$ specifies the shift distance.

i.e., Value to be shifted SHIFT OPERATOR the shift distance.

1. Left Shift Operator "<<":

It shifts the binary value of the left operand with sign to left side and fills the empty place with 0.

Let's solve some question to understand the concept fo Left shift operator:

Q.1 Solve 20 << 2 $\rightarrow$ shift 20 by 2 bits in the left.

Sol. The binary representation of 20 is: 00010100

Fig. 1.1 - Logic behind left shift operation 20 << 2

Therefore, 20 << 2 = 80. So, Answer = 80.

Note: If you closely observe:
System.out.println(10<<2); // output = $10*2^{2}$ = 40
System.out.println(10<<3); // output = $10*2^{3}$ = 80
System.out.println(10<<4); // output = $10*2^{4}$ = 160

$\therefore$ Left Shift Operator also act's as $LeftOperand*2^{Right Operand}$ . But, remember the default size of the data type.

Q. 2. what's the result of -20 << 2 ?

Sol. Negative integers are stored as it two's complement in Java.

Revision: Two's complement
Two's complement of a negative integer can be found by Inverting and adding '1' to the binary representation of the integer with -ve sign.

i.e., to reverse the sign you simply invert the bits (0 $\rightarrow$ 1, and 1 $\rightarrow$ 0) and add '1' to the resulting number.


Fig. 1.2 - Basic rules of Binary addition

Even subtraction (A - B) is considered as (A + (-B)) i.e., addition of a binary value 'A' with the two's complement of another binary value 'B'.

Fig. 1.3 - Basic Addition in Binary

Fig. 1.4 - Basic Subtraction in Binary

Suppose, we're working with 8-bit binary values (for simple calculation) and we want to find how -20 would be expressed in two's complement notation.

Step 1: Write the integer value (here 20) in it's binary form:

Fig. 1.5 : Representation of 20 in it's binary form i.e., $(20)_{10}$ = $(0 0 0 1 0 1 0 0)_{2}$

i.e., $(20)_{10}$ = $(0 0 0 1 0 1 0 0)_{2}$

Step 2: Then we invert the digits. 0 becomes 1, and 1 becomes 0:

1 1 1 0 1 0 1 1

Step 3: Then we add '1':

So, we represent $(-20)_{10}$ as $(1 1 1 0 1 1 0 0)_{2}$ . So, Answer = 11101100.

That is how one would write -20 in 8-bit binary.

Note: MSB tells us whether the binary representation is of a -ve or +ve Integer.

if MSB = 0 $\rightarrow$ it represents a +ve integer, and
if MSB = 1 $\rightarrow$ it represents a -ve integer.

Conversion from Two's Complement

Let's understand this with the help of above example. Let's convert the two's complement $(11101100)_{2}$ back to it's original form.

Step 1: Here, MSB = 1. So, we can conclude that it is a binary representation of a -ve integer.

Rule #1: to reverse the sign you simply invert the bits (0 goes to 1, and 1 to 0) and add one to the resulting number.

Step 2: Invert the digits. 0 becomes 1, and 1 becomes 0:

0 0 0 1 0 0 1 1

Step 3: Add '1':

So, from results found by step 1 and step 3. We found that $(11101100)_{2}$ = $(-20)_{10}$ Answer = -20.

So, let's convert -20 to it's binary equivalent:

Now, let's shift it to left with shift distance = 2, as mentioned in Q.2.

Since, the given integer was represented in 8 bits, we will only consider 8 bits for now. So, we got 1 0 1 1 0 0 0 0

since MSB = 1. It implies, this binary value is a representation of a -ve integer.

After inverting the digits $\rightarrow$ 0 1 0 0 1 1 1 1

After adding 1 $\rightarrow$ 0 1 0 1 0 0 0 0

$\rightarrow$ 128*0+ 64*1 + 32*0 + 16*1 + 8*0 + 4*0 + 2*0 + 1*0 = 64 + 16 = 80

So, since we found that it's a -ve integer => Answer = -80.

Q. 3. what's the result of 20 << -2 ?

Sol. Here the shift distance is "-2". So, this expression is considered undefined in C. But, in Java using Netbeans, we got an output for this expression. And Let's find it out how:

2 is represented in binary form as => 00000010

Inverting it => 11111101

After adding '1' => 11111110

So, -2 is represented as 11111110 in binary form.

Note: According to JSL:

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator with the mask value 0x1f (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.
If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator with the mask value 0x3f (0b111111). The shift distance actually used is therefore always in the range 0 to 63, inclusive.

So, the last 5 bits of 11111110 is 11110

After bitwise AND operation we get 11110. In integer form it's represented as 30.

$\therefore$ Shift distance = 30.
$\Rightarrow$ If we will shift $(0 0 0 1 0 1 0 0)_{2}$ , 30 times to left. We will get 32 0's. As 20 is a positive integer. And the size of int in java is 32 bit. $\therefore$ Answer = 0.

Q. 4. what's the result of `-20 << -2` ?

Sol. Two's complement of -20 = $(11101100)_{2}$ .
Two's complement of -2 = $(11111110)_{2}$ .
After subjecting the last 5 bits of 11111110 to bitwise AND operation with the mask 0b11111 $\Rightarrow$ we get 11110 $\Rightarrow$ it is the binary representation of 30.
$\therefore$ shift distance = 30.
$\Rightarrow$ If we will shift $(11101100)_{2}$ , 30 times to left. We will get 32 0's. As -20 is an integer. And the size of int in java is 32 bit. $\therefore$ Answer = 0.

TEST CODE FOR ANALYSING LEFT SHIFT OPERATOR

public class ShiftOpptn {

    public static void main(String[] args) {
         /* Left shift operator */
        System.out.println(20 << 2);   // output = 80
        System.out.println(Integer.toBinaryString(20 << 2));   // 1010000
        System.out.println(-20 << 2); // -80
        System.out.println(Integer.toBinaryString(-20 << 2));
        // output =11111111111111111111111110110000
        System.out.println(20 << -2); // 0
        System.out.println(Integer.toBinaryString(20 << -2));   // 0
        System.out.println(-20 << -2); // 0
        System.out.println(Integer.toBinaryString(-20 << -2)); // 0
    }
}

Output:

Fig. 1.5 - Output produced for above code in Netbeans IDE

2. Signed Right shift operator ">>"

It shifts the binary value of the left operand with sign to RIGHT side and fills the empty place with the value of SIGN BIT.

For +ve (positive) number it fills with 0. And,
for -ve (negative) number it fills with 1.

Example: 20 >> 2

Fig. 2.1 - Logic behind signed right shift operation 20 >> 2

Therefore, 20 >> 2 = 5 . And it is a +ve integer. So, rest of the empty space will be filled with the sign value i.e., 0.

$\Rightarrow$ 5 will be represented as 00000000 00000000 00000000 00000101 in binary.

Q.1. What's the result of -20 >> 2 ?

Sol. Two's complement of -20 = $(11101100)_{2}$ .
Since, the LHS operand is a -ve integer. The blank space will be filled by the -ve sign value '1'.

So, after shifting 2 bits right $\Rightarrow$ 11111011 $\Rightarrow$ two's complement of -5.

$\therefore$ -20 >> 2 = -5, which is represented as 11111111 11111111 11111111 11111011 in binary.

Q.2. What's the result of 20 >> -2 ?

Sol. Binary form of 20 = $(0 0 0 1 0 1 0 0)_{2}$
Two's complement of -2 = $(11111110)_{2}$ .
Since, the LHS operand is a +ve integer. The blank space will be filled by the +ve sign value i.e., '0'.

So, by JLS's specified rule for shift operator. least 5 digits of the RHS operand is passed through bitwise AND operation with the MASK value 0b11111.

So, 11110 AND 0b11111 = 11110 , which is the binary representation of 30.

$\therefore$ After shifting the binary of LHS operand to 30 bits right $\Rightarrow$ 00000000 $\Rightarrow$ 0.

$\therefore$ 20 >> -2 = 0, which is represented as 00000000 00000000 00000000 00000000 in binary.

Q.3. What's the result of -20 >> -2 ?

Sol. Two's complement of -20 = $(11101100)_{2}$
Two's complement of -2 = $(11111110)_{2}$ .
Since, the LHS operand is a -ve integer. The blank space will be filled by the -ve sign value i.e., '1'.

So, by JLS's specified rule for shift operator. least 5 digits of the RHS operand is passed through bitwise AND operation with the MASK value 0b11111.

So, 11110 AND 0b11111 = 11110 , which is the binary representation of 30.

$\therefore$ After shifting the binary of LHS operand to 30 bits right $\Rightarrow$ 11111111 $\Rightarrow$ Two's complement of -1.

$\therefore$ -20 >> -2 = -1, which is represented as 11111111 11111111 11111111 11111111 in binary.

Note: If you closely observe:
System.out.println(10<<2); // output = $\frac{10}{2^{2}} = \frac{10}{4}= 2$ => 2
System.out.println(10<<3); // output = $\frac{10}{2^3} = \frac{10}{8} = 1$ => 1
System.out.println(10<<4); // output = $\frac{10}{2^4} = \frac{10}{16} = 0$ => 0

$\therefore$ Right Shift Operator also act's as $\frac{LeftOperand}{2^{Right Operand}}$ . But, remember the default size of the data type.

TEST CODE FOR ANALYSING RIGHT SHIFT OPERATOR

public class ShiftOpptn {

    public static void main(String[] args) {
         /* Signed Right shift operator */
        System.out.println("1. 20 in binary = "+Integer.toBinaryString(20));
        System.out.println("2. 20 >> 2 = "+ (20 >> 2));
        System.out.println("Binary = "+ Integer.toBinaryString(20 >> 2));
        System.out.println("3. -20 >> 2 = "+ (-20 >> 2));
        System.out.println("Binary = "+ Integer.toBinaryString(-20 >> 2));
        System.out.println("4. 20 >> -2 = "+ (20 >> -2));
        System.out.println("Binary = "+ Integer.toBinaryString(20 >> -2));
        System.out.println("5. -20 >> -2 = "+ (-20 >> -2));
        System.out.println("Binary = "+ Integer.toBinaryString(-20 >> -2));
    }
}

Output:

Fig 2.2 Output produced for above code in Netbeans IDE

3. Unsigned right shift operator ">>>"

It shifts the binary value of the left operand without preserving SIGN to RIGHT side and fills the empty place with 0.

So, It is also known as unsigned right shift operator, and right shift with zero fill.

Q.1. What's the result of 20 >> 2 ?

Sol. Two's complement of 20 = $(0 0 0 1 0 1 0 0)_{2}$ .
>>> is an unsigned right shift operator. So, the blank space will be filled by '0'.

$\therefore$ after shifting 2 bits right $\Rightarrow$ (00000000 00000000 00000000 00000101)₂ = (5)_10.

$\therefore$ 20 >> 2 = 5, which is represented as 00000000 00000000 00000000 00000101 in binary.

Q.2. What's the result of -20 >> 2 ?

Sol. Two's complement of -20 = $(11101100)_{2}$ .
>>> is an unsigned right shift operator. So, the blank space will be filled by '0'.

$\therefore$ after shifting 2 bits right $\Rightarrow$ (00111111111111111111111111111011)₂ = (1073741819)_10.

$\therefore$ -20 >> 2 = 1073741819, which is represented as 00111111 11111111 11111111 11111011 in binary.

Q.3. What's the result of 20 >> -2 ?

Sol. Binary form of 20 = $(0 0 0 1 0 1 0 0)_{2}$
Two's complement of -2 = $(11111110)_{2}$ .
>>> is an unsigned right shift operator. So, the blank space will be filled by '0'.

So, by JLS's specified rule for shift operator. least 5 digits of the RHS operand is passed through bitwise AND operation with the MASK value 0b11111.

So, 11110 AND 0b11111 = 11110 , which is the binary representation of 30.

$\therefore$ After shifting the binary of LHS operand to 30 bits right $\Rightarrow$ 00000000 $\Rightarrow$ 0.

$\therefore$ 20 >> -2 = 0, which is represented as 00000000 00000000 00000000 00000000 in binary.

Q.4. What's the result of -20 >> -2 ?

Sol. Two's complement of -20 = $(11101100)_{2}$
Two's complement of -2 = $(11111110)_{2}$ .
>>> is an unsigned right shift operator. So, the blank space will be filled by '0'.

So, by JLS's specified rule for shift operator. least 5 digits of the RHS operand is passed through bitwise AND operation with the MASK value 0b11111.

So, 11110 AND 0b11111 = 11110 , which is the binary representation of 30.

$\therefore$ After shifting the binary of LHS operand to 30 bits right $\Rightarrow$ (00000000000000000000000000000011)₂ = (3)₁₀

$\therefore$ -20 >> -2 = 3, which is represented as 00000000 00000000 00000000 00000011 in binary.

TEST CODE FOR ANALYSING UNSIGNED RIGHT SHIFT OPERATOR

public class ShiftOpptn {

    public static void main(String[] args) {
         /* Unsigned Right shift operator ">>>" */
        System.out.println("1. 20 in binary = "+Integer.toBinaryString(20));
        System.out.println("2. 20 >>> 2 = "+ (20 >>> 2));
        System.out.println("Binary = "+ Integer.toBinaryString(20 >>> 2));
        System.out.println("3. -20 >>> 2 = "+ (-20 >>> 2));
        System.out.println("Binary = "+ Integer.toBinaryString(-20 >>> 2));
        System.out.println("4. 20 >>> -2 = "+ (20 >>> -2));
        System.out.println("Binary = "+ Integer.toBinaryString(20 >>> -2));
        System.out.println("5. -20 >>> -2 = "+ (-20 >>> -2));
        System.out.println("Binary = "+ Integer.toBinaryString(-20 >>> -2));
    }
}

Output:

Fig 3.1 The output produced by above code in Netbeans IDE

More on bit-shift operators

The shift operators are left-associative.

Did you know?ln programming language, associativity^[1] (a.k.a fixity) of an operatorproperty that determines how operators of the same precedence are grouped in the absence of parentheses.

If there are two operators with same precedence before and after an operand then the choice of which operations to apply the operand to, is determined by the "associativity" of the operators.

Operators may be associative (meaning the operations can be grouped arbitrarily), left-associative (meaning the operations are grouped from the left), right-associative (meaning the operations are grouped from the right) or non-associative (meaning operations cannot be chained, often because the output type is incompatible with the input types).

different programming languages may have different associativity and precedence for the same type of operator.

Consider the expression a ~ b ~ c. If the operator ~ has left associativity, this expression would be interpreted as (a ~ b) ~ c. If the operator has right associativity, the expression would be interpreted as a ~ (b ~ c). If the operator is non-associative, the expression might be a syntax error, or it might have some special meaning.

Some mathematical operators have inherent associativity. For example, subtraction and division, as used in conventional math notation, are inherently left-associative. Addition and multiplication, by contrast, are both left and right associative. (e.g. (a * b) * c = a * (b * c)).

The concept of notational associativity described here is related to, but different from the mathematical associativity. An operation that is mathematically associative, by definition requires no notational associativity. (For example, addition has the associative property, therefore it does not have to be either left associative or right associative.) An operation that is not mathematically associative, however, must be notationally left-, right-, or non-associative. (For example, subtraction does not have the associative property, therefore it must have notational associativity)[...]

After Unary numeric promotion, if the type of each of the operands of a shift operator is not a primitive integral type, then that will cause a compile time error.

FYI : Variables and Data types in Java
Variable:- is any name used to refer a memory location.
Data type:- represents the values that can be stored in the variable.

There are 3 types of variable in Java:
1. Local $\rightarrow$ ( variable declared inside the method ).
2. Instance $\rightarrow$ ( variable declared inside the class but outside the method ).
3. Static $\rightarrow$ ( Non-local variable that is declared as static ).

There are 2 types of compile-time data types in Java:
1. Primitive, and
2. Non-primitive.

Fig.3.1 - Data types in Java

Therefore, by primitive integral type we mean:-
(a.) Integer : byte, short, int, long. And
(b.) Floating-point : float, double.

In Java,
Data Type Default size    Default value
boolean    $\rightarrow$    1 bit              $\rightarrow$    false
byte    $\rightarrow$    1 byte            $\rightarrow$    0
char $\rightarrow$    2 byte          $\rightarrow$     '\u0000'
short    $\rightarrow$    2 byte            $\rightarrow$     0
int            $\rightarrow$    4 byte            $\rightarrow$     0
long          $\rightarrow$    8 byte          $\rightarrow$     0L
float          $\rightarrow$    4 byte            $\rightarrow$     0.0f
double      $\rightarrow$    8 byte             $\rightarrow$     0.0d

Java follows UNICODE system instead of ASCII code system. Well,
Lowest value: '\u0000'
Highest value: '\uFFFF'.
So, char in Java takes 2 byte.

UNICODE = Universal Interntionl Standard Character Encoding.

Different country were following different code system. So, to make it common for all, UNICODE System was developed.

FYI : Numeric promotions
Numeric promotions: - are used to convert the operands of a numeric operator to a common type so that the operation can be performed.

There are two kinds of numeric promotion:
1. Unary numeric promotion. And,
2. Binary numeric promotion.

1. Unary numeric promotion: - During an operation, some operators apply unary numeric promotion on the single operand which is to produce a numeric type value.

The operand of compile-time type byte, short, char, or int is subjected to $\rightarrow$ unboxing conversion, and it is then promoted to a value of type int by $\rightarrow$ a widening primitive conversion or an identity conversion.
Else, if the operand is of compile-time type long, float, or double, it is subjected to unboxing conversion.
Else, it remains as it is, without converting.

Unary numeric promotion is performed on expressions in the following situations:

Each dimension expression in an array creation expression. Ex: inte ar[] = new int[2];
The index expression in an array access expression. Ex: ar['\u0001'] = 1;
The operand of a unary +, -, ~ complimentary, or <<, >>, >>> shift operators. Ex: ar[0] = -'\u0001';

Note: A long shift distance (RHS operand of the SHIFT OPERATOR <<, >> or >>>) doesn't promote the value being shifted ( LHS operand of the shift operator) to long.

Example:

 byte a = 17;   // 1. assigning byte value

byte b = +a; // 2. Compiler error

2nd statement creates compile error because of the following rule mentioned by JLS: "if the operand is of compile-time type byte, short or char $\rightarrow$ unary numeric promotion promotes it to a value of type int by a widening conversion."

Fig. 3.2 - Example to illustrate compiler error produced during unary numeric promotion

To remove the error, we can explicitely caste it to byte $\rightarrow$ byte c = (byte) +a;

2. Binary numeric promotion: When an operator applies binary numeric promotion to a pair of operands, the following rules apply (in order):

Reference type operand is subjected to unboxing conversion.
Widening primitive conversion is applied to convert either or both operands as specified by the following rules:
- If either operand is of type double, the other is converted to double.
- Otherwise, if either operand is of type float, the other is converted to float.
- Otherwise, if either operand is of type long, the other is converted to long.
- Otherwise, both operands are converted to type int.

It implies, during this operation the priority of data type in descending order is $\rightarrow$ double, float, long, int.

After the conversion(s), if any, value set conversion is then applied to each operand.

Binary numeric promotion is performed on the operands of certain operators:

*, /, and % (multiplicative operator)
+ and - (additive operator)
<, <=, >, and >= (comparison operator)
== and != (equality operator)
&, ^, and | (integer bitwise operator)
? : (conditional operator)

Fig. 3.3 - Example to illustrate the compile error caused on breaking the rules of binary numeric promotion

Capsule Notes

The shift operators include left shift <<, signed right shift >>, and unsigned right shift >>>.

The value of n<<s is n left-shifted s bit positions with zero-extension.
The value of n>>s is n right-shifted s bit positions with sign-extension.
The value of n>>>s is n right-shifted s bit positions with zero-extension.

Negative integers are stores as it's two's complement in Java.

Note: According to JSL:

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance after getting subjected to a bitwise logical AND operator with the mask value 0x1f (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.

If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator with the mask value 0x3f (0b111111). The shift distance actually used is therefore always in the range 0 to 63, inclusive.

The shift operators are left-associative.

After Unary numeric promotion, if the type of each of the operands of a shift operator is not a primitive integral type, then that will cause a compile time error.

Interview Questions:

Q. 1. Why is there no <<< operator in Java 8?
Ans. To avoid redundancy. In java the sign values are stored in MSB. In left shift operation, the right side bit gets empty. So, in left shift operation there is no point in talking about signed and unsigned variable. The available left shift operator does the work.

FYI, there is no unsigned right shift operator ">>>" in C, but it's there is Java. So, we can say that it's a java specific operator.

p.s. this post content is concisely based on the data provided by the JLS ( Java Language Specification) on Java 8 release.

* ( Most of the questions have already been answered in the explanation. Yet if you find any question left unanswere. Please comment it below... )

Bibliography:

^[1]This article uses material from the Wikipedia article Operator associativity, which is released under the Creative Commons Attribution-Share-Alike License 3.0 (view authors).

Friday 9 June 2017

Bit shift operators in Java

Q. 4. what's the result of `-20 << -2` ?

1 comment

Category

Popular Posts

Archive

Friday 9 June 2017

Bit shift operators in Java

Q. 4. what's the result of -20 << -2 ?

1 comment

Category

Popular Posts

Archive

Q. 4. what's the result of `-20 << -2` ?