From: juejin. Cn/post / 684490…

Writing in the front

Binary bit operation is the most close to the real operation of the computer, through bit operation, we can efficiently complete a variety of basic operations (addition, subtraction, multiplication, division, take more than, etc.), we can also use bit operation clever to complete the original very complex work, truly understand the computer, we can better use the computer. In this article, I’ll start with a basic understanding of how Java works in practice.

The number of machines and the truth of the number of machines

The binary representation of a number in a computer is called the machine number of that number. Machine number is signed, the highest bit of the number of machines used by the computer to store the symbol, positive number is 0, negative number is 1. For example, in the case of 8-bit machine word length (which is the number of bits of binary data directly processed by the computer, which determines the accuracy of the computer’s operations), the +3 in decimal, If you convert it to binary it’s 0000 0011, if you convert it to negative 3 it’s 1000 0011. The converted binary numbers 0000 0011 and 1000 0011 are the machine numbers.

Here we also need to know the truth value of machine number, since the first machine number is a sign bit, so the formal value of machine number is not equal to the real value. For example, the signed number 1000 0011 above, whose highest bit 1 represents negative, has a true value of -3, not the formal value 131 (1000 0011 in decimal is 131), so, for the sake of distinction, the real value corresponding to the signed number of machines is the true value of the number of machines. For example, 0000 0001 = +000 0001 = +1 1000 0001 = — 000 0001 = — 1

Basic concepts and calculation methods of source code, inverse code and complement code

Above we have seen the machine number, or binary number, but the computer uses a certain encoding method to store, source code, inverse code and complement code is the machine to store a specific number of encoding.

The original code

The source code is the sign bit plus the absolute value of the truth value, i.e. the first bit represents the symbol and the rest of the bits represent the value.

[+1]原= 0000 0001

[-1] Original = 1000 0001

The first digit is a sign bit, and since the first digit is a sign bit, the range of values for 8-bit binary numbers is :(i.e. the first digit does not represent a value, only positive and negative digits.) [1111 1111, 0111 1111], which is the decimal number [-127, 127].

Radix-minus-one complement

The inverse of a positive number is itself, and the inverse of a negative number is the basis of its original code.

