What is bit operation

Let's talk about bit operation first. All numbers in the program are stored in binary form in the computer memory. Bit operation is to directly operate the binary bits of integers in memory. To put it bluntly, bit operation is to operate the binary of integer in memory.

c# corresponding bit operation

Operation symbol	significance	Operation object type	Operation result type	Number of objects	example
~	Bit logical non operation	Integer, character	integer	1	~a
&	Bit logic and operation			2	a & b
|	Bitwise logical or operation			2	a | b
^	Bit logical XOR operation			2	a ^ b
<<	Bit shift left operation			2	a<<4
>>	Bit shift right operation			2	a>>2

     

 

 

 

 

 

 

 

Usage scenario of bit operation

    

1. Inversion of ~ position

The operator rule is: reverse the binary number after the operator, 0 becomes 1, and 1 becomes 0. Therefore, take an inverse even number of times for a number, and the result is itself.

For example:

0000 0000 0000 0000 0000 0000 0000 0011 -> 3 1111 1111 1111 1111 1111 1111 1111 1100 -> ~ 3 = -4

Common scenarios:

Find the opposite number: ~ a + 1

2. < < move left

The operator rule is: all binary bits are shifted to the left by several bits, the high bits are discarded, and the low bits are supplemented by 0.

For example: 6 < < 2 = 24

0000 0000 0000 0000 0000 0000 0000 0110 -> 6 0000 0000 0000 0000 0000 0000 0001 1000 -> 6 << 2 = 24

We move the binary of 6 to the left by two bits, add two zeros to the low bit, and discard the high bit. The result is 24.

Common scenarios:

The left shift is often used for * (2 ^ n) operation. Because it is directly based on binary operation, the left shift efficiency is higher than * (2 ^ n).

3. > > shift right

The operator rule is: all binary bits are shifted to the right by several bits, the high bit of positive number is supplemented by 0, the high bit of negative number is supplemented by 1, and the low bit is discarded.

For example: 12 > > 2 = 3

0000 0000 0000 0000 0000 0000 0000 1100     -> 12 0000 0000 0000 0000 0000 0000 0000 0011     -> 12 >> 2 = 3

Because 12 is a positive number, in the process of moving to the right, the high position is supplemented with two zeros, and the low position is discarded. The result is 3.
For example: - 12 > > 2 = - 3

1111 1111 1111 1111 1111 1111 1111 0100    -> -12 1111 1111 1111 1111 1111 1111 1111 1101    -> -12 >> 2 = -3

Because - 12 is a negative number, in the process of moving to the right, the high position is supplemented with two 1s, and the low position is discarded. The result is - 3.

Common scenarios:

Shift right is often used for / (2 ^ n) operations. Because it is directly based on binary operations, the shift right efficiency is higher than that of / (2 ^ n).

4. > > > move right without symbol

The operator rule is: all binary bits are shifted to the right by several bits, the high bit is supplemented by 0, and the low bit is discarded.

For example: 12 > > > 2 = 3

0000 0000 0000 0000 0000 0000 0000 1100     -> 12 0000 0000 0000 0000 0000 0000 0000 0011     -> 12 >>> 2 = 3

We move the binary of 12 to the right by two bits, add two zeros to the high bit, and discard the low bit. The result is 24.
For example: - 12 > > > 2 = 1073741821

1111 1111 1111 1111 1111 1111 1111 0100    -> -12 0011 1111 1111 1111 1111 1111 1111 1101    -> -12 >> 2 = 1073741821

We move the binary of - 12 to the right by two bits, add two zeros to the high bit, and discard the low bit. The result is 1073741821.

 

5. & bit and
The operator rule is: if there are 0 on both sides of the operator, the result will be 0. Only if both sides are 1 at the same time, the result will be 1.

As follows:

 0 & 0 = 0；     0 & 1 = 0；     1 & 0 = 0；       1 & 1= 1；

For example: 3 & 5

0000 0000 0000 0000 0000 0000 0000 0011 -> 3 0000 0000 0000 0000 0000 0000 0000 0101 -> 5 0000 0000 0000 0000 0000 0000 0000 0001 -> 3 & 5 = 1

Special purpose of bit and operation:

1. Clear (perform bit sum operation between a unit and 0, and the result is zero)
2. Take a number to refer to positioning (for example, take the lower four bits of num=1010 1101, then get 0000 1101 from num & 0xf).
3. Judge parity: use if ((A & 1) = = 0) instead of if (a% 2 = = 0) to judge whether a is an even number.

6. | bit or
The operation rule is that if there are 1 on both sides of the operator, the result will be 1. Only if both sides are 0 at the same time, the result will be 0.

As follows:

0 | 0 = 0；  0 | 1 = 1；  1 | 0 = 1；   1 | 1 = 1 ；

For example: 3|5

0000 0000 0000 0000 0000 0000 0000 0011 -> 3 0000 0000 0000 0000 0000 0000 0000 0101 -> 5 0000 0000 0000 0000 0000 0000 0000 0111 -> 3 | 5 = 7

In addition, negative numbers participate in bitwise or operations in the form of complement.

Usage scenario:

The following method is taken from the HashMap class. This algorithm modifies the size passed in by the user using the constructor. This algorithm is implemented by shift and or combination, and its performance is better than circular judgment.

public static final int tableSizeFor(int cap) {     int n = cap - 1;     n |= n >>> 1;     n |= n >>> 2;     n |= n >>> 4;     n |= n >>> 8;     n |= n >>> 16;     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

 

7. ^ bit exclusive or
The operation rule is: when both sides of the operator are in the same position, the result returns 0, and if not, 1.

For example: 3 ^ 5 = 1

0000 0000 0000 0000 0000 0000 0000 0011 -> 3 0000 0000 0000 0000 0000 0000 0000 0101 -> 5 0000 0000 0000 0000 0000 0000 0000 0110 -> 3 ^ 5 = 6

Usually, when we exchange two numbers, we use a temporary variable to help: