Algorithm|2. XOR operation

Algorithms|2. XOR operation

1. Exchange the values of two numbers without additional variables

Title: Swap the values of two numbers (in an array) without additional variables

Problem-solving ideas:

• Properties using exclusive-or operations

Code and running results:

2. Find the only number that appears odd times

Question: In an array, there is an odd number of occurrences of a number, and an even number of occurrences of other numbers, how to find and print this number

Problem-solving ideas:

• Explanation: The complement of the complement code is the complement of the opposite number is equal to the complement of the original number together with the inversion of the sign bit and adding at the end
• XOR all the numbers in the array once, and the result is the result

Core code:

//In arr, only one kind of number appears odd number of times
public static void printOddTimesNum1(int[] arr){<!-- -->
    int ero=0;
    for (int cur:arr) {<!-- -->
        ero^=cur;
    }
    System.out.println("The numbers that appear odd times are:" + ero);
}

Test Methods:

Explain that this question and the next question are both writing logarithms, and the test method is written in the same main method. Therefore, the content of this part will not be written below.

//for test
public static void main(String[] args) {<!-- -->

    int[] arr1 = {<!-- --> 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
    // System.out.println("Expected result:" + 2);
    printOddTimesNum1(arr1);

    // int[] arr2={1,1,2,2,2,3,3,3,4,4};
    int[] arr2 = {<!-- --> 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
    // System.out.println("Expected result: " + 2 + " " + 3);
    printOddTimesNum2(arr2);

}

Test Results:

3. Find the only number that appears odd number of times

Question: In an array, there are two kinds of numbers that appear odd number of times, and other numbers appear even number of times, how to find and print these two numbers

Problem-solving ideas:

• Get the 1 on the far right: sum the original number and the opposite number
• Divide the numbers in the array into two groups. Grouping basis: Whether there is 1 on the far right side of the data of the XOR full array
• Get the position of 1 on the far right == “Represented in a binary sequence == “Decimal number == “Use this number to judge whether there is a 1 in the number in the array, and if there is, XOR to an ero1 to get it a result
• Another result can be obtained by XORing the ero and ero1 of the entire set of numbers and then XORing

Core code:

//In arr, there are two numbers that appear odd times
public static void printOddTimesNum2(int[] arr){<!-- -->
    int ero=0;
    for (int cur:arr) {<!-- -->
        ero^=cur;
    }
    //Extract the rightmost 1: AND the original number and the opposite number
    int righteousOne=ero & amp;(-ero);
    // System.out.println(rightestOne);
    //ero': Extract the result of a group of numbers whose rightmost is this 1
    int ero1=0;
    for (int cur:arr) {<!-- -->
        ero1^=(cur & amp;rightestOne)==0?0:cur;
    }
    ero=ero^ero1;
    System.out.println("Numbers that appear odd times are: " + ero + " " + ero1);
}

4. Find the only number that appears K times

Question: In an array, one kind of number appears K times, and other numbers appear M times. It is known that M > 1, K < M, and finding the number that appears K times requires additional space complexity O(1), time Complexity O(N)

Problem-solving ideas:

• Explanation: 1. The auxiliary array is a fixed-length array, and the space complexity is O(1) 2. judge whether the rightmost side is (num>>i) & amp;1, and the result is 1/0; extract the rightmost 1: num & amp;(-num), the result is an integer power of 2
• Use the auxiliary array to count how many numbers in the array are 1 in the i-th binary bit-Statistical method: Get the binary sequence of each element, and add the occurrence of 1 into the statistics array
• Use the ans variable, traverse the array, if the number of occurrences of 1 in this position is modulo m, if it is k, it means that there is a 1 in the digit of the target number, put it into the result variable — means of or
• The premise of taking modulo m is that k

Logarithm:

• The way to use map

• The method of traversing the table to find the number of k values – keySet (key) or entrySet (the relationship between ky and value)

  The keySet used by the logarithm, here is a demonstration of the use of entrySet:

Set<Map.Entry<String, String>> entrySet=map.entrySet();
 
for (Map.Entry<String, String> entry:entryseSet) {<!-- -->
 
    System.out.println(entry.getKey() + "," + entry.getValue());
 
}
//Get K through getKey(), and get V through getValue

• Shuffle Order (shuffleOrder): The number of i positions is exchanged with the randomly generated number of j (0~N-1) positions

Core code:

public static int km(int[] arr,int k,int m){<!-- -->
    int[] help=new int[32];
    //statistics
    for (int cur:arr) {<!-- -->
        for (int i = 0; i < 32; i ++ ) {<!-- -->
            help[i] + =(cur>>i) &1;
        }
    }
    //Judge the position where 1 appears in the number of k times, and put the relevant situation in the binary sequence of ans
    int ans=0;
    for (int i = 0; i < 32; i ++ ) {<!-- -->
        ans|=help[i]%m==0?0:1<<i;
    }
    return ans;
}

Test code:

 //for test
    public static int test(int[] arr,int k,int m){<!-- -->
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < arr. length; i ++ ) {<!-- -->
            if(map. containsKey(arr[i])){<!-- -->
                map. put(arr[i], map. get(arr[i]) + 1);
            }else{<!-- -->
                map. put(arr[i],1);
            }
        }
        int ans=0;
        for (int num:map.keySet()) {<!-- -->
            if(map.get(num)==k){<!-- -->
                ans=num;
                break;
            }
        }
        return ans;
    }

    //for test
    public static int[] generateRandomArray(int maxKinds,int range,int k,int m){<!-- -->
        int kNum=(int) (Math. random()*(range + 1))-(int) (Math. random()*(range + 1));
        int kinds= (int) (Math.random()*maxKinds) + 2;//2~maxkinds + 1

        //System.out.println("kinds:" + kinds);
        int[] arr=new int[k + (kinds-1)*m];
        //The random function of generating km is not written correctly....
// int[] arr= new int[0];
// try {<!-- -->
// arr = new int[k + (kinds-1)*m];
// } catch (NegativeArraySizeException e) {<!-- -->
// System.out.println("k:" + k);
// System.out.println("kinds:" + kinds);
// System.out.println("m:" + m);
            k:2
            kinds: 0
            m:4
// throw new RuntimeException(e);
// }
        int index=0;
        for(;index<k;index ++ ){<!-- -->
            arr[index]=kNum;
        }
        kind--;

        HashSet<Integer> set=new HashSet<>();
        set.add(kNum);

        while(kinds--!=0){<!-- -->
            int curNum=0;
            do {<!-- -->
                curNum=(int) (Math. random()*(range + 1))-(int) (Math. random()*(range + 1));
            }while(set. contains(curNum));
            set.add(curNum);
            for (int i = 0; i < m; i ++ ) {<!-- -->
                arr[index + +]=curNum;
            }
        }
        shuffleOrder(arr);
        return arr;
    }

    //for test
    //Scramble the order of the array:
    public static void shuffleOrder(int[] arr){<!-- -->
        for (int i = 0; i < arr. length; i ++ ) {<!-- -->
            int j = (int) (Math. random()*arr. length);
            int tmp=arr[i];
            arr[i]=arr[j];
            arr[j]=tmp;
        }
    }

    //for test
    public static void main(String[] args) {<!-- -->
        boolean succeed=true;
        int kinds=5;
        int range=30;
        int maxTimes=9;
        int testTimes=1000;
        for (int i = 0; i < testTimes; i ++ ) {<!-- -->

            int a = (int) (Math. random() * maxTimes) + 1; // a 1 ~ 9
            int b = (int) (Math. random() * maxTimes) + 1; // b 1 ~ 9
            int k = Math. min(a, b);
            int m = Math.max(a, b);
            // k < m
            if (k == m) {<!-- -->
                m++;
            }

            int[] arr=generateRandomArray(kinds,range,k,m);
            int ret1=km(arr,k,m);
            int ret2=test(arr,k,m);
            if(ret1!=ret2){<!-- -->
                System.out.println("k=" + k + " m=" + m);
                System.out.println("km:" + ret1);
                System.out.println("test:" + ret2);
                System.out.println(Arrays.toString(arr));
                System.out.println("Oops!Error!");
                succeed=false;
                break;
            }
        }
        if(succeed){<!-- -->
            System.out.println("succeed!");
        }
    }

Test Results:

Summary of XOR operation topic of bit operation

Definition:

Same as 0, different as 1.

Understanding: addition without carry

Nature:

• 0^N=N
• N^N=0
• commutative and associative

Example Summary:

• Swapping without temporary variables: three equations aba
• Find the only odd number of even times: all XOR
• Find the only two odd times in the even number of times: XOR grouping XOR; 1 on the far right of the grouping rule (complement of the opposite number)
• Find K of M times: auxiliary array; for each binary statistics (shift); traverse (or) for auxiliary array