Bitwise operations are a common part of programming, but there are still a lot of developers who don’t understand bitwise operations, which can lead to “cold feet” when it comes to bitwise operations. In fact, bit operation is not so complicated, as long as we understand the operation basis and the operation rules of the operator, we can master the knowledge of bit operation. Next, let’s learn about bit operations.

The number in the program exists in the form of binary in the computer memory, and the bit operation is to operate directly on the binary bits corresponding to the integer in the memory.

Note: this article deals only with integer operations, not decimal operations

The basis of bit operations

We use the decimal representation of numbers such as 3 and 5, while the basis of bit operations is binary. That is, humans use the decimal system, and machines use the binary system. To understand the bit operation, we need to understand the conversion method and corresponding relationship between the decimal system and the binary system.

binary

When converting from decimal to binary, adopt the method of “mod 2 and reverse order” :

  1. Divide a decimal number by 2 to get the quotient and remainder.
  2. Divisible by 2, the new quotient and remainder are obtained.
  3. Repeat steps 1 and 2 until the quotient is 0;
  4. The remainder obtained first is regarded as the high order of the binary number, and the remainder obtained later is regarded as the low order of the binary number.

The sorting result is the binary representation of the decimal number. For example, the calculation process for converting the decimal number 101 to binary is as follows:

101%2 = 50 + 1 50% 2 = 25 + 0 25% 2 = 12 + 1 12% 2 = 6 + 0 6% 2 = 3 + 0 3% 2 = 1 + 1 1% 2 = 0 + 1Copy the code

The reverse order is the order from the highest binary to the lowest binary, resulting in a 7-bit binary number of 1100101. If you want to convert to 8-bit binary number, you need to fill in the highest bit of 0. That is, the 8-bit binary number of the decimal number is 01100101.

The complete process is shown in the figure below:

Some netizens have sorted out the common base and ASCII code comparison table, the contents of the table are as follows:

ASCII control character

ASCII displayable characters

complement

We now know how to convert binary to decimal and have a base table. But before we start learning about bitwise operators, we need to know more about complement.

There are positive and negative values, so how do you represent positive and negative values in binary with only 0 and 1?

The highest bit in binary was set to be 0 for positive and 1 for negative. For example, 0000 1100 corresponds to 12, while 1000 1100 corresponds to -12. This representation is called source code. But the new problem is that the top bit of the binary is always 0, but there is an extra 1 in order to represent positive and negative, and it will make an error when performing the operation. For example, the binary operation of 1 + (-2) is as follows:

0000 0001 + 1000 0010 
= 1000 0011
= -3 
Copy the code

This is obviously problematic, and the problem is that this is the highest digit. Then came inverse codes (zeros and ones interchangeably, for example, 1111 0011 for 0000 1100). At this point, the operation looks like this:

0000 0001 + 1111 1101
= 1111 1110
We need to reverse the code again before converting to decimal
= 1000 0001 
= -1
Copy the code

I think I got it right this time. But it still has exceptions. Let’s look at 1 + (-1) :

0000 0001 + 1111 + 1110
= 1111 1111
= 1000 0000
= -0
Copy the code

Zero is not positive or negative. To solve this problem, the concept of complement was developed. The complement is to make negative numbers into positive numbers that can be added, so the complement of negative numbers = the absolute value of negative numbers is negative + 1. For example, the complement of -1 is:

The absolute value of -1 = 0000 0001# 1 binary source code= 1111, 1110# change the source code= 1111, 1111# plus 1 gives me my complement
Copy the code

The complete process of -1 complement derivation is shown in the figure below:

Conversely, the derivation of the original code from the complement code is the original code = complement -1, and then inverse. It should be noted that in the process of inverse coding, the value of the highest bit is unchanged, so as to ensure that the positive and negative results will not be wrong. For example, the operations of 1 + (-6) and 1 + (-9) are as follows:

The complement of # 1 plus the complement of minus 6
0000 0001 + 1111 1010
= 1111 1011 The result of the complement operation= 1111, 1010Subtract 1 from the complement to get the inverse= 1000, 0101# get the original code= 5# Corresponding decimal
Copy the code
The complement of # 1 plus the complement of minus 9
0000 0001 + 1111 0111
= 1111 1000 The result of the complement operation= 1111, 0111Subtract 1 from the complement to get the inverse= 1000, 1000# get the original code8 = -# Corresponding decimal
Copy the code

Note that the complement of a positive number is the same as the original and requires no additional operations. In other words, the appearance of complement is to solve the sign problem of negative number operation.

Life is short and I use Python.

Cui Qingcai | static find invite you attention WeChat public number: to advance the Coder

Operator introduction

Bit operations fall into six categories, which are:

The name of the symbol
Bitwise and &
Bitwise or |
The bitwise exclusive or ^
According to the not ~
Left shift operation <<
Moves to the right operation >>

