The common logical operations: and, or, and not should be familiar and easy to understand. I also learned some knowledge of Boolean algebra in high school mathematics. In logic circuits, and, or, and not are equally easy to understand. However, a very important operation XOR (XOR) is added to the logic circuit. Common textbooks only introduce the definition of XOR, so most people only remember what the operation rules of XOR are, but have a vague understanding of the meaning and application scenarios of XOR. Therefore, this paper tries to introduce the meaning of xOR, hoping to help you understand xor.

Logical meaning of xOR

Let’s start with the familiar or, which means that if one of the two conditions is true, then the conclusion is true. For example: the daily shopping amount is more than 1000 or single consumption is more than 500 can participate in the lottery, one of the two conditions to meet the result is true. But we also have an “or” in everyday life, and the two results can’t be true at the same time. I’ll be in Beijing or Shanghai tomorrow. I can be in Beijing, I can be in Shanghai, but I can’t be in Beijing and Shanghai at the same time.

So in terms of the result, the xOR rule is that if either of the two conditions is true, the result is true. Both are true, both are false, and the result is false.

If you look at the Venn diagram and the disjoint parts of the two conditions are true, and the dissimilar parts of the two conditions are true, the truth range is the sum of the dissimilar parts of the two conditions.

So why is there no xOR in the underlying logical operation? Because xor is not a fundamental operation, xor is a second-order operator that can be equated with and or not:

Xor in a logic circuit

The mathematical theory foundation of computer is Boolean algebra, and the physical foundation is logic circuit. In theory, logical operations can be represented with only three operators, but in engineering there is another thing to consider: reuse! When engineers find that a compound operation is often used in computers, they extract the functions of the compound operation and encapsulate them separately. Xor is a fundamental operation in logic circuits. Computers were originally designed to compute. One of the most basic functions of computation is addition. Let’s look at the implementation of addition at the binary level:

Let’s look at the simplest single digit addition:

0 + 0 =  0 
1 + 1 = 10
0 + 1 =  1
1 + 0 =  1
Copy the code

The result of the ones digit is the result of an xor operation: if two inputs are the same, the result is 0; If the input is different (one bit is 1), the result is 1.

Of course, we also need to consider the carry case:

   10
+  11-- -- -- -- -- =101
Copy the code

Thus, the sum of each bit of an adder is equal to the xOR result of the input and carry of two numbers. The carry is equal to the sum of the input numbers (if both numbers are 1, the carry is 1).

Because the basic addition operations in computers require the use of xor operations, xor gates are an essential component of logic circuits.

Xor properties and applications

Xor has the peculiar property that the result of a calculation is jointly affected by two inputs. Since the result is related to both inputs, if you know the xor result and one input, you can inversely derive the other input.

Let’s contrast this property with and or:

  • Or: As long as one input is 1, the other input is either 0 or 1, the result is 1
  • And: As long as one input is 0, the other input is 0 or 1, the result is 0 (short-circuit effect)

The result of xOR, regardless of whether one input is 0 or 1, needs to know the other input to know the result. It’s kind of like a key and a lock, you have to pair it to unlock it.

Exclusive or password

This feature is particularly important in encryption algorithms. We generate a set of keys and use this key to perform an xor to the plaintext to get a ciphertext. As long as the key is not leaked, the ciphertext cannot be calculated. If it’s and, if the plaintext is 0, then whatever the key is, it’s going to be 0. Obtaining the key and ciphertext cannot invert the plaintext.

Exclusive or check

Because the xOR result is determined by both inputs, if you know the xor result and one input you know what the other input is. For example, we know that the xor result is 1, and an input is 0. That means there’s a 1 in the input, and one is 0, so the other value is 1. Here are two more corollaries, a number that either or itself is zero. Because I’m the same as every one of my digits, this is 0. A number x or 0 equals itself. These two properties are called the zero return and identity laws:

The radius P = P0P the radius0 = P
Copy the code

If you know the xOR result and an input, you can find another input:

A ⊕ B = C a ⊕ B ⊕ B = C ⊕ B// Since B ⊕ b turns out to be 0, this simplifies toA radius0= C ⊕ B a = C ⊕ BCopy the code

What a coincidence! An xOR operation on one input yields another. This property is really helpful for data backup!

For example, an xOR parity check between two 3-bit binary sequences 101 and 011 yields the xor sum 110. If the sequence 101 is lost, we can check the known sequence 011 with xOR and perform xOR operation to get the lost sequence.

For example, we have a hard drive that needs to be backed up, but it would be a waste to back up every hard drive once. We can select two hard drives for xOR and save the results. As long as both drives don’t go down at the same time, the data can be recovered (I admit I’m a bit of a wager).

The interview questions

Some of the interview questions involved in-place arithmetic, and the most frequent was xOR arithmetic. A typical question is LeetCode: 136. Numbers that appear only once:

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.

If you use conventional methods, you have to use extra space to count the number of occurrences. If xOR is applied to each number using the zeroing law, the result is a number that appears only once:

public int singleNumber(int[] nums) {
    int single = 0;
    for (int num : nums) {
        single ^= num;
    }
    return single;
}
Copy the code

A slightly more difficult interview question for this feature is 56 – the number of occurrences in the array:

An integer array nums contains two occurrences of all but two digits. Write a program to find these two numbers that appear only once. The time complexity is O(n), the space complexity is O(1).

The solution to this problem also uses the xOR property. The solution is to group the xOR, and if we divide the two numbers we’re looking for into two groups, the xor of each group will be the two numbers we’re looking for.

So how do you divide these two numbers into two groups? Again, the xOR property is used: if the xor result of two numbers is 1, the two numbers are different. So let’s find the xor of the entire array, which is equal to A ⊕ b. Then pull out the bits that are 1 in the result. Group the array according to whether the digit is 0 or 1, and the two numbers will be divided into two groups.

public int[] singleNumbers(int[] nums) {
    int ret = 0;
    for (int n : nums) {
        ret ^= n;
    }
    int div = 1;
	// Find the left-shifted digit where the median value of the xor is 1
    while ((div & ret) == 0) {
        div <<= 1;
    }
    int a = 0, b = 0;
    for (int n : nums) {
        if((div & n) ! =0) {
            a ^= n;
        } else{ b ^= n; }}return new int[]{a, b};
}
Copy the code