What is left shift right shift and unsigned rght shift operator in Java

Carvia Tech | December 04, 2019 | 3 min read | 0 views


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.

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

23 << 1 becomes 46
00010111 << 1 becomes 00101110

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

-5 << 3 becomes -40
11111011 << 3 becomes 11011000

A left arithmetic shift by n is equivalent to multiplying by 2n (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 1

For Positive Numbers,

92 >> 2 becomes 23
01011100 >> 2 becomes 00010111

For Negative Numbers,

-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 2n 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 2n and rounding toward zero

Concepts

Arithmetic shift

In 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.

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]

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.


Top articles in this category:
  1. How to configure custom ThreadPool for Java 8 Stream API parallel operations
  2. What is Deadlock in Java? How to troubleshoot and how to avoid deadlock
  3. What do you understand by Java Memory Model?
  4. Discuss internals of a ConcurrentHashmap (CHM) in Java
  5. What is volatile keyword in Java
  6. How will you increment each element of an Integer array, using parallel operation
  7. What is difference between sleep() and wait() method in Java?


Find more on this topic:
Core Java image
Core Java

Core Java - OOP Concepts, Garbage Collection, Multi-threading, Collections Framework, Java 8 Features, Lambda Functions, Streams.

Last updated 1 week ago


Recommended books for interview preparation:

This website uses cookies to ensure you get the best experience on our website. more info