Xor operation tips

.

When I was working with LeetCode, I encountered some problems with XOR solutions that were really ‘amazing’. Today, I saw teacher Ruan Yifeng shared an article or tutorial, the reference link has the original text, feel very interesting, then translate, deepen understanding, consolidate knowledge.

If you’ve ever come across an amazing xor technique, please share in the comments

---

The text start

Published time: 2020-03-15

There are many popular interview questions that can be solved either by using common data structures and algorithms, or by using some of XOR’s features in seemingly incomprehensible ways.

While it’s not always reasonable to expect XOR solutions in an interview, it’s interesting to figure out how they work. As it turns out, they’re all based on the same technique, which we’ll slowly demonstrate in this article. Then, we’ll look at the use of xor techniques, such as solving this common interview question:

An array A contains n-1 members that are integers between 1 and n and are not duplicated. Find the missing number.

There are, of course, many straightforward ways to solve this problem, but using xor is definitely eye-opening.

Xor operator

XOR is a binary – based bit operation. I’ll use the ^ sign. If the two operands are the same, the result is 0, otherwise the result is 1. This is really an exclusive or operation. The final result will only be 1 if one of the arguments is 1

Xor truth table

x	y	x ^ y
0	0	0
0	1	1
1	0	1
1	1	0

Most programming languages implement ^ as a bit operator, which means that XOR treats its operands as 32-bit sequences of bits (zeros and ones) rather than decimal, hexadecimal, or octal values.

Here’s an example:

0011 ^ 0101 = 0110
Copy the code

Because:

0 to the 0 is 0, 0 to the 1 is 1, 1 to the 0 is 1, 1 to the 1 is 0Copy the code

This is why everything can be xor, not just Boolean manipulation.

Xor operation law

We can derive some characteristics from the previous definition and then apply these characteristics to interview questions. One by one, don’t worry!

1. The operation of a value with 0 is equal to itself

x ^ 0 = x
Copy the code

This can be seen from lines 1, 2, and 3 of the truth table.

2. Same value xor gets 0

x ^ x = 0
Copy the code

It can be seen from truth table 1 and 4 that when x = y, the result is 0.

3. The operation of x and -1 is the inverse of x

x ^ -1 = ~x
Copy the code

4. Exchangeability

x ^ y = y ^ x
Copy the code

5. Combined with sex

x ^ (y ^ z) = (x ^ y) ^ z
Copy the code

Combined with the above, let’s look at a small demo:

  a ^ b ^ c ^ a ^ b     // The law of commutativity
= a ^ a ^ b ^ b ^ c     // Use x ^ x = 0 rule
= 0 ^ 0 ^ c             // Use x ^ 0 = x and commutativity rules
= c
Copy the code

Interview question 1: Swap values

Let’s do a problem:

Swap values and do not use any new variables

I’m sure any programmer can do the basic operation of swapping values using a temporary variable, but the title says you can’t use new variables. This time the xor comes!!

x ^= y
y ^= x
x ^= y
Copy the code

Isn’t it Amazing!! So let’s see step by step how do we do this, where each line of comment represents the current value of (x, y)

x ^= y // => (x ^ y, y)
y ^= x // => (x ^ y, y ^ x ^ y) = (x ^ y, x)
x ^= y // => (x ^ y ^ x, x) = (y, x)
Copy the code

This is the fastest way to swap values between two variables without requiring any extra space.

The action here is: having x ^ y in one register and x in another allows us to modify y. Once x ^ y is stored (instruction 1), we simply place x in another register (instruction 2) and use it to change x ^ y to Y (instruction 3).

Interview question 2: Find the missing number

Take a look at the question at the beginning of the article:

An array A contains n-1 members that are integers between 1 and n and are not duplicated. Find the missing number.

Of course, there are many direct ways to do this, so today we’re going to look at xOR.

1 ^ 2 ^... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 2]Copy the code

In this case, each member of the array appears twice, and the xor operation gives you 0. Only the missing number appears once, so you end up with this value. Write code (originally in Python, I wrote it in JS, if you are interested in Python, see the original)

function findMissing(arr, n) {
  let result = 0;
  // XOR of all values in the given array
  for (let i = 0; i < arr.length; i++) {
    result ^= arr[i]
  }
  // XOR of all the values from 1 to n
  for (let i = 1; i <= n ; i++) {
    result ^= i
  }
  return result
}
Copy the code

Just looking at the code, this seems like an incomprehensible algorithm. However, when you know how the XOR technique works, it becomes so easy. I think that explains why it’s unreasonable to expect this solution in an interview: It requires knowledge of a very specific technique, but doesn’t require much algorithmic thinking. Before we move on, let me say two more things:

Promote applications beyond integers

So far, we have looked at integers from 1 to n, but this is not required. In fact, the previous algorithm applies to the following cases:

(1) There is a set of potential elements

(2) There is a set of elements actually present.

(3) The two sets differ only in one missing element.

This works well for integers because the set of potential elements is from 1 to n.

However, in practical application, we will encounter the following situations:

1) The collection of potential elements is the Person object, where we need to find missing attributes

2) The set of potential elements is all the nodes in the graph, and we need to find a missing node

3) The set of potential elements is ordinary integers (not necessarily from 1 to n), and we want to find a missing integer

Use ordinary operators to solve problems

If the algorithms above still seem a bit confusing, it might be helpful to think about how to use arithmetic operators to achieve the same result.

 function findMissing(arr, n) {
    let result = 0;
    // Subtract all values in the given array
    for (let i = 0; i < arr.length; i++) {
      result += arr[i]
    }  
    // Add all the values from 1 to 
    for (let i = 1; i <= n ; i++) {
      result -= i
    }
    return result
  }