Bitwise and

The bitwise and operation matches the corresponding binary bits of the two numbers involved in the operation. If the corresponding binary bits are both 1, the result bit is 1; otherwise, the result bit is 0. The bitwise and operator is &, and the complement of the operation appears. For example, the bitwise and operation of the digits 5 and 8 is actually the bitwise and operation of the binary 0000 0101 corresponding to the digit 5 and the binary 0000 1000 corresponding to the digit 8, namely:

0000 0101
&
0000 1000
Copy the code

According to the bitwise and rule, the numbers of each position are compared. The operation process is as follows:

0000 0101&0000 1000 ---- ---- 0000 0000Copy the code

Since there is no “1” in their corresponding positions, the result is 0000 0000. The complete process of bitwise and operation of numbers 5 and 8 is shown below:

If you convert the result to decimal, you get 0, which is 5&8 = 0.

Bitwise or

The bitwise or operation is the binary phase or corresponding to the two numbers involved in the operation, and the result bit is 1 as long as there is 1 in the corresponding binary bit, otherwise the result bit is 0. Bitwise or arithmetic operators for |, participate in the operation of complement. For example, the bitwise or operation of the numbers 3 and 7 is actually the bitwise or operation of the binary 0000 0011 corresponding to the number 3 and the binary 0000 0111 corresponding to the number 7, namely:

0000 0011
|
0000 0111
Copy the code

According to the bitwise or rule, the numbers in each position are compared. The operation process is as follows:

0000 | 0011 0000 0111-0000-0111Copy the code

The final result is 0000 0111. The results converted to decimal, get 7, namely 3 | 7 = 7.

The bitwise exclusive or

A bitwise xor operation causes the binary bits of the two numbers involved in the operation to be xor. If the corresponding binary bits are different, the result bit is 1; otherwise, the result bit is 0. The bitwise xor operator is ^, and the complement of the operation appears. For example, the bitwise xOR operation of the numbers 12 and 7 is actually the bitwise xOR operation of the binary 0000 1100 corresponding to the number 12 and the binary 0000 0111 corresponding to the number 7, i.e. :

0000 1100
^
0000 0111
Copy the code

The numbers in each position are compared according to the bitwise xOR rule. The operation process is as follows:

0000 1100
^
0000 0111
---- ----
0000 1011
Copy the code

The final result is 0000 1011. If you convert the result to decimal, you get 11, which is 12^7 = 11.

According to the not

The bitwise inverse operation replaces the 0 above each bit of the binary number with a 1, and the 1 with a 0. The bitwise inverse operator is ~, and the complement mode of the operation appears. For example, the bitwise inverse operation of the number 9 is actually the bitwise inverse operation of the binary number 9, 0000 1001, i.e. :

~ 0000 1001 = 0000 1001# complement, positive complement is the original code= 1111, 1010# the not= 10Copy the code

So you get minus 10. For another example, the reverse of -20 is as follows:

~ 0001 0100 = 1110 1100# complement= 0001, 0011# the not
= 19
Copy the code

The final result is 19. We see the pattern in the example, and the inverse bitwise results are expressed mathematically:


We can apply this to 9 and -20:

~ 9 = -(9 + 1) = -10 ~(-20) = -((-20) + 1) = 19Copy the code

This rule also applies to the number 0, i.e. ~0 = -(0 + 1) = -1.

Left shift operation

The left shift operation moves all the corresponding binary digits to the left by several bits, discarding the high ones and adding 0 to the low ones. The left-shift operator is <<. For example, to move the number 5 4 bits to the left is to move the binary number 5 in binary 0000 0101 4 bits to the left:

5 << 4
= 0000 0101 << 4
= 0101 0000 Discard the high value and fill the low value with 0
= 80
Copy the code

The complete operation process of moving the number 5 4 bits to the left is shown as follows:

The final result is 80. This is equivalent to:


In other words, the law of left shift operation is:


Moves to the right operation

The right shift operation moves all the corresponding binary digits of a number several bits to the right. For the left void, 0 is added if it is positive, and negative numbers may be added either 0 or 1 (Turbo C and many compilers opt for 1). The right shift operator is >>. For example, to move the number 80 four bits to the right is to move the binary number 80 in binary 0101 0000 four bits to the right, i.e. :

80 >> 4
= 0101 0000 >> 4
= 0000 0101 Positive numbers complement 0, negative numbers complement 1
= 5
Copy the code

The final result is 5. This is equivalent to:


In other words, the rule of right shift operation is:


Notice that if it’s not divisible, you take an integer. The rules for rounding division are similar to floor division in PYTHON.

I use Rust

WeiShiDong | quinn asked you to focus on WeChat public number: Rust of zen

Application of bit operation

Now that we know about bit operations, we can try it out in development. There has always been a rumor that bit operation is efficient and fast, but it has never been proved in literature, so this paper will not discuss the efficiency and speed. If you are reading this article and you have relevant literature, please leave a message to inform, thank you.

