1. Bitwise Operations Overview

In modern computers, all data is stored in binary form, i.e., two states: 0 and 1. Operations performed by computers on binary data (such as addition, subtraction, multiplication, and division) are called bitwise operations, which are operations that operate on each bit of a binary number.

To better understand bitwise operations, here is a simple example: suppose we have the following code to perform addition of two integers:

int a = 35;
int b = 47;
int c = a + b;

The computer converts these two integers into binary form, and then performs the addition:

35:  0010 0011
47:  0010 1111
----------------
82:  0101 0010

Therefore, compared with directly using+、-、*、/operators, the reasonable use of bitwise operations can significantly improve the execution efficiency of the code on the machine.

2. Bitwise Operations at a Glance

3. Bitwise AND Operator (&)

Definition: performs an "AND" operation on the binary bits of the two data operands involved.

Operation rule：

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

Summary: Only when both bits are 1, the result is 1; otherwise, the result is 0.

For example:3 & 5i.e.0000 0011 & 0000 0101 = 0000 0001, therefore3 & 5the value is 1.

Note: Negative numbers participate in bitwise AND operations in two's complement form.

Applications：

1. Clear to zero: If you want to clear a unit to zero, just AND it with a value whose bits are all zero; the result is zero.
2. Extract the specified bits of a number: For example, take theX = 1010 1110low 4 bits of a number, just find another numberY = 0000 1111, thenX & Y = 0000 1110you can getXthe specified bits.
3. Determine odd or even: By checking whether the least significant bit is 0 or 1 to determine parity, you can useif ((a & 1) == 0)instead ofif (a % 2 == 0)to determineawhether it is even.

4. Bitwise OR Operator (|)

Definition: performs an "OR" operation on the binary bits of the two operands involved.

Operation rule：

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

Summary: As long as one of them is 1, the result is 1.

For example:3 | 5i.e.0000 0011 | 0000 0101 = 0000 0111, therefore3 | 5the value is 7.

Note: Negative numbers participate in bitwise OR operations in two's complement form.

Applications：

1. Set certain bits to 1: For example, to set theX = 1010 1110low 4 bits of a number to 1, just find another numberY = 0000 1111, thenX | Y = 1010 1111you can get it.

5. Bitwise XOR Operator (^)

Definition: performs an "XOR" operation on the binary bits of the two data operands involved.

Operation rule：

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

Summary: If the corresponding bits are the same, the result is 0; if they are different, the result is 1.

Properties：

1. Commutative law
2. Associative law:(a ^ b) ^ c == a ^ (b ^ c)
3. For any numberx, it holds thatx ^ x = 0，x ^ 0 = x
4. Self-inverse:a ^ b ^ b = a ^ 0 = a

Applications：

1. Flip the specified bits: For example, to flip theX = 1010 1110low 4 bits of a number, just find another numberY = 0000 1111, thenX ^ Y = 1010 0001you can get it.
2. XOR with 0 keeps the value unchanged: for example1010 1110 ^ 0000 0000 = 1010 1110
3. Swap two numbers：

void Swap(int &a, int &b) {
if (a != b) {
    a ^= b;
    b ^= a;
    a ^= b;
}
}

6. Bitwise NOT Operator (~)

Definition: performs a "NOT" operation on the binary bits of the single operand involved.

Operation rule：

~1 = 1111 1110
~0 = 1111 1111

That is:

~1 = -2
~0 = -1

Summary: Change 0 to 1, and 1 to 0.

Applications：

1. Set the least significant bit of a number to zero: For example, to setathe least significant bit of a number to 0, it can be expressed as:a & ~1。~1the value of ... is1111 1111 1111 1110, then perform an "AND" operation, and the least significant bit will certainly be 0.

7. Left Shift Operator (<<)

Definition: Shift all binary bits of an operand to the left by a certain number of positions; high bits are discarded, and low bits are filled with 0.

For example, leta = 1010 1110，a = a << 2willathe binary bits of ... be shifted left by 2 positions, with zeros filled in on the right, resulting ina = 1011 1000。

If the high bits discarded during left shifting do not contain a 1, then each left shift by one position is equivalent to multiplying the number by 2.

8. Right Shift Operator (>>)

Definition: Shift all binary bits of a number to the right by a certain number of positions; high bits are filled with 0 or the sign bit, and the right side is discarded.

For example,a = a >> 2willathe binary bits of ... are shifted right by 2 positions, with the left side filled with 0 or the sign bit, depending on whether the number is positive or negative.

Each time an operand is shifted right by one position, it is equivalent to dividing the number by 2.

9. Compound Assignment Operators

Bitwise operators are combined with assignment operators to form new compound assignment operators, which are:

• &= Example:a &= bis equivalent toa = a & b
• |= Example:a |= bis equivalent toa = a | b
• >>= Example:a >>= bis equivalent toa = a >> b
• <<= Example:a <<= bis equivalent toa = a << b
• ^= Example:a ^= bis equivalent toa = a ^ b

The operation rules are similar to those of the compound assignment operators mentioned above.

Bitwise operations on data of different lengths：

If two data items of different lengths undergo a bitwise operation, the system aligns them by their right ends and then performs the bitwise operation.

Take the "AND operation" as an example:

In C language,longtype occupies 4 bytes,inttype occupies 2 bytes. If alongtype data and ainttype data undergo an "AND operation", after aligning to the right, the insufficient bits on the left are filled according to the following three cases:

1. If the integer data is positive, the left bits are filled with 16 zeros.
2. If the integer data is negative, the left bits are filled with 16 ones.
3. If the integer data is unsigned, the left bits are also filled with 16 zeros.

For example:

long a = 123;
int b = 1;
long result = a & b;

long a = 123;
unsigned int b = 1;
long result = a & b;