Task06: bit operation

1. Video title

1.1 A number that appears only once

1.1.1 describe

Given an array of non-empty integers , Except that an element only appears once , Each of the other elements occurs twice . Find the element that only appears once .

explain ：

Your algorithm should have linear time complexity . Can you do this without using extra space ？

Example 1:

Input : [2,2,1]
Output : 1

Example 2:

Input : [4,1,2,1,2]
Output : 4

1.1.2 Code

In fact, the intuitive problem-solving may still be based on the table , Create a new dictionary to store numbers and occurrences

First, traverse the original array to count the number of occurrences , Then traverse the dictionary to get the number that appears once

But this exercise is a bit operation , Operations using bit operations , It's also intuitive

The XOR result of a number itself is zero , Any number with zero exclusive or is itself

And XOR is an operation , Satisfy the law of exchange and the law of union , It's no longer proven here

That is, an XOR sequence , Will eliminate all even numbers

That is to say, there are only odd numbers left , In this topic is 1 Time

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        while nums:
            ans = ans^nums.pop()
            
        return ans

1.1.3 summary

A sequence of numbers with XOR operations , Will eliminate all even numbers , Keep odd numbers

1.2 A number that appears only once III

1.2.1 describe

Given an array of integers nums, There are exactly two elements that only appear once , All the other elements appear twice . Find the two elements that only appear once . You can press In any order Return to the answer .

Advanced ： Your algorithm should have linear time complexity . Can you just use constant space complexity to achieve ？

Example 1：

Input ：nums = [1,2,1,3,2,5]
Output ：[3,5]
explain ：[5, 3] It's also a valid answer .

Example 2：

Input ：nums = [-1,0]
Output ：[-1,0]

Example 3：

Input ：nums = [0,1]
Output ：[1,0]

Tips ：

2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
Except for two integers that appear only once ,nums The other numbers in appear twice

1.2.2 Code

The idea of intuitive problem-solving is still to make a table , Create a new dictionary to store numbers and occurrences

If you want to use bit operations , The idea may be a little more complicated

The first step is to continue the operation of the previous question , Exclusive or entire sequence

The final result , Is the exclusive or of two numbers that only appear once

Here we review the definition of XOR , If the corresponding bit is different, it is one , Is the difference

So now we get the difference between two numbers that only appear once

So we can divide two numbers into two sets of XOR sequences according to this difference

As for other figures , Every two identical ones will be divided into the same sequence and eliminated

So the final result of these two XOR sequences is two numbers that only appear once

Another thing to note is how to design a check number to separate the two numbers of the answer

We can use & operation , Make the XOR result of the first step & The opposite of itself , Take out the rightmost 1

At this time, the other positions of the verification number are 0, Only Far right 1 That one is 1

The next step is to use this check number to separate the two numbers of the answer into two sequences

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        ans = 0
        for i in nums:
            ans = ans^i
        #  Get the result of exclusive or of two elements that occur only once 
        ans = -ans & ans
        #  Take the rightmost bit of the XOR result 1, For verification 
        ans1 = ans2 = 0
        for i in nums:
            if i&ans==0 :
            #  If the check bits are different 
                ans1 ^= i
            else:
            #  If the check bits are the same 
                ans2 ^= i
        
        return [ans1,ans2]

1.2.3 summary

The definition of XOR is , If the corresponding bit is different, it is 1, Is the difference between the two

A number & The opposite of itself , The one taken out is the one on the far right 1

That is, the other positions of this result are 0, Only Far right 1 That one is 1

2. Assignment topic

2.1 2 The power of

2.1.1 describe

Give you an integer n, Please judge whether the integer is 2 Power square . If it is , return true ; otherwise , return false .

If there is an integer x bring n == 2x , Think n yes 2 Power square .

Example 1：

Input ：n = 1
Output ：true
explain ：20 = 1

Example 2：

Input ：n = 16
Output ：true
explain ：24 = 16

Example 3：

Input ：n = 3
Output ：false

Example 4：

Input ：n = 4
Output ：true

Example 5：

Input ：n = 5
Output ：false

Tips ：

$-2^{31}<=n<=2^{31}-1$

Advanced ： You can do without loops / Can recursion solve this problem ？

2.1.2 Code

Intuitively speaking, it is still loop or recursion , In numbers than n In small cases

Multiply by 2, Until equal or greater 2 Be big

But if, in terms of bit operations , Just refer to the summary of the previous question

A number & The opposite of itself , The one taken out is the one on the far right 1

So if a number is 2 The power of , Then only one is 1, That is, the rightmost 1

That is, a number & The opposite number of himself is equal to himself , by 2 The power of

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n==0:
            return False
        else:
            return (n & -n) == n

2.1.3 summary

A number & The opposite number of himself is equal to himself , Then the number is 2 The power of

2.2 A number that appears only once II

2.2.1 describe

Give you an array of integers nums , Except that one element only appears once Outside , Every other element just happens to appear Three times . Please find and return the element that only appears once .

Example 1：