[+1] = [0000 0001] = [0000 0001

[-1] = [1000 0001] = [1111 1110

complement

The expression of complement is that the complement of a positive number is itself, and the complement of a negative number is based on its original code, the sign bits remain unchanged, the other bits are reversed, and finally +1 (that is, +1 based on its inverse code).

[+1] = [0000 0001] Original = [0000 0001] inverse = [0000 0001] complement

[-1] = [1000 0001] Original = [1111 1110] inverse = [1111 1111] complement

Knowing these three basic concepts, it is worth mentioning that if the inverse code is added, it will produce the problem of two zeros (-0 and +0), so we use the complement code, not only to fix the zero symbol and the existence of two coding problems, but also can represent one more lowest number. This is why 8-bit binary, represented in source or inverse, ranges from [-127, +127] to [-128, 127] in complement. [-231, 231-1] [-231, 231-1] [-231, 231-1] [-231, 231-1] [-231, 231-1]

Operators in Java

Attention, all of the following bit operations are through the complement, the complement of a positive number is its itself, negative number corresponding to the own, both operands is positive, the result will directly take binary decimal, if two operands one is negative or both negative, the result if the sign bit is 1 (negative), is the complement, You need to convert from the complement to the source code, and then to decimal, if the resulting symbol bit is 0, take the binary to decimal. That is to say, when you do the operation, you take the original on the negative. You can first convert all of the following decimal numbers into binary complement, and then take it in to see if it is correct.

The xOR operation symbol is “^”, the same is 0, different is 1, the code example is as follows:

public static void main(String[] args) {
    System.out.println("The result of 2^3 is :"+(2^3));
    //打印的结果是:   2^3 运算的结果是 :1
}

//2 的二进制 0010，3 的二进制 0011，2^3 就为 0001，结果就是 1

public static void main(String[] args) {
    System.out.println(The result of the -2^3 operation is:+ (2 ^ 3)); // The result of the operation is :-3} // the binary complement of -2 is 1110, the binary complement of 3 is 0011, and -2^3 is 0001Copy the code

The and symbol is “&”, as long as one of the 0 is 0, the code example is as follows:

public static void main(String[] args) {
     System.out.println("The result of 2&3 is :"+ (2 & 3)); 2} public static void main(String[] args) {system.out.println () {public static void main(String[] args) {system.out.println ("The result of -2&3 is :"+ (- 2 & 3)); // The result of the -2&3 operation is :2} copy codeCopy the code

Or operator is “|”, as long as there is a 1 is 1, the code for the following:

public static void main(String[] args){
    System.out.println("The result: 2 | 3 operation"2 | + (3)); / / print the result is: 2 | 3 operation result: 3} public static void main (String [] args) {System. Out. Println ("- 2 | 3 operation result is:"+ (- 2 | 3)); / / print the result: - 2 | 3 operation result: - 1} copy codeCopy the code

The non-operator is “~”, that is, the inverse, the code example is as follows:

public static void main(String[] args){
    System.out.println(The result of the ~5 operation is:+ (~ 5)); -6} public static void main(String[] args){system.out.println (){public static void main(String[] args){system.out.println ("The result of ~(-5) is:"+ (~ (5))); The result of the ~(-5) operation is: 4} copy the codeCopy the code

Left shift symbol “<<, the binary moves n bits to the left, followed by a complement of 0

public static void main(String[] args) {
     System.out.println("The result of 2<<3 is :"+ (2 < < 3)); 16} public static void main(String[] args) {system.out.println () {public static void main(String[] args) {system.out.println (The result of the -2<<3 operation is:+ (- 2 < < 3)); // The print result is: -2<<3 operation means, move 3 bits to the left, the result is :-16} copy codeCopy the code

Shift the symbol “>>” to the right, the binary moves n bits to the right, if the value is positive, 0 is inserted at the high level, if the value is negative, 1 is inserted at the high level

public static void main(String[] args) {
     System.out.println("2>>3 results in :"+ (2 > > 3)); } public static void main(String[] args) {system.out.println ();} public static void main(String[] args) {system.out.println ();The result of the -2>>3 operation is:+ (- > 2 > 3)); // Print the result: -2>>3 Operation means, move 3 bits to the right, the result is :-1} copy codeCopy the code

Unsigned move the sign “>>>” to the right, ignoring the sign bit and filling the empty space with 0. The only difference between “>>>” and “>>” is that it is filled with zeros regardless of the original leftmost number. For example, if byte is 8 bits, -1 means byte is 11111111(complement notation) b>>>4 means unsigned 4 bits to the right, 00001111, resulting in 15. (Whisper beep beep, don’t ask me if I moved left unsigned, it’s a very low question when you really understand it.)

public static void main(String[] args) {
     System.out.println(The result of operation 16>>2 is:+ ((16) > > 2)); 4} public static void main(String[] args) {system.out.println () {public static void main(String[] args) {system.out.println ("-16>>2 results in:+ (16) (- > > 2)); Public static void main(String[] args) {system.out.println (String[] args) {system.out.println (The result of the 16>>>2 operation is:+ ((16) > > > 2)); 4} public static void main(String[] args) {system.out.println () {public static void main(String[] args) {system.out.println ("-16>>>2 results in :"+ (16) (- > > > 2)); // The printed result is: -16>>>2 The operation result is :1073741820} Duplicate codeCopy the code

You don’t have to multiply and divide

add

Taking 13+9 as an example, we split the operation like this:

  • Step 1: Add each digit without considering the carry, and the result is “sum”, the units digit 3 plus 9 is 2. Ten digit 1 plus 0 is 1; The final result is 12;
  • Step 2: Only carry is considered, the result is stored as CARRY, 3 + 9 has carry, and the carry value is 10;
  • Step 3: If the carry result obtained in step 2 is not 0, repeat steps 1, 2, and 3 for sum obtained in step 1 and carry obtained in step 2. If carry is 0, it ends, and the final result is sum obtained in step 1.

Sum = 12 and carry = 10

  • (a) Add the digits separately without considering the carry, sum = 22;
  • (b) Only carry is considered: there is no carry in the previous step, so carry = 0; (c) Step 2CARRY = 0, end, sum = 22.

This is our demonstration in decimal, so let’s switch to binary to see if it is the same. The binary number of 13 is 0000 1101 and the binary number of 9 is 0000 1001:

  • Sum = 0000 1101 + 0000 1001 = 0000 0100
  • Step 2: Consider the carry, there are two places of carry, 0 and 3, only consider the carry result: CARRY = 0001 0010
  • Step 3: Carry == 0? , is not 0, repeat steps 1, 2, 3; 0 ends, and the result is sum.

In this case,

  • Ignore the carry sum = 0001 0110;
  • Only carry = 0 is considered;
  • Carry == 0, end, sum = 0001 0110

In decimal it’s exactly 22. There are actually three steps, which you can visualize in pseudocode as follows, this time using 3+9 as an example.

a = 0011, b = 1001; start; first loop; 1.1 sum = 1010 1.2 carry = 0010 1.3 carry! = 0 , go on; second loop; 2.1 the sum = 1000; 2.2 carry = 0100; 2.3 carry! = 0, go on; third loop; 3.1 the sum = 1100; 3.2 carry = 0000; 3.3 carry == 0, stop; result = sum; End copy codeCopy the code
Int add(int a,int b){// add(int a,int b){if (b == 0)
        return a;
    else{
        int carry = (a & b) << 1;
        a = a ^b;
        returnadd(a,carry); Int add2(int a,int b){int carry;while(b ! = 0){ carry = (a & b) << 1; a = a ^b; b = carry; }returna; } Duplicate codeCopy the code

subtraction

We know that bit operations add, so subtraction is a little bit easier. We implemented addition, and naturally, we would think to transform subtraction 11 minus 6 into addition 11 plus minus 6, which is a positive plus a negative number. Yes, very clever, in fact our computers operate in this way, so some people say why don’t computers implement a subtracter like an adder? Yes, that’s a reasonable assumption, but given that subtraction is much more complicated than addition, it’s difficult to implement. Why is that? We know that addition actually only has two operations, add and carry, and subtraction, subtraction has a borrowing operation, and if you don’t subtract enough you borrow from the higher end, and there’s a problem here, what’s the borrowing? In addition, carry is done by adding and and moving one bit to the left, while borrowing is really hard to represent. So we naturally want to convert subtraction to addition. How do you do that?

We just said that subtraction can be converted to a positive number plus a negative number, so let’s first look at how negative numbers are represented in computers.

Plus 8 is represented in the computer as 1000 in binary, so what about minus 8? It is easy to imagine that a binary bit (bit) can be designated as a sign bit, representing a positive number when it is equal to 0 and a negative number when it is equal to 1. For example, in an 8-bit machine, the highest bit of each byte is specified as a sign bit. So, plus 8 is 00001000, and minus 8 is 10001000. Here’s a simple way to express a negative number. The computer represents a negative number by the complement of 2. It is a method to represent signed numbers in binary, and it is also a way to change the signs of positive and negative numbers.

  • The first step is to take the opposite value of each binary bit, with 0 becoming 1 and 1 becoming 0.
  • In the second step, add 1 to the value obtained in the previous step.

It’s just like taking minus plus one!

int subtraction(int a ,int b){
     b = ~b+1;
     returnthis.add(a,b); } Duplicate codeCopy the code

The multiplication

Consider the process of taking the product manually in real life, and this method also applies to binary. Let me take 13*14 as an example to show you how to take the product of the absolute value of the multiplier and the multiplier manually.

As can be seen from the calculation process in the figure above, if the current bit of the multiplier is 1, the result of moving the multiplier one bit to the left is added to the final result. If the current bit is 0, add 0 to the product (adding 0 means doing nothing)

  • Determine whether the multiplier is 0, if 0, jump to Step (4)
  • Perform and operation on the multiplier and 1 to determine whether the last bit is 1 or 0. If it is 1, the sum is the current multiplicand; If 0, the sum is 0; To add a phase addend to the final result;
  • Multiplied by one to the left, multiplied by one to the right; Back to Step (1)
  • Determine the sign bit, output the result;
Int a multi (int a,int b){int I = 0; int res = 0; // The multiplier is not 0while(b ! = 0){// process the current bit // The current bit is 1if((b & 1) == 1){ res += (a << i); b = b >> 1; I++; }else{// the current bit is 0 b = b >> 1; i++; }}returnres; } Duplicate codeCopy the code

division

It’s easy to think of division as a subtraction operation, where you keep subtracting the dividend by the divisor until the dividend is less than the divisor, and the number of subtractions is the quotient we need, and the remainder is the dividend. What needs to be noted here is the determination of the sign. The sign of the quotient is the same as that of the product in the multiplication operation, that is, it depends on the divisor and dividend. The same sign is proof, and the different sign is negative. The remainder has the same sign as the dividend. Computers are a binary world, and all ints can be represented by a base of [2^0, 2^1… 2^31] (up to 31 bits of int). It’s not hard to think of divisor 2^31, 1,2^30… 2^2,2^1,2^0 tries to subtract the dividend, and if it works, adds the corresponding multiple to the quotient; If that doesn’t work, try smaller multiples in turn. This allows you to quickly approximate the final result.

Two to the I is the same thing as moving one to the left, so why start at the 31st place? Because the maximum value of an int is 2^31.

    int division(int a,int b){
          int res;
          if(a<b){
              return 0;
          }else{
              res=division(subtraction(a, b), b)+1;
          }
          return res;
     }Copy the code