# What are left shift <<, right shift >> and Unsigned right shift >>> operator in Java? How are these useful?

Integer in Java is of signed type 4 bytes (All Negative numbers are represented in 2’s complementary notation in Java),

Java provides both signed and unsigned bit shift operators to support signed and unsigned shift of bits.

Also, X = a << b means the same as X = a*2^b

For Positive Numbers,

For example,

However, as the logical right-shift inserts value 0 bits into the most significant bit, instead of copying the sign bit, it is ideal for unsigned binary numbers, while the arithmetic right-shift is ideal for signed two’s complement binary numbers.

For arithmetic left shift, since filling the right-most vacant bits with 0s will not affect the sign of the number, the vacant bits will always be filled with 0s, and the sign bit is not considered. Thus, it behaves in a way identical to the logical (unsigned) left shift. So there is no need for separate unsigned left sift operator.

Bloom Filter, Fast mathematical calculations, hashing functions of HashMap are some of applications.

Java 8 source code reveals that HashMap uses unsigned rightshift operator to calculate hash for a given key. This hash is used to identify the right bucket for given Key.

See original article at

http://javainterviews.scribbleit.in/core-java/java-bitwise-right-and-left-shift-unsigned-right-shift-operator/p/BPkWMg

Java provides both signed and unsigned bit shift operators to support signed and unsigned shift of bits.

### Left Shift Operator << (Signed)

It shifts the underlying bits of an integer to left by the given distance filling the right most bits with zero always, irrespective of the sign of the number.Also, X = a << b means the same as X = a*2^b

The same thing happens for negative numbers which are represented in 2’s complementary notation, for example

`23 << 1 becomes 46`

`00010111 << 1 becomes 00101110`

`-5 << 3 becomes -40`

`11111011 << 3 becomes 11011000`

A left arithmetic shift by n is equivalent to multiplying by 2

^{n}(provided the value does not overflow)### Right Shift Operator >> (Signed)

Right Shift Operator shifts the bits to right by specified amount maintaining the sign of underlying integer. It fills the left most bits with 0 if the number is positive otherwise with bit 1For Positive Numbers,

For Negative Numbers,

`92 >> 2 becomes 23`

`01011100 >> 2 becomes 00010111`

`-92 >> 2 becomes -23`

`10100100 >> 2 becomes 11101001`

A right arithmetic shift by n of a two’s complement value is equivalent to dividing by 2

^{n}and rounding toward negative infinity### Unsigned right shift Operator >>> (does not preserve the sign of Number i.e. does not preserve the 1st bit)

Unsigned right shift operator >>> is effectively same as >> except that it is unsigned, it fills the left most positions with bit 0 always. (Irrespective the sign of the underlying number)For example,

`11001100 >>> 1 becomes 01100110 (shown in diagram)`

`10000000 >>> 3 becomes 00010000 in binary`

`256 >>> 3 becomes 256 / 2^3 = 16.`

Unsigned right shift by n of a two’s complement value is equivalent to dividing by 2

^{n}and rounding toward zero#### Arithmetic shift

n an arithmetic shift, the bits that are shifted out of either end are discarded. In a left arithmetic shift, zeros are shifted in on the right; in a right arithmetic shift, the sign bit (the MSB in two’s complement) is shifted in on the left, thus preserving the sign of the operand.#### Logical shift

In a logical shift, zeros are shifted in to replace the discarded bits. Therefore the logical and arithmetic left-shifts are exactly the same.However, as the logical right-shift inserts value 0 bits into the most significant bit, instead of copying the sign bit, it is ideal for unsigned binary numbers, while the arithmetic right-shift is ideal for signed two’s complement binary numbers.

**Why there is no unsigned left shift operator in Java?**For arithmetic left shift, since filling the right-most vacant bits with 0s will not affect the sign of the number, the vacant bits will always be filled with 0s, and the sign bit is not considered. Thus, it behaves in a way identical to the logical (unsigned) left shift. So there is no need for separate unsigned left sift operator.

#### What is need of bitwise shifts in Java?

Uses of bitwise operators: bitwise operators are used for few very efficient mathematical calculations in Big O(1).Bloom Filter, Fast mathematical calculations, hashing functions of HashMap are some of applications.

For example, on a typical machine, bitwise shift operator takes 10 ns,
while modulus operator (10%2) takes 100 ns (nano seconds). Thus it makes
more sense to use bitwise operators in time critical operations like
hashmap’s get operation to figure out the correct bucket rather than
using modulus operator.

**Java 8 HashMap’s hash method definition**Java 8 source code reveals that HashMap uses unsigned rightshift operator to calculate hash for a given key. This hash is used to identify the right bucket for given Key.

Please note that modulus operator could have been used by the above logic to identify the appropriate bucket for a given key, but performance would have suffered in that case.

`static final int hash(Object key) {`

`int h;`

`return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);`

`}`

`//Then below code is used to figure out appropriate bucket from table of buckets`

`Node first = tab[(n - 1) & hash]`

See original article at

http://javainterviews.scribbleit.in/core-java/java-bitwise-right-and-left-shift-unsigned-right-shift-operator/p/BPkWMg

## No comments:

## Post a Comment

Your comment will be published after review from moderator