Practice with the topic of bit operation force deduction

Basic knowledge of bit operation

An operation （&、|、^、~、>>、 | Novice tutorial (runoob.com)https://www.runoob.com/w3cnote/bit-operation.html Excerpt power button topic 136 、137、 260 、645

subject 1: 136. A number that appears only once https://leetcode-cn.com/problems/single-number/

  Code :

class Solution {
    public int singleNumber(int[] nums) {
        int sn=0;
        // According to the nature of the xor - reflexivity   The other elements appear twice   So all XORs are OK 
        for(int i=0;i<nums.length;i++){
            sn^=nums[i];
        }
        return sn;
    }
}

result :

subject 2:137. A number that appears only once IIhttps://leetcode-cn.com/problems/single-number-ii/

Code :

class Solution {
    public int singleNumber(int[] nums) {
        int res=0;
        for(int i=0;i<32;i++){
            // Traverse all bits from low to high 
            int sum=0;
            // Traverse all the numbers in the array 
            for(int num:nums){
                // Sum the current bit  & Take a bit 
                //sum+=(num&(1<<i));  That's not good   Still thinking about why ...
                sum+=(num>>i)&1);
            }
            if(sum%3==1){
                // If the sum of this bit is modulo three   Have remainder   Then assign the remainder to the result value 
                //| Make a position 1  because   For this problem, the single number with remainder   This one knows   So is 1 了 
                res|=(1<<i);
            }
        }
        return res;
    }
}

result :

 

subject 3:260. A number that appears only once IIIhttps://leetcode-cn.com/problems/single-number-iii/

 

Code :

class Solution {
    public int[] singleNumber(int[] nums) {
        int temp=0;
        int flag=0;
        int sn1=0;
        int sn2=0;
        // All values XOR   Get the XOR value of two numbers that occur only once 
        for(int num:nums){
            temp^=num;
        }
        // Traversal XOR results   Check which of the two numbers is different 
        for(int i=0;i<32;i++){
            // This one   The two numbers are different 
            if(((temp>>i)&1)==1){
                flag=i;
                break;
            }
        }
        // There are two groups of XOR 
        for(int num:nums){
            if(((num>>flag)&1)==0){
                sn1^=num;
            }else{
                sn2^=num;
            }
        }
        return new int[]{sn1,sn2};
    }
}

result :

subject 4:645. The wrong set https://leetcode-cn.com/problems/set-mismatch/

 

Code :

class Solution {
    public int[] findErrorNums(int[] nums) {
        int temp=0;
        int flag=1;
        int sn1=0;
        int sn2=0;
        // All values and 1-n XOR together   The repeated and the lost are singular 
        // Get duplicate and lost   The XOR value of two numbers 
        for(int i=1;i<=nums.length;i++){
            temp^=nums[i-1];
            temp^=i;
        }
        // Traversal XOR results   Check which of the two numbers is different 
        while((temp&flag)==0)
            flag<<=1;
        // There are two groups of XOR   Get the missing number and the repetition number 
        for(int i=1;i<=nums.length;i++){
            if((nums[i-1]&flag)==0)
                sn1^=nums[i-1];
            else
                sn2^=nums[i-1];  
            if((i&flag)==0)
                sn1^=i;
            else
                sn2^=i;
        }
        // Determine which number is repeated 
        for(int num:nums){
            if(sn1==num)
                return new int[]{sn1,sn2};
        }
        return new int[]{sn2,sn1};
    }
}

result :

 

Reference resources :

introduction - Force buckle plus - Try to do the best algorithm solution in West Lake District https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/