Judge the numbers even and odd

In general, we know whether a number is odd or even by taking mod. For example, the way to determine the parity of 101 is as follows:

# python
if 101 % 2:
	print('even number')
else:
	print('odd')
Copy the code

We can also implement parity by bitwise and in bitwise operations, for example:

# python
if 101 & 1:
	print('odd')
else:
	print('even number')
Copy the code

This is because the least significant binary of an odd number is always 1, while the least significant binary of an even number is always 0. So, any odd number with 1 which is 0000, 0001 is going to be 1, and any even number with 1 is going to be 0.

Variable exchange

In C, the exchange of two variables must be implemented through a third variable. The pseudocode is as follows:

# pseudocode
a = 3, b = 5
c = a
a = b
b = a
--------
a = 5, b = 3
Copy the code

In PYTHON, it’s not that much of a hassle and can be swapped directly. The corresponding PYTHON code is as follows:

# python
a, b = 3.5
a, b = b, a
print(a, b)
Copy the code

The code runs as 5, 3. Most programming languages do not support PYTHON, in which case we can swap variables by bitwise xor in bitwise operations. The corresponding pseudocode is as follows:

# pseudocode
a = 3, b = 5
a = a ^ b
b = a ^ b
a = a ^ b
Copy the code

And then finally, a is equal to 5, b is equal to 3. We can use C language and PYTHON language to verify, the corresponding PYTHON code is as follows:

# python
a, b = 3.5
a = a ^ b
b = a ^ b
a = a ^ b
print(a, b)
Copy the code

The code run result is 5 3, indicating that the variable exchange is successful. The corresponding C code is as follows:

#include<stdio.h>
void main(a)
{
    int a = 3, b = 5;
    printf("A =%d, b=%d\n",a,b);
    a = a^b;
    b = a^b;
    a = a^b;
    printf("A =%d, b=%d\n",a, b);           
} 
Copy the code

The code results are as follows:

Before exchange: A =3, b=5 After exchange: A =5, b=3Copy the code

This indicates that the exchange of variables was successful.

Take x times 2 to the n

Take a number x and multiply x with 2 to the NTH power. It’s all very simple mathematically:


In bitwise operations, all you need to do is use the left shift operation, x << n.

Take the KTH bit of x

That is, take the binary value of the KTH bit of the binary corresponding to the number x. Assuming that the number is 5 and the corresponding binary is 0000 0101, the operation of the k-th binary value is x >> k & 1. We can verify this with PYTHON code:

# python
x = 5  # 0000, 0101,
for i in range(8):
	print(x >> i & 1)
Copy the code

The code results are as follows:

1 0 1 0 0 0 0 0 0Copy the code

This shows that the algorithm of bit operation is correct and can meet our needs.

Determine the assignment

if a == x:
    x = b
else:
    x = a
Copy the code

It’s the same thing as x is equal to a to the b to the x. We can verify this with PYTHON code:

# python
a, b, x = 6.9.6
if a == x:
    x = b
else:
    x = a
print(a, b, x)
Copy the code

The code runs as 699, and its equivalent is as follows:

# python
a, b, x = 6.9.6
x = a ^ b ^ x
print(a, b, x)
Copy the code

This eliminates the if else statement.

Instead of floor removal

Binary search is one of the most commonly used algorithms, but it has a certain prerequisite: the object of binary search must adopt the sequential storage structure, and the elements are arranged in order. Such as ordered lists in PYTHON. The optimal complexity of binary search is O(1) and the worst time complexity is O(log n). For example, suppose we need to find the subscript of the specified element from the list [1, 3, 5, 6, 7, 8, 12, 22, 23, 43, 65, 76, 90, 543]. The corresponding PYTHON code looks like this:

# python
def search(lis: list, x: int) -> int:
    """ Non-recursive binary lookup returns the index of the specified element in the list -1 means it does not exist ""
    mix_index = 0
    max_index = len(lis) - 1
    while mix_index <= max_index:
        midpoint = (mix_index + max_index) // 2
        if lis[midpoint] < x:
            mix_index = mix_index + 1
        elif lis[midpoint] > x:
            max_index = max_index - 1
        else:
            return midpoint
    return - 1


lists = [1.3.5.6.7.8.12.22.23.43.65.76.90.543]
res = search(lists, 76)
print(res)
Copy the code

Midpoint = (mix_index + max_index) // 2 We can replace it with midpoint = (mix_index + max_index) >> 1 to get the same result. That’s because moving 1 to the left is the same thing as multiplying by 2, and moving 1 to the right is the same thing as dividing by 2. There are many more such cases, which will not be repeated here.

At this point, we have a certain understanding of bitwise operations, hope you use bitwise operations in your work. For more Saoperation and knowledge, please scan the qr code below.