Introduction to bit operations and application scenarios in java

We know that all numbers in the program are stored in binary form in computer memory, and bit operations are to directly operate on the binary bits of integers in memory. For example, the and operation is originally a logical operator, but the AND operation can also be performed between integers.

Bit operations mainly include shift operations and logical operations. Next we will talk about shift operations and logical operations respectively.

Shift operation:

Left shift: The operator is <<, move to the left, add 0 to the low bit on the right, discard the high bit on the left, treat binary as an integer, shift left by 1 bit is equivalent to multiplying by 2. Unsigned right shift: The operator is >>>, moving to the right, discarding the right side, and adding 0 to the left side. Signed right shift: The operator is >>, move to the right, and discard the right side. The value added to the left depends on the original highest bit. If it is originally 1, add 1, and if it is 0, add 0. Think of binary as For an integer, shifting it right by 1 bit is equivalent to dividing by 2.

For example:

int a = 4; // 100
a = a >> 2; // 001，等于1
a = a << 3 // 1000，变为8

Logical operations include:

• Bitwise AND&: both bits are 1 to be 1

• Bitwise OR|: As long as one bit is 1, it is 1

• ##Bitwise negation~: 1 becomes 0, 0 becomes 1

• bitwise Application scenarios:
  Scenario 1: Determine parity

Analysis: Odd numbers are not integer multiples of 2. After conversion to binary, the lowest bit must be 1, and the opposite is true for even numbers. Using this feature, we can easily determine the parity of an integer through bit operations.

Look at the code:

int a = ...; 
a = a & 0x1 // 返回0或1，就是a最右边一位的值。
a = a | 0x1 //不管a原来最右边一位是什么，都将设为1

Scenario 2: Determine whether a positive integer is an integer power of 2

Analysis: Let’s first look at the common integer powers of 2 The numbers: 2, 4, 8, 16, converted into binary are: 10, 100, 1000, 10000. Have you found the pattern? That is, except for the first bit which is 1, the others are all 0. It just so happens that after subtracting 1 from these numbers, they equal the results of their bitwise inversions. For example, 8-1=7, which is 111 in binary, can be obtained by bitwise inverting the binary 1000 of 8. And 8&7=0, extract the rule and it is:

   int i = 1;// 二进制存储方式为00000000000000000000000000000001
    int j = 5;// 二进制存储方式为00000000000000000000000000000101
    int k = 6;// 二进制存储方式为00000000000000000000000000000110
    if ((i & j) == 1) {
      System.out.println("j的最低位为1，为奇数");
    }    if ((i & k) == 0) {
      System.out.println("k的最低位为0，为偶数");
    }

The n that conforms to this rule is an integer power of 2.

(Learning video sharing:

java video tutorial

)

Scenario 3: Simple collection processing

No nonsense, just look at the code:

(n&(n-1))==0

Test it:

public class SimpleSet {  public static final int A = 0x01;// 最后四位为0001
  public static final int B = 0x02;// 最后四位为0010
  public static final int C = 0x04;// 最后四位为0100
  public static final int D = 0x08;// 最后四位为1000
  private int set = 0x00;// 初始0000，空集合
  public void add(int i) {// 将i对应位的值置为1，重复add不影响。默认传入值为ABCD之一，此处省去边界判断
    set |= i;
  }  public boolean contain(int i) {// 判断相应位置是否为1
    return (set & i) == i;
  }  public boolean remove(int i) {// 来不及不解释了快看代码
    if (contain(i)) {
      set -= i;      return true;
    } else {      return false;
    }
  }
}

The output is:

 public static void main(String[] args) {
    SimpleSet set = new SimpleSet();
    System.out.println(set.contain(A));
    set.add(B);
    System.out.println(set.contain(A));
    System.out.println(set.contain(B));
    set.add(A);
    set.add(C);
    System.out.println(set.contain(A));
    set.remove(A);
    System.out.println(set.contain(A));
    System.out.println(set.remove(A));
    System.out.println(set.contain(C));
  }

Okay, no problem.

You may think that A, B, C, and D in the above example code are somewhat similar to enumerations. In fact, the collection class EnumSet in the jdk source code for enumerations uses a similar solution. Of course it is much more complicated than this. If you are interested, you can check out the source code. This solution has a name, called bit vector.

By the way, there are many static tools in Integer, the packaging class of int in Java, that provide bit operations, and most of them are very complicated. If you are interested, you can take a look.

Conclusion:

Bitwise operations are the operations that computers are best at, and they are also used extensively in the source code of jdk. Understanding them will help us understand the computer more deeply, and it will also help us write more elegant code.

Related recommendations:

java introductory tutorial

The above is the detailed content of Introduction to bit operations and application scenarios in java. For more information, please follow other related articles on the PHP Chinese website!