Preparing for the Blue Bridge Cup -- bit operation

Catalog

What is bit operation

An operator

And operation &

Or operations |

Exclusive or operation ^

Reverse operation ~

Left shift operation   <<

Right shift operation >>

priority

Example

371. Sum of two integers

  The finger of the sword Offer 64. seek 1+2+…+n​

link

---

What is bit operation

All the numbers in the program are stored in the computer memory in binary form . Bit operation is to operate the binary bit of integer in memory directly , Bit operation is very efficient , Try to use bit operation in the program , This will greatly improve the performance of the program .

An operator

         And operation &

and Operations are usually used for binary bit operations , For example, a number & 1 The result is to take the last bit of the binary . This can be used to determine the parity of an integer , The last bit of binary is 0 Indicates that the number is even , The last is 1 Indicates that the number is odd .

Two numbers with the same digit All for 1, Then for 1; If you have any One is not for 1, Then for 0.

00101 & 11100=00100

         Or operations |

or Operations are usually used for unconditional assignments on binary specific positions , For example, a number | 1 The result is to force the last bit of the binary into 1. If you need to change the last bit of the binary to 0, For this number | 1 After that, just subtract one , Its practical significance is to force this number to the nearest even number .

Same bit as long as One for 1 That is to say 1.

00101 | 11100=11101

          Exclusive or operation ^

The sign of XOR is ^. Bitwise exclusive or operation , Perform a logical bitwise XOR operation on each bit of the bitwise or binary number of the equal length binary pattern , The result of the operation is that if a bit is different, the bit is 1, Otherwise, this bit is 0.

In a nutshell Same as 0, Different for 1.

00101 ^ 11100=11001

         Reverse operation ~

The definition of negation operation is to take 0 and 1 All reversed .

~ 00101=11010

         Left shift operation   <<

a << b It means to put a Shift left after binary b position （ Add after b individual 0）. for example 100 The binary of is 1100100, and 110010000 To convert to decimal is 400, that 100 << 2 = 400. It can be seen that ,a << b The value of is actually a multiply 2 Of b Power , Because add a... After the binary number 0 It's equivalent to multiplying this number by 2.

It is commonly believed a << 1 Than a * 2 faster , Because the former is a lower level operation . So the program multiplies by 2 Please try to shift one bit to the left instead of .

         Right shift operation >>

and << be similar ,a >> b Indicates binary shift right b position （ Remove the end b position ）, amount to a Divide 2 Of b Power （ integer ）. The same example as above , that 4002 = 100

priority

Priority	Operator
1	~( According to the not )
2	<<（ Move left ） >>（ Move right ）
3	&（ Bitwise AND ）
4	^（ Bitwise XOR ）
5	|（ Press bit or ）

Example

        371. Sum of two integers

​

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            unsigned int c = (unsigned int)(a & b) << 1;
            a = a ^ b;
            b = c;
        }
        return a;
    }
};

          The finger of the sword Offer 64. seek 1+2+…+n

int quickMulti(int A, int B) {
    int ans = 0;
    for ( ; B; B >>= 1) {
        if (B & 1) {
            ans += A;
        }
        A <<= 1;
    }
    return ans;
}

link

Prepare for the Blue Bridge Cup ———— Operator ^

Prepare for the Blue Bridge Cup ———— The pointer

Prepare for the Blue Bridge Cup ———— Dichotomy search

Prepare for the Blue Bridge Cup ———— A collection of commonly used string functions

I am not talented , If there is a mistake , Welcome to the comments section . If it helps you, please give the thumbs-up , Collection , Focus on Oh ！

​

​

  One sentence per day

Efforts and gains , It's all my own , It has nothing to do with others . The greatest sense of achievement , Is always moving in the direction you want