Interesting shift operations in JAVA

Interesting shift operations in JAVA

<<, >>, <<<, >>> What do these symbols mean? What are the details that are easily missed?

Last time I introduced interesting bit operations in JAVA . I learned that bit operations are directly operating on a reshaped binary bit. The efficiency is much higher than addition, subtraction, multiplication and division, so it is often used in performance-sensitive scenarios.

Today we will introduce the shift operation in binary.

Original code, inverse code, complement

Sharpening the knife and not chopping wood by mistake, can these terms still have an impression?

  • Original code: binary representation, the leftmost bit is the sign bit, 0 means positive number, 1 means negative number
  • Inverse code: the same as the original code when the number is positive; when the number is negative, it is equal to the inversion of each bit of the original code (except for the sign bit)
  • Complement code: the same as the original code when the number is positive, and the complement code +1 when the number is negative

In computer systems, values ​​are always represented and stored in complements. The reason is that by using the complement code, the sign bit and the value field can be processed uniformly; at the same time, addition and subtraction can also be processed uniformly. In addition, the complementary code and the original code are converted mutually, the operation process is the same, and no additional hardware circuit is required.

The same is true in JAVA, storage and shift operations are both complements, the same is true for positive numbers, and attention should be paid to negative numbers.

<< Left shift

In the binary format, move all the numbers to the left by the specified number of bits, the left high bit is shifted out (discarded), and the extra space in the right low bit is filled with 0.

n = n << 1, shift one bit to the left, equivalent to n = n * 2

It should be noted that the highest binary bit of a positive number is 0. If the bit that is pushed up after shifting to the left is 1, the number becomes a negative number.

If it feels strange, think about the scene we have sometimes encountered: a large positive int number, after multiplying a positive number, if the result exceeds the storage limit of the int, it often becomes a negative number, or a very small int A positive number.

Another thing to note is that since Java only stores the complement, the positive complement is the same as the original code. The complement of the negative number will change the original code from 0 to 1, so when the negative number is shifted to the left, the highest value will be shifted out. It is 1, and the one that comes up later is generally 1 (not to the limit), so it is still a negative number.

For programmers, it might be easier to put the content and the code together to make people pay attention...
public class Bit {

    public static void main(String[] args) {
        int n = 6;//..000110 (6)
        System.out.println(n + "Shift 1 bit to the left" + (n << 1));//..001100 (12)
        System.out.println(n + "Shift 2 digits left" + (n << 2));//..011000 (24)
        System.out.println(n + "Shift left by 3 places" + (n << 3));//..110000 (48)

       //Assign value through binary system (jdk7+), start with 0b, followed by binary representation (if the maximum value of int is exceeded, add L to the end to become Long)
       //equivalent to int x = 1073741825
       //01000000000000000000000000000001 The first 0 is a positive number
        int x = 0b01000000000000000000000000000001;
        System.out.println("x = "+ x);

       //10000000000000000000000000000010
       //After shifting to the left, the highest bit becomes 1 and becomes a negative number
        System.out.println("x is shifted 1 bit to the left\t = "+ (x << 1));
       //Just like multiplying by 2, it will become negative if it exceeds the maximum value of int, and the result is the same
        System.out.println("x times 2\t = "+ (x * 2));

       //If you shift to the left by two bits, the highest bit is still a positive number (4)
       //00000000000000000000000000000100
        System.out.println("x left shifted by 2 digits\t = "+ (x << 2));
       //If a positive number exceeds the limit, it may become a negative number, and it is not surprising that a negative number becomes a positive number.
        System.out.println("x times 4\t = "+ (x * 2 * 2));

       //y = -3:
       //Original code: 10000000000000000000000000000011
       //Inverse code: 11111111111111111111111111111100 (except the sign bit, the rest are inverted)
       //Complement code: 11111111111111111111111111111101 (inverse code+1)
       //Java stores the complement, and the shift operation is also the complement operation
       //It also explains why when a negative number is shifted to the left by 1 bit, the result is the same as multiplying by 2 (the highest 1 is gone, and the following is also 1, and the sign is still negative)
        int y = -3;
        System.out.println(y + "Binary representation (complement)" + Integer.toBinaryString(y));

       //After the complement is shifted one bit to the left: 11111111111111111111111111111010
       //Convert to inverse code: 11111111111111111111111111111001 (complement -1)
       //Convert to original code: 10000000000000000000000000000110
       //Decimal: -6
        System.out.println(y + "Shift 1 bit to the left" + (y << 1));
    }

}
/* Output:

6 shift left by 1 bit 12
6 shift left by 2 bits 24
6 shift left by 3 bits 48

x = 1073741825
x left shifted by 1 bit = -2147483646
x times 2 = -2147483646
x left shifted by 2 bits = 4
x times 4 = 4

-3 binary representation (complement) 11111111111111111111111111111111101
-3 Shift 1 bit to the left -6

*/

