@ the Author: Runsen

The essence of programming comes from algorithm, and the essence of algorithm comes from mathematics, programming is just to code mathematical problems. —- Runsen

According to my mental outline, now is the time to enter the gate of bitwise computing.

Bitwise operation, all the numbers in the computer are stored in binary, bitwise operation is the operation of binary bits

Bitwise and operation

The bitwise and operator is: &. First I declare a variable I equal to 11 and j equal to 2. Then we compute the bitwise and operation of I and j, which is 11&2, and get 2.

Where do the twos come from? Well, first we have to convert this 11 and this 2 into binary, and we see from the figure above that the binary of 11 is 0b1011, and the binary of 2 is 0b10. 0b this is just a binary identifier, which tells us that this is binary.

According to the bitwise “and” principle, if the corresponding position of both values is 1, that is, the upper and the lower values are 1, then the result is 1, and if one of them is not 1, then it is 0

1011The 0010-0010Copy the code

So, the bitwise “and” operations of 1011 and 0010 are 0010, and then we convert the binary 0010 to decimal, which is our result 2.

Operation by bit or

Next, we introduce the bitwise or operation. According to “or” arithmetic operator is: |. We also compute the bitwise “or” of 11 and 2, and the result is 11.

How exactly does this result 2 work? The binary of 11 is 1011, and the binary of 2 is 0010.

According to the principle of bit “or” operation, if one of the corresponding positions of two values is 1, the result is 1, i.e., if both values are 0, the result is 0

10110010 -1011
Copy the code

So, the bitwise “and” operations of 1011 and 0010 are 1011, and then we convert the binary 1011 to decimal, which is our result 11.

Bitwise xOR operation

Next, we introduce bitwise xOR operations. The bitwise xOR operator is: ^. We also compute the bitwise xOR of 11 and 2, and the result is 9.

How exactly does this result 9 work? The binary of 11 is 1011, and the binary of 2 is 0010.

The principle of bitwise xOR operation is that if the corresponding position of two values is the same 1, then the result is 0. That is, if both values are 0 or 1, the result is 0. Again, only 1 and 0, those results are 1

10110010 -1001
Copy the code

So, the bitwise xOR operations for 1011 and 0010 are 1001, and then converting the binary 1001 into decimal is our result, 9.

Inverse operation by bit

Next, we introduce bitwise inverse operations. The bitwise xOR operator is: ~. When we take the inverse of 11, we get -12.

How exactly does this result -12 work? The calculation result of the inverse of the bit is: ~n = -(n+1)

Therefore, the bitwise operation of 11 is reversed: ~11=-(11+1)=-12

Left shift operator

Next, we introduce the left-shift operator. The left-shift operator is: <<. We calculate the shift of 11 by 2 bits to the left, and the result is 44.

How exactly does this result 44 work? So if you move 2 to the left, you get 1011 and you move 2 to the left, and then you fill it up with 0’s, you get 101100. I’m going to move to the left here, but I’m going to drop two bits back here

1011
----
101
Copy the code

So, the operation of moving 1011 two bits to the right is 101100, and then converting 101100 from binary to decimal is our result 44.

Right shift operator

Next, we introduce the right shift operator. The right shift operator is: >>. We compute the shift of 11 by 2 to the right, and we get 2.

How exactly does this result 2 work? So if we move 2 to the right, that’s 1011 we move 2 to the right, and then the 11 on the right goes away, and it becomes 10. I’m moving to the right here, but I’m actually deleting digits.

1011
----
10
Copy the code

So, the operation of moving the sum of 1011 two bits to the left is 10, and then converting the binary 10 to decimal is our result 2. The table below is a summary.

symbol meaning The sample
~ Logical non operation ~a
& Logic and operations a&b
| Logic or operation. a|b
<< Bit shift to the left a<<2

| a | moves to the right operation a > > 2

Determine 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

So 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, as shown in Python:

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

To move one to the left is the same thing as multiplying by 2, to move one to the right is the same thing as dividing by 2

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

Binary lookup in Python looks like this:

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 returns None" "
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        if list[mid] == item:
            return mid
        elif list[mid] < item:
            low = mid + 1
        elif list[mid] > item:
            high = mid - 1
    return None
Copy the code

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

The following is a summary of common uses of bitwise operations

Find the odd and even values of x

x % 2= =1// The normal way is x &1= =1// true odd, false evenCopy the code

Calculate median

mid = (left + right) / 2Mid = (left + right) >>1/ / operationCopy the code

LeetCode 78: Subset

Now, let’s look at a problem with binary Leetcode. Given an array of integers with no repeating elements, return all possible subsets (power sets) of nums

Given an array of integers with no repeating elements, nums returns all possible subsets (power sets) of the array.
Note: The solution set cannot contain duplicate subsets.
# sample:
Nums = [1,2,3]
# output:
# [
# [3].
# [1].
# [2].
# [1, 2, 3].
# [1, 3].
# [2, 3].
# [1, 2].
# []
#] 
# Related Topics bit operator array backtracking algorithm
Copy the code

And since we’re dealing with all subsets, we can start with the characteristics of subsets. If the length of the integer array is 3, then there are 8 subsets. The length of the integer array is 4, so there are 16 subsets.

The number of elements in a subset of n is 2n2 to the n2n, which is a set problem in high school math.

This is a very clever use of bits in binary. Using bitwise operations, find a subset of [1,2,3] for each digit with a 1 indicating that this digit exists. We can use 0 and 1 to represent presence and absence. For example, if you code 001, you only have 3, and if you code 101, you have 1,3. The code 111 stands for 1,2,3.

Because each number can only be selected or not selected, the specific situation is as follows.

Specific Python code.

class Solution:
    def subsets(self, nums: List[int]) - >List[List[int]] :
        ret = []
        n = len(nums)
        Walk through all the states
        1 to the left of n is equal to 2 to the n, which can also be written as 2**n
        for s in range(1 << n):
            cur = []
            Find out if each bit is a 0 or a 1
            for i in range(n):
                # Determine whether the state of s is 0 or 1 in the ith bit, 2 to the I power
                if s & (1 << i):
                    cur.append(nums[i])
            ret.append(cur[:])
        return ret
Copy the code

In fact, bit operation is simple and very simple, but sometimes I can’t think of how to use it, mainly because there are many strange things.

In this case, another approach is the backtracking algorithm, noting that empty sets need to be added.

class Solution:
    def subsets(self, nums: List[int]) - >List[List[int]] :
        res = [[]]
        for i in nums:
            res = res + [[i] + num for num in res]
        return res
Copy the code

GitHub, portal ~, GitHub, portal ~, GitHub, Portal ~