1. Bit operators
-
Left shift (<<) : 0011 << 1 = 0100, expressed in decimal equivalent to multiplying by 2
-
Move right (>>) : 0110 >> 1 = 0011, represented in decimal equivalent of dividing by 2
-
Bitwise and (&) : 0011&1011 = 0011
-
The bitwise or (|) : 0011 | 1011 = 1011
-
In reverse (~) : ~0011 = 1100
-
Bitwise xor: 0011 ^ 1011 = 1000
-
Equal to 0, different to 1; So xor can be remembered without carrying addition
-
Several features:
X ^ x = 0 c = a ^ b =>a ^ c = b, A ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c // associativeCopy the code
-
2. The bit operation at position (n)
Operations on specified bits are usually performed in conjunction with a shift operation (associated with n, where n is the rightmost digit).
-
Clear the rightmost n bit of x: x & (~0 << n)
-
Get the value of the NTH bit of x (0 or 1) :(x >> n) &1;
Principle: 1 & other values = Other values
-
X & (1 << (n-1))
-
Only for the position of the n 1: x | (1 < < n)
-
Only the NTH position is 0: x & (~ (1 << n))
-
X & ((1 << n) -1)
Note: the leftmost bit is the highest bit and the rightmost bit is the lowest bit
-
X & (~((1 << (n + 1)) -1))
3. Practical points of bit operation
First of all, the bitwise operators can be used in either binary or decimal form; Because bitwise operators also operate after converting from decimal to binary
- Judge parity
- X % 2 == 1 —–> (x & 1) == 1; It’s odd if the last bit is equal to 1
- x %2 == 0 ——> (x & 1) == 0
- Multiplication/division 2
- X /= 2 —–> x >>= 1; Actually the bottom layer of the compiler is optimized for bitwise operations
- mid = (left + right) / 2 ——> mid = (left + right) >> 1
- X and x
- x & -x = 1
- x & ~x = 0
- N & (n-1) == 0
At the end of the article, put a reference link…