Computation is closely related to programming. Every program we write may have addition, subtraction, multiplication and division, but of course this is the most basic operation. I learned my first programming language C as a freshman, along with mod (%) and trinary operators (? :), I thought (? 🙂 awesome, but I rarely use it in programming because the if and else are already in my head.

There are also some deviations from the operators in different languages. For example, the Python divisor (//) is not available in C, and the C trinary operator has different representations in Python, such as np.where and if and else.

The following is a bit operator that I think is superior. It is superior partly because bit operations are very convenient to solve certain problems, and partly because it can be ZhuangBi. If you haven’t been exposed to bitwise, even a small amount of bitwise code can be confusing, and once you do, it’s really neat.

We know that all numbers, including letters and symbols, are stored in binary form in the computer, and bit operation is to operate on binary directly. Common bit operations include the following:

  • The bitwise and: &
  • Bitwise or: |
  • Bitwise xor :^
  • Left: < <
  • Moves to the right: > >
  • Invert: ~

These bit-operation symbols are sorted in order of priority as follows:

1 2 3 4 5
~ < <, > > & ^ Bitwise or

For ease of understanding and viewing, only 8-bit binaries are listed in the following examples

The bitwise and (&)

The bitwise and algorithm can be summarized as “if it is true, if it is false”. The operation between 0 and 1 has the following form:

  • 1 and 1 = 1
  • 1 & 0 = 0
  • 0, 0 = 0

For example, a bitwise and operation is used between the numbers 5 and 6. By matching each bit of the 8-bit binary form of the two arrays, a new number 4 can be obtained by applying the above rule, that is, 5 & 6 = 4.

Bitwise or (|)

The bitwise or bitwise algorithm can be summarized as “if it is true, if it is false, if it is true”. The operation between 0 and 1 has the following form:

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

Also with the Numbers 5 and 6, for example, using the same way do bitwise or operation between them, be able to get a new number 7, 5 | 6 = 7.

Bitwise xor (^)

The bitwise xOR algorithm can be summarized as “same is false, different is true”. The operation between 0 and 1 has the following form:

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

Again, the number 5 and the number 6 can be used in the same way as above to perform a bitwise foreign operation between the two, resulting in a new number 3, that is, 5 ^ 6 = 3.

Shift to the left (< <)

The left shift operation is to move the binary form of a number to the left as a whole, and then fill the virtual bit on the right with 0.

This example shows that 2<<2 = 8. You can see that 1 was originally in the second place on the right. If you move it two places to the left, the 1 will move to the fourth place on the right.

Moves to the right (> >)

The operation mode of right shift is the same as that of left shift, but the direction is opposite. See the following figure for the specific movement:

This example is the embodiment of 6>>2 = 1, just need to move the whole thing to the right two, and then the left imaginary 0, do not need to worry about whether 1 will be covered.

These two symbols are a little confusing, so here’s a little tip of your own: the arrow goes where it goes, the left goes up, the left goes down.

Invert (~)

The inverse is easier, just remember this little formula: ~x = -(x+1), for example, the inverse of the number 5 is equal to -6, that is, ~5 = -(5+1) = -6.

Has introduced over the six bits of binary operators is how to operate, but simple introduction does not stand out operations on the tall, the use of bit operations skills to solve some problems, these problems are not difficult, but we can meet in place of operation is convenient, and deepen the impression para arithmetic operations.

Swap two numbers

For this problem, we may think of the first method is to use the third variable to help exchange, for example, if you want to exchange the values of a and B variables, you need to define a temporary variable temp assist.

a = 1; b =2
temp = 0
temp = a; a = b; b = temp
Copy the code

This requires extra storage, so is there a way to swap the values of a and B just in place? Bit operations do it, and it’s really easy.

a = a^b # (1)
b = a^b # (2)
a = a^b # (3)
Copy the code

If you’re new to bitwise operations, these three lines of code are pretty confusing. There are a few other properties you need to know about bitwise xOR:

  • 1. Bitwise xor satisfies the commutative law, i.e. a ^ b = b ^ a
  • (a^b)^c=a^(b^c)
  • 3. Any number equal to 0 or is equal to itself, such as a ^ 0 = a.

If the formula (1) is substituted into the formula (2), the formula (2) can be changed into the following form by using the above properties and combining with the principle of bitwise exclusivity or “the same is false” :

b = a^b^b = a^0 = a
Copy the code

In this way, a is assigned to B, and if we substitute the formula (2) into formula (3), formula (3) becomes:

a = a^a^b = 0^b = b
Copy the code

So we’ve done the transposition between the variables A and B, and if you already have a NiuBi feel, let’s move on to the next one.

A power of 2

Given a number, you need to determine whether it is a power of two and return true if it is, and false if it is not.

This problem is also a good use of the loop method, set a loop condition, and then let the input integer n always divided by 2, and finally only need to determine whether n is equal to 1, because n==1 is only satisfied when n is a power of 2.

while n>1:
    n/=2
return n==1
Copy the code

This method should be a very common method, do not reflect their forced case how to do? Let’s see what we can do with bits.

return n > 0 and n & (n - 1) = =0
Copy the code

If n is a power of 2, it should be 1 at the top and 0 at the rest, such as 1000 at 8. For n-1, all but the highest bits are 1, so for example, 7 is 0111, so n&(n-1)=0.

Looking for different

Given a string s1 that contains only lowercase letters, s2 scrambles S1 and inserts a new lowercase letter into it, expecting you to pick out the new letter. For example, s1 = ‘ABC ‘,s2 = ‘badc’, output D.

The first idea is to use a hash table to count and store the number of occurrences of each element. Each occurrence is a new element added, and using a hash table means space for a new dictionary. By using bitwise xor operation, only a third variable can be introduced to solve this problem, using the xor properties 1 and 3 mentioned above, and the “same is false” rule.

m = s1+s2
first = 0
for i in range(0,len(m)):
    first ^= ord(m[i])
return chr(first)
Copy the code

In this case, ORD converts a letter to the corresponding Ascii code, and CHR converts an Ascii number to the corresponding alphabetic form.

Flipped binary

For example, if the input binary is 000100111, the output binary is 11001000.

Integer flipping works fine with strings, but binary is different from integers because there are lots of zeros in binary, and some of them might get erased after flipping and converting. Here you can use the bit operation to achieve binary flipping, the specific code is as follows:

res = 0
for i in range(8):
    res <<= 1
    res += n & 1
    n >>= 1
return bin(res)
Copy the code

Here, using bitwise and the “true if true, false if false” rule, we compare the last bit of the input binary with 1 each time, adding the result to res, and then moving n one bit to the right, since the last bit has already been compared.

Be careful to move the res one bit to the left at the beginning of each iteration, because whether n&1 yields a 0 or a 1, it makes sense in binary, and you need to provide a space for the number you’re going to get, so you can’t omit it. Here is the recommendation of their own hand push, it is easy to understand.

Parity of 1 number

Given an 8-bit binary, calculate the parity of 1 of the 8 digits. If 1 of the 8 digits is odd, return 1. If 1 is an even number, 0 is returned. For example, 00110111, there are five ones in it, so it should return one.

If it is true, if it is true, if it is false, if it is not true, then it is false. If it is true, if it is true, then it is false. If it is true, then it is true.

count = 0
for i in range(8):
    count += n & 1
    n >>= 1
return count & 1
Copy the code

But that’s not the NiuBi part of bit arithmetic. The following method is really strong, but probably not as readable as the above method.

n = n^(n>>1)
n = n^(n>>2)
n = n^(n>>4)
return n & 1
Copy the code

Use 00110111 as an example, perform xor operation between n and n>>1 to get a new binary, as follows:

The meaning of 0 in the new binary means that this position shares an even number of 1’s with the previous position and 1 means that this position shares an odd number of 1’s with the previous position. For example, the 6th digit of New indicates that the 5th and 6th digit of Num1 have an odd number of 1s. It can be seen that the corresponding position of Num1 is 01. Similarly, other positions have the same property.

Similarly mobile two indicates the position and the parity of the number of the first three position 1, four said the mobile location and the parity of the number seven position 1 before, so when the mobile bottom after four Numbers is said in the 8 bit binary 1 parity, if the bottom is 1, represents has an odd number of 1, if the bottom is 0, represents has an even number of 1.

conclusion

Bit operation may be a lot of people know, but in the solution of the problem is rarely used, because there are a lot of easy to understand methods can replace bit operation, but the function of bit operation is very powerful, worth learning. Through the above examples, we can also find that bit operation is really convenient to solve some problems, but it is not readable to people who do not understand. At the same time, this is where bit operation can be ZhuangBi.

Follow the public account “milk Candy Cat” for the first time to get more wonderful articles