In the process of looking at the source code of various frameworks at ordinary times, often see some displacement operations, so as a Java developer is certain to master displacement operations.

In addition, I have sorted out the interview questions for 20 years, including spring, concurrency, database, Redis, distributed, Dubbo, JVM, microservices and other aspects of the summary, as well as the summary of the interview questions, if necessary, click the link to collect yourself:Tencent document

Positive displacement operation

There are three shift operations in Java:

• << : left move • >> : right move • >>> : Unsigned right move

Let’s go straight to the Demo:

System.out.println(2 << 1);     / / 4
System.out.println(2 >> 1);     / / 1
System.out.println(2 >>> 1);    / / 1
System.out.println(-2 << 1);    / / - 4
System.out.println(-2 >> 1);    // -1
System.out.println(-2 >>> 1);   / / 2147483647
Copy the code

At first glance, the printout of the Demo above should be confusing, but let me explain how it works. In the above Demo, we have “2” and “-2”, which are two decimal numbers and are of type int (four bytes in Java). The bit operation is based on binary bit, so we need to convert decimal to binary before performing the operation:

  • 2 < < 1: The decimal “2” is converted to the binary “00000000 00000000 00000000 00000010”, then the binary is moved one bit to the left, the high part is discarded, and the low part is filled with 0, so the result is “00000000 00000000 00000000 00000100”. In decimal, it’s four.
  • 2 > > 1: The decimal “2” is converted to the binary “00000000 00000000 00000000 00000010”, then the binary is moved one bit to the right, the lower part is discarded, and the higher part is filled with zeros, so the result is “00000000 00000000 00000000 00000001”. In decimal, it’s one.

It’s easy to understand in both cases, but what is unsigned right shift, and how do negative numbers work? Let’s take a look at -2 << 1 and -2 >> 1. The left shift and right shift operations of these two negative numbers are actually similar to positive numbers, in that they are converted from decimal numbers to binary numbers first and then moved from binary numbers. Therefore, the key now is how to represent negative numbers in binary numbers.

Source code, inverse code, complement code

Next we’ll focus on the different ways in which decimal numbers can be represented in binary, so for brevity we’ll use one byte, eight bits, to represent binary numbers.

The original code

The decimal system The original code
2 0000, 0010,
2 – 1000, 0010,

The source code is actually the easiest to understand, but you need to use the first bit in binary to represent the symbol bit, 0 represents a positive number, 1 represents a negative number, so you can see that a number in binary source code, the value range is -111 1111 ~ +111 1111, in decimal is -127 ~ 127.

Radix-minus-one complement

In mathematics, we have the addition, subtraction, multiplication, and division for computer best only addition, such opportunity of calculation is more simple and efficient, 5-3 = 2 we know that in mathematics, in fact, can be converted into 5 + (3) = 2, which means subtraction can be expressed in addition, the multiplication is addition, the accumulation of division is the accumulation of subtraction, so as long as there is an addition in the computer is enough.

A number represented in source code is easy to understand, but a separate bit is required to represent the sign bit. And in addition, the computer needs to identify a binary source code is positive or negative, after identifying the corresponding operation. This efficiency is not high, can let the computer in the operation without the sign bit, that is to say, let the sign bit also participate in the operation, which is to use inverse code.

The decimal system The original code Radix-minus-one complement
2 0000, 0010, 0000, 0010,
2 – 1000, 0010, 1111, 1101,

The inverse of a positive number is the same as the original code, while the inverse of a negative number is based on the original code and the sign bits remain unchanged, and the other bits are reversed. So let’s see what happens when we use inverse directly. Let’s take 5 minus 3. 5 minus 3 is 5 plus minus 3.

The decimal system The original code Radix-minus-one complement
5 0000, 0101, 0000, 0101,
– 3 1000, 0011, 1111, 1100, 
5-3
= 5+ (-3)
= 0000 0101(inverse) +1111 1100(inverse) =0000 0001(inverse) =0000 0001(Source code) =1
Copy the code

