Bit operation performance we must be clear, efficiency is absolutely high. I believe that the love of source code students, in the process of learning to read the source code will find a lot of source code using bit operations. But why aren’t they used in real programming? Perhaps the biggest reason is that it is difficult to understand. However, during the interview process, writing a bit or two of code while writing by hand will still impress the interviewer.

An operation commonly used operators including & (bitwise and), | (bitwise or), ~ (non), ^ (the bitwise xor), < < (symbol left shift), > > (signed right shift).

Here are a few examples to illustrate its application, hoping to inspire you.

1. Decide whether odd or even

And the way we usually figure out whether odd or even is to divide by 2 and see if the remainder is 0.

The Python code is as follows:

def isodd(x):
 return True if (x % 2 <> 0) else False
Copy the code

How do you use bitwise operations?

We just use ampersand, ampersand with 1, if it’s 1, then it’s odd; If 0, then the number is even, and the Python code looks like this:

def isodd(x):
 return True if (x & 1) else False
Copy the code

2. Moving one place to the left is the same as multiplying by 2, and moving one place to the right is the same as dividing by 2

One of the common problems encountered during the interview process is writing binary lookup code.

Binary search code is as follows:

def binary_search(list, item):
 ' '':param list: ordered list: param item: the element to look for :return: index of item in list, if not in list return None'' '
 low = 0
 high = len(list) - 1
 while low <= high:
 midpoint = (low + high) // 2
 if list[midpoint] == item:
 return midpoint
 elif list[midpoint] < item:
 low = midpoint + 1
 elif list[midpoint] > item:
 high = midpoint - 1
 return None
Copy the code

Midpoint = (low + high) >> 1 midpoint = (low + high) >> 1

3. Swap the two values

The code for numeric exchange is familiar to everyone, since it seems to have been used since the beginning of learning a programming language:

temp = b
b = a
a = temp
Copy the code

But how do you use bitwise operations to do this?

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

It’s a little hard to understand. What’s the mechanism?

The first line, a = a ^ b, is easy to understand;

The second row, b = b ^ a = b ^ a ^ b, and since b ^ b = 0, b = a ^ 0, b = a;

The third line, a = a ^ b, and since a was reassigned in the first step, a = a ^ b ^ a = b, completes the swap.

Here, the characteristics of xOR operation are summarized: the xOR result of any number and itself is 0; Zero and any number xor is itself.

4. Look for uniqueness in the data list

There is a list of data (2N+1 integers) in which only one number occurs once and the other N numbers occur twice. How do I find this unique data?

So the first algorithm that comes to mind is counting, creating a list, looping through the data and counting, and then iterating through the list to find the number of occurrences of 1.

In this case, the space complexity is ORDER N.

How do you reduce space complexity?

Notice the xOR property that we just talked about: any number and itself xor result in 0; Zero and any number xor is itself.

So, the xOR of N that occurs twice is 0, and the xor of N that occurs once is that number. That is, the way to find this unique data is to perform xOR operations on all the data, reducing the space complexity to O (1).

Calculate how many 1’s there are in a binary number

And I think with that foundation, you can easily implement this algorithm. It’s just a bit operation, you do and with 1, see if it’s 1, and then you move it one bit to the right, and you keep checking. The Python code is as follows:

def number1Bit(x):
 count = 0
 while x:
 count = count + (x&1)
 x = x >> 1
 return count
Copy the code

One problem with this is that if you have consecutive zeros, you have to do multiple shifts. Is there an easy way to skip consecutive zeros?

That’s by ampersand with x minus 1. This might not be easy to understand, but let me give you an example

x 1110 0000
x - 1 1101 1111
x&(x-1) 1100 0000
Copy the code

And that way, it will detect the last one.

The Python code is as follows:

def number1Bit(x):
 count = 0
 while x:
 count = count + 1
 x = x & (x-1)
 return count
Copy the code

Conclusion:

1, and operation is usually used to obtain the value of a certain bit is 1 or 0 (such as judging odd or even numbers, the number of 1 in the statistical value);

2, left move right move characteristics: left move one is equivalent to multiplying by 2, right move one is equivalent to dividing by 2;

3, xor characteristic: any number and its xor result is 0; Zero and any number xor is itself.

What do you want to say, welcome to leave a message! More Python tutorials will be updated regularly!