Input ：nums = [2,2,3,2]
Output ：3

Example 2：

Input ：nums = [0,1,0,1,0,1,99]
Output ：99

Tips ：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums in , Except that one element only appears once Outside , Every other element just happens to appear Three times

Advanced ： Your algorithm should have linear time complexity . Can you do this without using extra space ？

2.2.2 Code

The more direct way is to make a table , Count the times , Then filter out the answers

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        freq = collections.Counter(nums)
        ans = [num for num, occ in freq.items() if occ == 1][0]
        return ans

If you use bit operations , It is necessary to treat these numbers as binary numbers , The following follows this premise

For each digit of this set of numbers , If and for 3 Multiple , The one who proves the answer is 0, Instead of 1

take [0,1,0,1,0,1,99] The integer array given in the question , Here, the last one is taken as an example to briefly explain

0 The last digit of 0, appear 3 Time ,1 The last digit of 1, Three times ,99 The last digit of 1, once

therefore , The sum of the last digit of this set of numbers , by 4, No 3 Integer multiple , the 3 The remainder of the remainder is 1

in other words , This number of the answer , The value in the last bit is 1; If the remainder is zero , Then this one of the answers is also 0

It should be noted that , If the language used is right 「 Signed integer type 」 and 「 Unsigned integer type 」 There is no distinction , Then you may get the wrong answer . This is because 「 Signed integer type 」（ namely int type ） Of the 31 Binary bits （ That is, the highest position ） Is a sign bit in the sense of complement , Corresponding $-2^{31}$ , and 「 Unsigned integer type 」 Because there is no symbol , The first 31 Two bits correspond to $2^{31}$ . So in some languages （ for example Python） It is necessary to make special judgment on the highest position in .

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            total = sum((num >> i) & 1 for num in nums)
            if total % 3:
                # Python  Special judgment is required for the highest position 
                if i == 31:
                    ans -= (1 << i)
                else:
                    ans |= (1 << i)
        return ans

2.2.3 summary

The main thing to note here is python It's an unsigned type , So there may be an error at the top ¹

above Python Code and the C# The code logic is exactly the same , But the submission times are wrong . The error message is as follows ：
 

 Input ：[-2,-2,1,1,-3,1,-3,-3,-4,-2]
 Output ：4294967292
 Expected results ：-4

 
We found that ：
 

-4  The complement is  1111 1111 1111 1111 1111 1111 1111 1100

 
If the sign bit is not considered
 

1111 1111 1111 1111 1111 1111 1111 1100 -> 4294967292 

 
Isn't it a hole ,C++,C#,Java The integer of such languages is limited in length , Such as ：byte 8 position ,int 32 position ,long 64 position , but Python The integer of is unlimited in length （ That is, there is no high-level overflow ）, therefore , When the output is negative , Will result in a positive number ！ Because it puts 32 Bit signed integers are considered unsigned , What a pit .
 
We modify the above code , Add judgment conditions if result > 2 ** 31-1
It means more than 32 The range of bit integers represents negative numbers result -= 2 ** 32, You can get the corresponding negative number .

There are more advanced methods , Time is limited , later ²、³、⁴

2.3 A subset of

2.3.1 describe

Give you an array of integers nums , Elements in an array Different from each other . Returns all possible subsets of the array （ Power set ）.

Solution set You can't Contains a subset of repetitions . You can press In any order Returns the solution set .

Example 1：

Input ：nums = [1,2,3]
Output ：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2：

Input ：nums = [0]
Output ：[[],[0]]

Tips ：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums All elements in Different from each other

2.3.2 Code

Finding subsets , That is to find out the different permutations and combinations of various elements

Suppose there is 5 Elements , We'll just use one 5 Bit binary number

Each bit of this binary number corresponds to each element ,1 Represents the collection ,0 On the contrary

So the case of all subsets , In fact, it is 0 To this $2^5$ All the figures represent the situation

Each number represents a possible subset of the integer array

class Solution:
    def subsets(self, nums):
        allset=2**len(nums)
        #  Find the number of bits of binary digits 
        result=[]
        #  Store a set of all subsets as a result 
        for i in range(allset):
        #  For each number , In each case 
            item=[]
            for j in range(len(nums)):
            #  Check whether each bit is 1
            #  To decide whether to put the element of this bit into this subset 
                if i&(2**j):
                    item.append(nums[j])
            result.append(item)
            #  Put this subset into the result 
        return result

2.3.3 summary

Each bit of this binary number corresponds to the state of each element ,1 Represents the collection ,0 On the contrary

That is, each number represents a subset of the situation , That is, which elements the subset contains

So the case of all subsets , In fact, it is 0 To this $2^{len(num)}$ All the figures represent the situation

---

1. Technical graphics ：Python Bit operation pit Prevention Guide ︎

2. 137. A number that appears only once II（ Finite state automata + An operation , Clear illustration ）︎

3. Leetcode 137： A number that appears only once II（ The most detailed solution ！！！）︎

4. 【LeetCode】 There is only one digital series problem （I、II、III）︎