Isn’t that right? !!!!! 5-3 = 1? Why is it 1? Let’s look at a special operation:

1-1
= 1+ (-1)
= 0000 0001(inverse) +1111 1110(inverse) =1111 1111(inverse) =1000 0000(Source code) = -0
Copy the code

Let’s look at a special operation:

0+0
= 0000 0000(inverse) +0000 0000(inverse) =0000 0000(inverse) =0000 0000(Source code) =0
Copy the code

We can see that 1000 0000 represents -0, 0000 0000 represents 0. Although -0 and 0 are the same, they are different when expressed in source code and inverse code. We can understand that when a byte is used to represent the value range of numbers, there is an extra -0 in these numbers. Therefore, when we use inverse code to operate directly, the sign bit can directly participate in the operation, but the result will be wrong.

complement

In order to solve the problem of inverse code, the complement code appeared.

The decimal system The original code Radix-minus-one complement complement
2 0000, 0010, 0000, 0010, 0000, 0010,
2 – 1000, 0010, 1111, 1101, 1111, 1110,

The complement of a positive number is the same as the original and inverse, and the complement of a negative number is the inverse +1.

The decimal system The original code Radix-minus-one complement complement
5 0000, 0101, 0000, 0101, 0000, 0101,
– 3 1000, 0011, 1111, 1100, 1111, 1101, 
5-3
= 5+ (-3)
= 0000 0101(Complement) +1111 1101(Complement) =0000 0010(Complement) =0000 0010(Source code) =2
Copy the code

5-3 = 2!!!!! Correct. And in particular:

1-1
= 1+ (-1)
= 0000 0001(Complement) +1111 1111(Complement) =0000 0000(Complement) =0000 0000(Source code) =0
Copy the code

1-1 = 0!!!!! Correct and let’s do a special operation:

0+0
= 0000 0000(Complement) +0000 0000(Complement) =0000 0000(Complement) =0000 0000(Source code) =0
Copy the code

0 + 0 = 0!!!!! Also correct. So, we can see that the complement solves the inverse problem. So for numbers, we can use the form of complement for binary representation.

Negative displacement operation

Let’s look at minus 2 << 1 and minus 2 >> 1. -2 is represented by the original code 10000000 00000000 00000000 00000010. -2 is represented by the inverse code 11111111 11111111 11111111 1111101. -2 is represented by the complement code 11111111 11111111 11111111 111110-2 << 1, indicating that the complement of -2 is moved one bit to the left and becomes 11111111 11111111 111111 11111100. The corresponding inverse code of the complement is

11111111 11111111 11111111 11111100
- 1
= 11111111 11111111 11111111 11111011
Copy the code

The source code of this inverse code is: the symbol bit remains unchanged, and the other bits are reversed, 10000000 00000000 00000000 00000100, indicating -4. So minus 2 << 1 = minus 4. So minus 2 >> 1 is the same thing, so I’m not going to do it here.

Unsigned shift to the right

In the above left and right shifts, I did not mention that the sign bit is fixed when the complement is moved, while the unsigned right shift means that the sign bit will also move when the complement is moved. Like -2 >>> 1. -2 is represented by the original code 10000000 00000000 00000000 00000010. -2 is represented by the inverse code 11111111 11111111 11111111 1111101. -2 is represented by the complement code 11111111 11111111 11111111 11111110-2 when the complement code moves to the right 1 bit is: 01111111 11111111 11111111 11111111 11111111 01111111 11111111 11111111 11111111 11111111 (because the sign bit is 0, which represents a positive number, the positive number has the same primitive, inverse, and complement codes), the corresponding decimal number is 2147483647. So minus 2 >>> 1 is 2147483647

conclusion

The article may be quite messy, I hope you can understand, can harvest. Here to sum up, we can find: 2 << 1 = 4 = 2* 2 2 << 2 = 8 = 2* 2* 2 2 << n = 2* 2n m << n = M * 2n right shift is the opposite, so we later in the source code to see the bit operation, you can refer to the above formula.