Copy the code

Addition is not as fast as xor and requires extra space. If the number is large, there is a possibility of spillover.

Interview question 3: Find duplicate numbers

Here’s the interesting thing: We can apply the same answer to similar interview questions:

An array A contains n+1 members, which are integers between 1 and n. Only one member appears twice, the other members only appear once, please find the number that appears twice.

In the code. Opponents! Again, the solution to interview question 2.

function findDuplicated(arr, n) {
  let result = 0;
  for (let i = 0; i < arr.length; i++) {
    result ^= arr[i]
  }
  for (let i = 1; i <= n ; i++) {
    result ^= i
  }
  return result
}
Copy the code

Combined with XOR technique, it can be simplified into the following problem solving ideas:

  x ^ x ^ x
= x ^ 0
= x
Copy the code

Everything else cancels out because they happen to show up twice.

Interview question 4: Find 2 missing/duplicate numbers

Now we can go one step further. Consider this slightly more difficult problem

Given array A, containing n-2 members, integers between 1 and n, all numbers appear only once, only 2 are missing, find both of them.

Let’s take two numbers that are repeated and do the same thing, so we’re not going to do the repeated case here.

I think you’ve already figured it out, but we’re going to go through it the same way we did before. Let’s consider what would happen if we used the previous xor algorithm: we would again get an xor statement where everything cancels out with each other except the two elements we are looking for.

We use u and v for these two elements. After applying the previous algorithm, we are left with u to the v, but how do we extract u and v?

Operate u and V bit by bit

Think back to the old law: if they are alike, they get 0, otherwise they get 1.

Let’s analyze each byte in u ^ v: each zero means that the byte has the same value in both u and v. Each 1 represents a difference in bytes between u and v.

So based on that, we can find the first 1 in u ^ v, let’s say the ith bit, which means that u ^ V is different on the ith byte.

We can get 2 partitions:

1).0 partition

A). The set of all digits with the ith digit 0 in 1-n b). The set of digits with the ith digit 0 in aCopy the code

2). 1 partition

A). Set of all digits with the ith digit 1 in 1-n b). Set of digits with the ith digit 1 in aCopy the code

Because u and v are different at position I, we know they’re in different partitions. So u and v are in partition 0 and one is in partition 1.

Simplify the problem

Next, we can use the conclusion we mentioned earlier:

So far, we have looked at integers from 1 to n, but this is not required. In fact, the previous algorithm applies to the following cases:

(1) There is a set of potential elements

(2) There is a set of elements actually present.

(3) The two sets differ only in one missing element.

This corresponds exactly to our set in each partition! So we can apply this idea to one partition to find the missing element to find u, and then apply it to the other partition to find V!!

This is actually a good solution: we have effectively reduced this new problem to a general solution.

Take a chestnut

If you are confused by the above description, let me give you an example to make it easier to understand:

If A is equal to [1, 3], n is equal to 4, of course, the human eye will immediately see that 2 and 4 are missing. But how to make the computer understand.

Table 1-4 corresponding to decimal binary:

The decimal system	binary
1	0001
2	0010
3	0011
4	0100

The numeric decimal binary in array A corresponds to the table

The decimal system	binary
1	0001
3	0011

According to the formula:

 1 ^ 2 ^ 3 ^ 4 ^ 2 ^ 3 
 = 1 ^ 4
 = 5
Copy the code

Converting 5 to binary yields: 0101

We iterate from left to right and find that the index of the position where the first 1 occurs is 1, that is, I = 1 (for ease of traversing from left to right).

Next, we are divided into groups:

1).0 partition

A) set of all digits with the ith digit 0 in 1-4 ==> [1, 2, 3] b) set of digits with the ith digit 0 in A ==> [1, 3]Copy the code

2). 1 partition

A) set of all digits with the ith digit 1 in 1-n ==> [4] b) set of digits with the ith digit 1 in a ==> []Copy the code

It’s easy to say, u, v one partition at 0, one partition at 1

For the set in the two partitions: only one number in A and B is different! Use the previous xOR technique to solve the problem 🍺!

talk is cheap

show me the code:

function getTwoMissing(arr, n) {
  const result = findMissing(arr, n)
  const toBinary = parseInt(result).toString(2)
  // find the position where the first 1 appears
  let index = toBinary.indexOf('1');
  // Build partition to get two minimal sets
  // Get u, v
  // Crash!! I can't go on 😭
}
Copy the code

Sorry I can’t write any more! The idea of using xor makes me feel a bit nauseous ~~ I’d rather just use brute force to build a map to find 🤣

Challenge the limit

One might try to go a step further and aim to solve problems with more than two missing values. I don’t really think about it too much. But I think you can only do so much with XOR. If more than two elements are missing (or repeated), parsing a single byte will fail because the results of 0 and 1 can have several combinations.

The problem seems to require more complex solutions that are no longer based on xor. More complicated problems

More applications

Ruan yifeng’s article mentioned the use of xor to do data backup and encryption, interested students can have a look.

conclusion

As mentioned earlier, interview test techniques are not a good idea. They need to know an arcane trick, and once they know it, there’s nothing left to solve (except perhaps for interview question 4) : there’s almost no way to highlight algorithmic thinking, and there’s no good way to use data structures.

Sure, it’s cool to know how to use xor

Refer to the link

• The original link
• MDN
• Teacher Ruan Yifeng – Xor tutorial