>> right shift

In the binary format, move all the numbers to the right by the specified number of bits, shift out the low position (discard), and complement the sign bit in the upper space, that is, complement 0 for positive numbers and 1 for negative numbers (think of the complement and original code of negative numbers. different).

n = n >> 1, shift one bit to the right, equivalent to n = n/2 (PS: positive number)

public class Bit {

    public static void main(String[] args) {
        int n = 6;//..110 (6)
        System.out.println(n + "Shift right by 1 bit" + (n >> 1));//..011 (3)
        System.out.println(n + "Shift right by 2 digits" + (n >> 2));//..001 (1)
        System.out.println(n + "Shift right 3 digits" + (n >> 3));//..000 (0)
        System.out.println(n + "Shift right 4 digits" + (n >> 4));//..000 (0)
    }

}
/* Output:

6 shift right by 1 bit 3
6 shift right 2 bits 1
6 shift right 3 bits 0
6 shift right by 4 bits 0

*/

The above is a positive shift to the right, and the situation is a bit different when it is a negative number.

Since the computer stores and shifts are all complements, the positive complement is the same as the original code. It is always shifted to the right and finally becomes 0, just like always dividing by 2 and finally dividing it to 0 no matter how it is divided.

The complement of a negative number has been shifted to the right and finally all are 1, namely:

Complement: 11111111111111111111111111111111
Inverse code: 11111111111111111111111111111110 (complement -1)
Original code: 10000000000000000000000000000001
Decimal: -1
public class Bit {

    public static void main(String[] args) {
        int m = -3;
        System.out.println(m + "\t's complement" + Integer.toBinaryString(m));
        System.out.println(m + "\t's complement shift right by 1 bit" + (m >> 1));
        System.out.println(m + "\t's complement right shift 2 digits" + (m >> 2));
        System.out.println(m + "\t's complement shift right by 3 digits" + (m >> 3));
    }
}

/* Output:

-3 complement 11111111111111111111111111111101
-3 Complement code shifted by 1 bit to the right -2
-3 Complement code shifted right by 2 digits -1
-3's complement is shifted right by 3 digits -1

*/

>>> Unsigned right shift

It still shifts the specified number of bits to the right. The difference from the right shift is that no matter whether it is positive or negative, the high digits are filled with 0. It has no effect on positive numbers. For negative numbers, such a shift will directly become a positive number.

public class Bit {

    public static void main(String[] args) {
        int m = -3;
        System.out.println(m + "\t's complement" + Integer.toBinaryString(m));
        System.out.println(m + "\t's complement unsigned right shift 1 bit" + (m >>> 1));
        System.out.println(m + "\t's complement unsigned right shift by 2 bits" + (m >>> 2));
        System.out.println(m + "\t's complement unsigned right shift 3 bits" + (m >>> 3));
    }
}

/* Output:

-3 complement 11111111111111111111111111111101
-3's complement unsigned right shift 1 bit 2147483646
-3's complement unsigned right shift by 2 bits 1073741823
-3's complement unsigned right shift 3 bits 536870911

*/

<<< Unsigned shift left

Digit limit

An easily overlooked place, each move one bit loops N times, and one move N bits at a time, the result is not necessarily the same.

Taking int as an example, if you directly shift 36 bits to the left, the result is not 0, but is equivalent to 36% 32=4 bits left.

The same applies to shift right and unsigned shift right.

public class Bit {

    public static void main(String[] args) {
        int m = 3;
        int t = m;
        for (int i = 1; i <= 36; i++) {
            t = t << 1;
        }
        System.out.println(t);
        System.out.println(m << 36);
        System.out.println(m << (36% 32));
    }
}
/* Output:

0
48
48

*/

summary

  1. Move wherever the arrow is
  2. Left shift operation is equivalent to multiplying by 2, right shifting is equivalent to dividing by 2, not all
  3. The left shift operation may change the sign, because the sign bit will be removed, and the new sign bit may not be the same as before
  4. The right shift operation does not change the sign, because the sign bit is filled on the left
  5. Unsigned right shift will turn negative numbers into positive numbers
  6. No unsigned shift left
  7. After the displacement exceeds the number of digits of the basic JAVA type, it is equivalent to the number of digits after the displacement modulus