23 << 1 becomes 46
What is left shift right shift and unsigned rght shift operator in Java
Upasana | December 04, 2019 | 3 min read | 472 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
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:
- What is AtomicInteger class and how it works internally
- What is difference between sleep() and wait() method in Java?
- What is difference between Vector and ArrayList, which one shall be preferred
- What is volatile keyword in Java
- Discuss internals of a ConcurrentHashmap (CHM) in Java
- Java 8 Parallel Stream custom ThreadPool
- What is purpose of Collections.unmodifiableCollection
Recommended books for interview preparation:
Book you may be interested in..
Book you may be interested in..
