The two data participating in the operation are ANDed according to the binary bits.

Operation rules: 0&0=0;?0&1=0;1&0=0;1&1=1;

?That is: the result is "1" only if both bits are "1" at the same time ”, otherwise it is 0

For example: 3&5? That is, 0000 0011& 0000 0101 = 00000001? Therefore, 3&5 is worth 1.

In addition, negative numbers participate in bitwise AND operations in two's complement form.

Special uses of "AND operation":

(1) Clear. If you want to clear a cell to zero, even if all its binary bits are 0, just AND it with a value whose bits are all zero, and the result will be zero.

(2) Take the specified bit in a number

Method: Find a number that corresponds to the bit to be taken by X. The corresponding bit of the number is 1, and the remaining bits are zero. This The specified bit in X can be obtained by performing an "AND operation" on the number and X.

Example: Suppose X=10101110,

Take the lower 4 digits of Take the 2, 4, and 6 digits of X.

The two objects participating in the operation perform an "OR" operation based on binary bits.

Operation rules: 0|0=0; ?0|1=1; ?1|0=1; 1|1=1;

That is: the two As long as one of the objects is 1, its value is 1.

For example: 3|5　that is 00000011?| 0000 0101 = 00000111? Therefore, 3|5 is worth 7.

In addition, negative numbers participate in bitwise OR operations in two's complement form.

Special functions of "OR operation":

(1) Often used to set certain positions of a data to 1.

Method: Find a number that corresponds to the bit of X to be set to 1. The corresponding bit of the number is 1, and the remaining bits are zero. This number is relative to X or sets some position in X to 1.

Example: Set the lower 4 bits of X=10100000 to 1 and use X?| 0000 1111 = 1010 1111 to get it.

The two data participating in the operation perform an "exclusive OR" operation based on binary bits.

Operation rules: 0^0=0; ?0^1=1; ?1^0=1; ? 1^1=0;

That is: the two An object, if the two corresponding bits are "exclusive" (different values), the result of the bit is 1, otherwise it is 0.

The special function of "XOR operation":

(1) Flip specific bits to find a number that corresponds to the bits of X to be flipped. The corresponding bit of the number is 1, and the rest If the bit is zero, this number can be XORed with the corresponding bit of X.

Example: X=10101110, flip the lower 4 bits of

(2) XOR with 0, retain the original value, X ^ 00000000 = 1010 1110.

Let’s focus on bitwise XOR. XOR is actually addition without carry, such as 1+1=0, 0=0, 1+0=1.

Several properties of XOR:

1. Commutative law

2. Associative law (i.e. (a^b)^c == a^( b^c))

3. For any number x, x^x=0, x^0=x

4. Reflexivity:? a^b^ b=a^0=a;

The XOR operation is most commonly used in polynomial division, but its most important property is reflexivity: A XOR B XOR B = A, that is, for a given number A , after using the same operation factor (B) to perform two XOR operations, A itself is still obtained. This is a magical property that can lead to many interesting applications. For example, all programming textbooks will point out to beginners that to exchange the values ??of two variables, an intermediate variable must be introduced. But if you use XOR, you can save the storage space of a variable: Given two variables A and B, the stored values ????are a and b respectively, then the following three lines of expressions will interchange their value expressions (values) ：

a=a^b;

b=b^a;

a=a^b;

Application example 1 :

1-1000 is placed in an array containing 1001 elements. Only one element value is repeated, and the others only appear once

. Each array element can only be accessed once. Design an algorithm to find it. Can you design an algorithm to implement it without auxiliary storage space

?

Solution 1. Apparently someone has proposed a more exciting solution, add up all the numbers and subtract the sum of 1+2+...+1000.

This algorithm is perfect enough. I believe that the standard answer of the questioner is this algorithm. The only problem is that if the sequence is too large, it may cause overflow.

Solution 2, XOR, does not have this problem and has better performance.

XOR all the numbers, and the result is XORed with the result of 1^2^3^...^1000, and the result is the duplicate number.

Shift all the binary bits of an operand to the left by a certain number of bits (the left bits are discarded and the right bits are filled with 0).

Example: a = a<< 2 Shift the binary bits of a to the left by 2 bits and add 0 to the right.

After shifting by 1 bit to the left, a?=?a *2;?

If the high bit discarded when shifting left does not contain 1, then each left shift is equivalent to multiplying the number by 2.

Shift all the binary digits of a number to the right by a certain number of bits. Positive numbers are left padded with 0s, negative numbers are left padded with 1s, and the right sides are discarded.

Each right shift of the operand by one bit is equivalent to dividing the number by 2.

For example: a = a>> 2 Shift the binary bit of a to the right by 2 bits,

Add 0 to the left? Or add 1 to the left, depending on whether the number being moved is positive or negative.

If two data of different lengths are subjected to bit operations, the system will align them on the right end and then perform bit operations.

Taking the "AND" operation as an example, the explanation is as follows: We know that in C language, the long type occupies 4 bytes and the int type occupies 2 bytes. If a long type data is compared with an int type data, "AND" operation, after the right end is aligned, the insufficient bits on the left are filled according to the following three situations.

(1) If the integer data is a positive number, 16 0s are added on the left.

(2) If the integer data is a negative number, 16 1s are added to the left.

(3) If the integer data is an unsigned number, 16 0s are also added to the left.

For example: long a=123; int b=1; calculate a& b.

For example: long a=123; int b=-1; calculate a& b.

For example: long a=123; unsigned intb=1; calculate a & b.