Leetcode question brushing 06 bit operation

An operation

Basic knowledge of

Original code 、 Inverse and complement

Binary has three different representations ： Original code 、 Inverse and complement , Internal use of the computer Complement code To express

Original code ： Is its binary representation ,（ The first bit is the sign bit ）

Inverse code ： The inverse of a positive number is the original code , The inverse of a negative number is a sign bit invariant , The rest of the bits are reversed .

Complement code ： The complement of a positive number is the original code , The complement of a negative number is the inverse +1

Sign bit ： The highest bit is the sign bit ,0 It means a positive number ,1 A negative number , In the bit operation, the sign bit also participates in the bit operation

Bit operations

1. Bitwise non operation

Every bit of the binary of an integer is reversed （0 become 1,1 become 0）

00 00 01 01 -> 5
~
11 11 10 10 -> -6  ( The inverse code is 11 11 10 01,  The original code is 10 00 01 10, So it is -6) 

2. Press bit and operate

Only the two corresponding bits in binary are 1 Only then 1

00 00 01 01 -> 5
&
00 00 01 10 -> 6
---
00 00 01 00 -> 4

3. To press or operate

There is a corresponding bit in the binary system 1 for 1, All for 0 The result is 0

00 00 01 01 -> 5
|
00 00 01 10 -> 6
---
00 00 01 11 -> 7

4. Operate by bitwise exclusive or

Only the corresponding bit is different, and the result is 1, Otherwise 0

00 00 01 01 -> 5
^
00 00 01 10 -> 6
---
00 00 00 11 -> 3

XOR operation satisfies commutative law and associative law , namely ：

A^B = B^A

A^BC = A^(BC)

A^A = 0

A^0 = A

A^BA = A^AB = 0^B = B

5. Shift left by bit operation

num << i take num The binary representation of moves to the left i position , The right to repair 0 Get the value of the , Move left 1 Bits represent the doubling of decimal values .

00 00 10 11 -> 11
11 << 3
01 01 10 00 -> 88

6. Shift right by bit operation

num >> i take num The binary representation of moves to the right i Bit

00 00 10 11 -> 11
11 >> 3
00 00 00 10 -> 2

title

A number that appears only once

1. Title Description

Topic link

2. Analysis idea and code

You can get the answer by XOR each number , Because any number XOR is equal to itself 0, The title says that only one number appears once , The others all appeared twice , Therefore, the result of two digital XORs is 0,0 The number of XOR appearing only once is equal to the number of XOR appearing only once , The time complexity is O(n)

	public int singleNumber(int[] nums) {
    
        int res = 0;
        for (int i = 0; i < nums.length; i ++ ) {
    
            res = res ^ nums[i];
        }
        return res;
    }

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for item in nums:
            res = res ^ item
        return res

A number that appears only once III

1. Title Description

Topic link

2. Solution ideas and code

Ideas ：

• Use a hash table to store the number of occurrences of each number , Then the number of occurrences will be 1 The result is returned to
• Use XOR and and and operations , Suppose the number appearing once is x1、x2, First, XOR all numbers , According to the last question, the final result is $x=x1\oplus x2$, And then take x The last 1, That is to use x & -x, Because the result of this bit is 1, So it can be concluded that x1 and x2 The bit of must be different , This bit of all numbers of the original array can be divided into two groups by using the and operation ,x1 and x2 Must not be in the same group , Then each group will have only one number that appears once , You can get the final result .

	public int[] singleNumber(int[] nums) {
    
        if (nums.length < 2)    return new int[2];
        
        int res = 0;
        for (int num : nums) {
    
            res ^= num;
        }
        res = res & (-res);
        int num1 = 0, num2 = 0;
        for (int num : nums) {
    
            if ((res & num) == 0) {
    
                num1 ^= num;
            } else {
    
                num2 ^= num;
            }
        }
        return new int[]{
    num1, num2};
    }

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        if len(nums) < 2:
            return []
        res = 0
        for num in nums:
            res ^= num
        res = res & (-res)
        num1, num2 = 0, 0
        for num in nums:
            if res & num == 0:
                num1 ^= num
            else:
                num2 ^= num
        return [num1, num2]

A number that appears only once II

1. Title Description

Topic link

2. Solution ideas and code

• Use a hash table to map the number of occurrences of each number , Then find the element that only appears once
• Get the number on each digit of the answer , Because all the other numbers appear three times , So each digit of the answer is equal to the result and modulus of all digits 3, Note that if the target language does not distinguish between signed and unsigned numbers , The highest position requires special judgment .

	public int singleNumber(int[] nums) {
    
        int res = 0;
        for (int i = 0; i < 32; i ++ ) {
    
            int total = 0;
            for (int num : nums) {
    
                total += ((num >> i) & 1);
            }
            
            if ((total % 3) == 1) {
    
                res |= (1 << i);
            }
        }
        return res;
    }

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in range(32):
            total = sum((num >> i) & 1 for num in nums)
            if total % 3:
                if i == 31:
                    res -= (1 << i)
                else:
                    res |= (1 << i)
        return res

2 The power of

1. Title Description

Topic link

2. Solution ideas and code

• Use n & (n - 1) You can remove n The lowest point of , Judge whether the result is 0 that will do
• Use n & (-n) It can be taken out n The last 1, Determine whether the result is consistent with n Equal is enough

	public boolean isPowerOfTwo(int n) {
    
        return n > 0 && ((n & (n - 1)) == 0);
    }

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

A subset of

1. Title Description

Topic link

2. Solution ideas and code

• Iteration results , Each result in the array can be represented by the corresponding number of bits in binary , Suppose the array has 3 Elements , that 100 Indicates that the first element appears , The second element does not appear , The third element does not appear , The final binary maximum is 111.
• Recursive solution , For each position of the array , You can choose to include or exclude

	public List<List<Integer>> subsets(int[] nums) {
    
        List<Integer> tmp = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < (1 << nums.length); i ++ ) {
    
            tmp.clear();
            for (int j = 0; j < nums.length; j ++ ) {
    
                if ((i & (1 << j)) != 0) {
    
                    tmp.add(nums[j]);
                }
            }
            //  Note that you must reinitialize a List, otherwise ans The final result of all points to the same value 
            ans.add(new ArrayList<Integer>(tmp));
        }
        return ans;
    }




class Solution {
    
    List<Integer> tmp = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    
    
    public List<List<Integer>> subsets(int[] nums) {
    
        dfs(0, nums);
        return ans;
    }
    
    public void dfs(int cur, int[] nums) {
    
        if (cur == nums.length) {
    
            ans.add(new ArrayList<>(tmp));
            return ;
        }
        
        //  Do not select this bit 
        dfs(cur + 1, nums);
        
        //  Select this bit 
        tmp.add(nums[cur]);
        dfs(cur + 1, nums);
        tmp.remove(tmp.size() - 1);
    }
}

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for i in nums:
            #  Add the current number before each existing result 
            res = res + [[i] + num for num in res]
        return res