找出给定范围内所有数字的异或结果

1. Overview

In this tutorial, we’ll present the problem of finding the XOR of all numbers in a given range.

First, we’ll explain the naive approach. Then, we’ll see how we can improve it in order to obtain a better solution. Finally, we’ll present a comparison between both approaches.

2. Defining the Problem

In this problem, we’re given an array of size and multiple queries. In each query, we’re asked to calculate the bitwise XOR operation between all the elements in range [L, R] .

The array doesn’t change between queries. In other words, there are no queries that ask us to change the value of a certain element inside the array.

Therefore, for each query [L, R] inside the array , we must return the value of $A_L \oplus A_{L+1} \oplus A_{L+2} \oplus ... \oplus A_R$ , where $\oplus$ is the bitwise XOR operation between the elements in the range [L, R] .

3. XOR Background

As we know, the bitwise XOR operation works on the two numbers bit by bit. For each bit, the result can be extracted from the presented table:

As we can see, if both bits are similar, then the XOR equals to zero. Otherwise, the result equals to one. Put differently, the bitwise XOR operation equals zero in case the number of ones is even and equals one in case the number of ones is odd.

Also, an important thing to notice is that the bitwise XOR works on each bit independently. In other words, the result of each bit doesn’t affect the result of any other bits inside the number. Keep these notes in mind when we discuss the solution in section 5.

4. Naive Approach

First, we’ll explore the naive approach. Let’s take a look at its algorithm:

algorithm NaiveXorRange(A, L, R):
    // INPUT
    //    A = The input array
    //    L = The left side of the range
    //    R = The right side of the range
    // OUTPUT
    //    Returns the XOR of all the elements in the range [L, R]

    answer <- 0
    for i <- L to R:
        answer <- answer XOR A[i]
    return answer

In the beginning, the algorithm sets the answer to zero. After that, we iterate over the elements of the range and calculate the XOR of all of its elements. Finally, we return the calculated answer.

The complexity of the naive approach is , where is the size of the array. The reason behind this complexity is that we might end up iterating over all the elements in the worst case.

Therefore, the complexity of each query is linear.

5. Prefix-XOR Approach

Let’s try to improve our naive approach.

5.1. Precalculation Idea

Since each bit is calculated separately, we can solve the problem for each bit independently. After that, we can create a complete solution.

Suppose the problem was to handle individual bits. Same as before, we need to calculate the XOR for this bit in the range [L, R] . First, let’s create a boolean array named pref . In each cell , we’ll store the prefix XOR of all bits in the range [0, i] .

From the definition of the XOR operation in section 3, we can see that if the number of bits in the ith prefix is even, then the ith cell will equal to zero. Otherwise, the ith cell will equal to one.

Now, let’s check the original problem. We need to find the XOR of bits in the range [L, R] — in other words, whether the number of ones in the range [L, R] is even or odd.

To do this, let’s consider two values. The first value is pref[R] , which covers the range [0, R] . This range covers all the elements from the needed range, plus some extra elements which are in the range [0, L-1] . Therefore, the second value is pref[L-1] , which covers the range .

From these two values, we can conclude the value of the range [L, R] .

5.2. Solution Idea

After calculating the pref array, we have four cases to consider in each query:

Both and equal zero. Since equals zero, the number of ones is even before starting the range . Also, the number of ones remains even after processing the range . This can only happen if the number of ones in the range is even as well.
Both and equal one. Since equals ones, the number of ones is odd before entering the range . Also, since equals one, the number of ones in this range is also odd. This can only hold if the number of ones in the range is even, which causes the parity of the bit to remain the same.
equals one, while equals zero. Since the number of ones in the range is odd, but then changes to be even in the range , we can conclude that the number of ones in the range is odd.
equals zero, while equals one. Since the number of ones in the range is even, but then changes to be odd in the range , we can conclude that the number of ones in the range is odd.

We can see that if both pref[R] and pref[L-1] have the same value, then the answer is zero. Otherwise, the answer equals one.

This is equivalent to performing the XOR operation between pref[R] and . Therefore, the answer is simply $pref[R] \oplus pref[L-1]$ , where $\oplus$ is the bitwise XOR operation.

5.3. Precalculation Algorithm

In order to form a general solution, we need to calculate the prefix XOR array pref .

Let’s take a look at the implementation of this step:

algorithm PrecalculationXorPrefix(A, n):
    // INPUT
    //    A = The input array
    //    n = The size of the array
    // OUTPUT
    //    Returns the prefix XOR array of A

    pref[0] <- 0
    for i <- 1 to n:
        pref[i] <- pref[i - 1] XOR A[i]
    return pref

The idea is based on dynamic programming. In the beginning, we know that the answer of Pref[0] equals zero.

Next, for each range [0, i] , we can calculate its answer from the range [0, i-1] . The only difference between these two ranges is A[i] . Therefore, we need to add A[i] to the range . In other words, $pref[i] \gets pref[i-1] \oplus A[i]$ . In the end, we return the calculated array pref .

The complexity of the precalculation step is , where is the number of elements in the array .

5.4. Answering the Queries

After building the pref array, we can answer each query with the same approach discussed in section 5.2.

Let’s take a look at the algorithm of answering the queries:

algorithm PrefixXorRange(L, R, pref):
    // INPUT
    //    L = The left side of the range
    //    R = The right side of the range
    //    pref = The prefix XOR array (calculated using algorithm PrecalculationXorPrefix)
    // OUTPUT
    //    Returns the XOR of all the elements in the range [L, R]

    return pref[R] XOR pref[L - 1]

As we can see, we just return the XOR between pref[R] and pref[L-1] as discussed in section 5.2. The complexity of answering each query is .

6. Comparison

Consider the table that shows a comparison between both approaches:

Naive

Prefix XOR

Precalculation
Complexity

None

O(n)

Query
Complexity

O(n)

O(1)

Limitations

None

When changing an element
in , we must calculate
the pref array from scratch

Obviously, the prefix XOR approach is better when it comes to comparing complexities. However, it requires us to calculate the pref array in advance. After that, we can answer each query efficiently at the complexity of O(1) .

One thing to keep in mind is that this only holds when we don’t change the values of the elements in the array . When we have two types of queries, either changing the value of a single element or answering a query of the XOR of elements in the range [L, R] , both approaches have the same complexity.

Therefore, we can use the naive approach, which is simpler.

7. Conclusion

In this tutorial, we explained the problem of calculating the XOR of a given range of numbers. First, we presented the naive approach. Next, we discussed the theoretical idea and implementation of the prefix XOR approach.

Finally, we presented a summary comparison between the two approaches.

Persistence

REST

Security