Classic application of XOR operation in algorithms

 "Except for two numbers in an integer array, all other numbers appear twice. Please write a program to find these two numbers that only appear once?" This is a classic algorithm problem. At first glance, this problem has a lot of ideas.

   For example, first sort and then find the two numbers by searching for different data. The time complexity of this implementation method should be O(NlgN), because the best time complexity of the comparison sorting algorithm is like this. But at first glance, this problem has been solved, but a condition has not been fully utilized. Most elements appear in pairs. What is the role of this condition? Of course, another idea is to implement it with hashmap. This implementation method is to use a hash table to store the number of times each variable appears, and then traverse the hash table. However, this method also has problems. If there are negative numbers, or the values ​​of the array elements are particularly large, the space complexity of using Hashmap is too large. It is not the solution we need. The hashmap is suitable for counting values ​​within a certain range. The above two methods may be the quickest to think of.

   There are many ways to solve this problem, but it is difficult to find the best solution. This article will introduce the solution of this problem using XOR operation.

   XOR operation is a bitwise operation in C language. This operation may be familiar to embedded programmers, but it may be less used by general programmers. XOR operation has the following characteristics:

   0^num = num; 1^num = ~num; num ^ num = 0; where num = 0 or 1.

   The characteristics of using associative law are:

   a^a^b^b^c = (a^a)^(b^b)^c=0^0^c=c;

   Note: If a + b = c, then it is possible that a ^ b ^ c = 0; this condition is neither sufficient nor necessary. For example, if a = 1, b = 2, c = 3, then a ^ b ^ c = 0 is true, but if a = 2, b = 2, c = 4, then it is not true.

   From the associative law above, we can know that if the result of the XOR operation on two identical numbers is 0, since the elements in the question appear in pairs, we can make full use of the associative characteristics of the XOR operation. The result after XORing the array elements will definitely contain the characteristics of two unpaired elements.

   Assume that the array elements are a[N], where N is a large value and the unpaired elements are an and am. The steps to implement the above process are as follows:

   First, the variable element performs an XOR operation on all elements, and the result is definitely an^am. In other words, after the XOR operation, the characteristics of an and am are preserved in the result. Since am and an are different, the result of am^an must be greater than or equal to 1. If am and an are different, then a bit that is 1 in am^an must be a characteristic of either am or an.

   Then, define two values ​​num1 and num2, which are used to calculate an and am respectively. Select a bit in am^an as the characteristic bit. Assume that the Kth bit is the characteristic bit, and traverse the elements again. If the Kth bit of the element is 1, the element may be am or an, then perform an XOR operation on the current element and num1. If the Kth bit of the element is not 0, then the element may be another value, then perform an XOR operation on the current element and num2. After traversing all elements, since most data appear in pairs, according to the characteristics of the XOR operation, num1 and num2 will store two different values ​​respectively.

   From the above analysis, we can see that this algorithm only needs to traverse the array space twice to realize data judgment, so the time complexity is O(N). At the same time, because there is no structure such as hashmap, the space complexity is O(1). The implementation of this algorithm is definitely the best. Compared with the hashmap and sorting algorithms mentioned above, the time complexity and space complexity are smaller, so the implementation of this algorithm should be the best.

   The code is implemented as follows:

    #include
    #include

    int whichbitone(int in)
    {
        int i = 0;
        
        while((in & (1 << i)) == 0)
            i ++ ;

        return i;
    }

    int isbitone(int in, int k)
    {
        if((in & (1 << k)) != 0)
            return 1;
        else
            return 0;
    }

    void xortest(int *array, int size)
    {
        int dxor = 0, xor = 0;
        int i = 0, j = 0;
        int num1 = 0, num2 = 0;

        for(i = 0; i < size; ++ i)
            dxor ^= array[i];
        
        if(dxor != 0)
        {
            j = whichbitone(dxor);
            for(i = 0; i < size; ++ i )
            {
                if(isbitone(array[i],j) == 1)
                    num1 ^= array[i];
                else
                    num2 ^= array[i];
            }
            /*Get the first number*/
            printf("first data is %d ",num1);
            printf("second data is %d ",num2);
        }
    }

    int main(int argc, char *argv[])
    {
        int array[10] = {1,2,3,4,7,2,3,1,4,9};
        xortest(array,10);

        return 0;    
    }

   The above code basically implements the above description.

   Another variation of this question is "The elements in the array appear in pairs, but there are three unpaired elements. How can we quickly find these three elements?"

   This question seems to be related to this one. I even think we can use the same method to find three values. But later I found that there is a problem with this method. The situation with three values ​​is much more complicated than the situation with two values, because there are many more possibilities. It is not a problem of belonging to this element or another element. Although this solution may cause problems, it is still possible to solve it, except when the XOR result of the three elements is 0, that is, x^y^z = 0, this method is not valid.
   For finding copies of three different elements, I think it is mainly to find one of the elements, then remove this element, and then search for the other two elements as mentioned above. Of course, we first exclude the special case that the XOR of three data is zero. For the specific implementation, please refer to http://blog.csdn.net/zzran/article/details/8108787 .

   This problem still exists. If the value of these three elements after XOR is exactly zero, this method cannot solve it. Therefore, there is no problem in using XOR to solve the problem of only one unpaired or two different elements. It is feasible for three elements, but it may not always be true.

   The problem that the XOR operation targets in the algorithm is also specific, mainly the problem that the elements appear in pairs. If they do not appear in pairs, the practical performance of the algorithm will be greatly reduced, and even repeated elements may not be practical.