Neglected technique: bit operation

Summary of basic operation knowledge of bit operation

1. Move left operation A<<B

take A Each bit of the binary representation of is shifted to the left B position , Cut off the excess bits on the left , The insufficient position on the right 0

A = 1100 B = 2
A << B = 110000

2. Move right A>>B,A>>>B
The right shift operation is divided into arithmetic right shift and logical right shift

Arithmetic right shift is a signed right shift , Logical right shift is an unsigned right shift .

Arithmetic shift right ： take A Each bit of the binary representation of is shifted to the right B position , The excess bits on the right are cut off , The number of sign bits filled by the insufficient bits on the left .

Logical shift right ： take A Each bit of the binary representation of is shifted to the right B position , The excess bits on the right are cut off , The insufficient space on the left makes up 0.

C Language ： Logical shift right only A >> B

Arithmetic shift right A >> B , Logical shift right A >>> B

A = 1111111111111111110000001
B = 2
A >> B = 1111111111111111111100000
A >>> B = 0011111111111111111100000

3. Press bit and operate A&B
take A and B Each bit of the binary representation of , Only two corresponding bits are 1 when , The result is 1, Otherwise 0.

A = 001010
B = 101100
A & B = 001000

4. To press or operate A|B
take A and B Each bit of the binary representation of a , As long as one of the two corresponding binary bits is 1, The result bit is 1, Otherwise 0.

A = 001010
B = 101100
A | B = 101110

5. Bitwise non operation ~A
take A The binary representation of each bit negates , If the corresponding binary bit is 0, The result bit is 1, Otherwise 0.

A =01010
~A = 10101

6. Operate by bitwise exclusive or A^B
take A and B Each bit of the binary representation of the , If the corresponding bits are different , The result bit is 1, Otherwise 0.

A = 001010
B = 101100
A ^ B = 100110

Summary of topics related to bit operation ：

1.1Single Number/Single Number II
In an array, except one number appears once , The rest of the numbers appear twice , Find the number that only appears once .
C The language code ：

int number(vector<int> &num)
{
    
	int result=0;
	for(int a:num)
	{
    
		result^a;
	}
	return result;
}

explain ： Exclusive or operation ：
1.a ^ a=0
2.a ^ 0=a
3.a ^ b ^ a=b ( A number exclusive or the same number can be restored twice )
If only one number appears once in an array , According to the above 1 and 2 You know , The XOR result of two identical numbers is 0, Then the number XOR appearing twice in the array is 0, There is only one occurrence left .

1.2 In a set of numbers , There is a number that appears only once , The rest of them came out three times , Find the number that only appears once .
The solution is similar to the above problem

2. The binary form of a decimal number 1 The number of
And operation

Use and operation 0&1=0, Continue to convert a non-zero number into a binary form 1 in 0

int get_one_num(int n){
    
    int res = 0;
    while(n){
    
       n = n&(n-1);
       res++;
    }
    return res;
}

3. Judge whether a number is 2 The power of , such as 1=2^0, 2=2^1, 4=2^2
And operation
Utilization and operation ,2&1=0,4&3=0,2 The binary form of the power of must be that the first digit is 1, For the other 0, And its minus one form must be that this one is 0, For the other 1.
for example ：8 The binary of is 1000 and 7 The binary of is 111,4 The binary of is 100,3 The binary of is 11

boolean istwores(int n){
    
     return n&(n-1)==0?True:False;
}

4. Because bit operations are faster than multiplication , So we can x = x * 2 Optimize to x = x << 1.
x=x/2 Optimize to x=x>>1, Improved computing speed

5、 Judge the two numbers entered m、n How many bits are different in the binary bits of , First m and n Do bitwise XOR , Set the different parts of the binary representation of the two to 1, Same partial setting 0, Get a number diff, Then count diff How many bits are there in the binary representation of 1.

int differences(int m, int n)
{
    
    int diff = m ^ n;
    int count = 0;
    while(diff)
    {
    
        diff = diff & (diff - 1);
        count++;
    }
    return count;
}

6. No new variables , Exchange the values of two variables
Based on XOR operation

a=a^b;

b=a^b;

a=a^b;

for example ： a=4( Binary is 100) b=3( Binary is 11)
a=a ^ b=4 ^ 3=7
b=a ^ b=7 ^ 3=4
a=a ^ b=7 ^ 4=3

summary
Question type of bit operation ：
1. Hexadecimal conversion
2. Binary 1 The number of
3. A statement determines whether an integer is 2 Integer power of
4. One number changes several digits to get another number ：
5. The number of occurrences of numbers in an array
6. Do not add, subtract, multiply or divide