• 1. The question
  • 2. Get down to business
    • 2.1. Binary, source, inverse and complement
      • 2.1.1. The original code
      • 2.1.2. Radix-minus-one complement
      • 2.1.3. Complement
    • 2.2. Integer in Java
  • 3. Summary
  • 4. The last

1. The question

When checking Leetcode recently, I encountered this problem:

Given a 32 – bit signed integer, you need to invert each digit of the integer. Assuming that our environment can store only 32-bit signed integers, the value range is [−231-2^{31}−231, 2312^{31}231]. Based on this assumption, return 0 if the integer overflows after inversion.

After reading the questions, I asked myself a few questions and found that I didn’t know:

  1. What is a 32-bit integer? What does 32 bits mean?
  2. Why is the range of 32 a signed integer [−231-2^{31}−231, 2312^{31}231]?
  3. How do I write binary?

Pull out your calculator and calculate in binary: 2322^{32}232=4294967295, 2312^{31}231=2147483647

At this point, the above problem is basically solved, and a new one comes:

  1. How does binary represent positive and negative numbers
  2. How do you calculate positive and negative numbers in binary? How do computers deal with that
  3. What is source code? Radix-minus-one complement? Complement?
  4. How is Integer handled in Java?

2. Get down to business

2.1. Binary, source, inverse and complement

Why complement?

In this example, four bits are used. The highest bit of the binary system is 0 + and 1 –

The integer The original code
4 0 100
4 – 1, 100
0 0000
5 0 101
– 5 1, 101
2 0010
7 0 111
7 – 1, 111
5 0110

Since there is no subtraction in computers, we find that the sum of the positive and negative numbers of these numbers is correct only with the binary calculation of 4, which results in 0. In order to solve this problem, so there is the concept of inverse code, complement.

The integer The original code Radix-minus-one complement complement
4 0 100 0 100 0 100
4 – 1, 100 1, 011 1, 100
0 – – 0000
5 0 101 0 101 0 101
– 5 1, 101 1, 010 1, 011
0 – – 0000
7 0 111 0 111 0 111
7 – 1, 111 1, 000 1, 001
0 – – 0000

Through the complement of positive and negative numbers, the result is correct

2.1.1. The original code

The highest bit represents a plus or minus sign, 0 represents an integer, 1 represents a negative number, and the other bits represent the binary of the value

2.1.2. Radix-minus-one complement

  • The inverse of a positive number: the same as the original code
  • The inverse of negative numbers: the highest sign bit is unchanged, the other bits are reversed

2.1.3. Complement

  • Complement of a positive number: identical to the original code
  • Complement for negative numbers: inverse + 1

2.2. Integer in Java

    @Test
    void testLocal(a) {
        Integer maxInt = Integer.MAX_VALUE;
        Integer minInt = Integer.MIN_VALUE;

        log.info(Decimal: min = {}, Max = {}", minInt, maxInt);
        String minBinary = Integer.toBinaryString(minInt);
        String maxBinary = Integer.toBinaryString(maxInt);
        log.info(Binary: minBinary {} bit = {}, maxBinary {} bit = {}", minBinary.length(), minBinary, maxBinary.length(), maxBinary);
        log.info("int 0 = binary {}", Integer.toBinaryString(0));

        log.info("{} = {}, {} = {}", minInt + 1, Integer.toBinaryString(minInt + 1), maxInt - 1, Integer.toBinaryString(maxInt - 1));
        log.info("IntMax + 1 = {}", maxInt + 1);
    }
Copy the code

The size of an Integer in Java is 32 bits, ranging from −231-2^{31}−231, 2312^{31}231] to 31 bits, with the highest bit 0/1 representing positive and negative values.

From the binary point of view, the maximum value of a positive Integer is 31 bits 1, and then all bits are carried by 1 to 0. The result is that the highest bit is 0 -> 1, and the binary result is the same as the minimum value of a negative Integer.

2.3 Int Minimum (2021.3.2)

Integer maximum and minimum values in Java are not clearly defined.

The minimum value of an int negative number is 32 1’s. The minimum value of an int negative number is 32 1’s. In fact, after converting to binary in Java is the inverse of negative numbers, let’s look at the conversion process

// 0 to 1 to the largest positive integer 2,147,483,647, a total of 2,147,483,648 digits, the corresponding binary values are as follows
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 = 0
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 = 1
0111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 = 2.147.483.647

// Minimum negative integer -2,147,483,648 to -1, also 2,147,483,648 digits
1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 = -2.147.483.648
1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 = -2.147.483.647
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 = -1

// Negative binary in Java is the inverse of signed binary

// Binary of 1
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 = 1
// The process of converting -1
1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 = -1
// The inverse of negative numbers: the highest sign bit remains unchanged, the other bits are reversed
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1110
// Complement for negative numbers: inverse + 1
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 = -1
Copy the code

In this way, it is found that the binary of a negative number is its complement. In particular, 0 can be seen as [+0] and [-0], [+0]=0, [-0]=-2,147,483,648. All of this can be derived in binary form.

3. Summary

  1. Computing in the computer only addition and binary, for the original code, inverse code, complement is to solve the computer operation
  2. Integer out of bounds is the process of converting the binary result into an integer with a fixed 32-bit length
  3. Through a question to extend a series of problems, from the numerical range -> binary representation -> with/without sign -> binary calculation -> source/inverse/complement -> integer boundary crossing…

4. The last

How do Java shift operators (“<<“, “>>”, “>>>”) operate?