Find XOR of all numbers in a given range

Question

You are given a wide range [a, b], where "a" and "b" can usually be from 1 to 4,000,000,000 inclusive. You should find the XOR of all numbers in the given range.

This issue was used in TopCoder SRM. I saw one of the solutions presented in the match, and I can’t understand how it works.

Did anyone help explain the winning solution:

long long f(long long a) { long long res[] = {a,1,a+1,0}; return res[a%4]; } long long getXor(long long a, long long b) { return f(b)^f(a-1); } 

Here getXor() is the actual function for calculating xor the whole number in the transmitted range [a, b] and "f ()" is a helper function.

Answer 1

This is a pretty smart decision - it takes advantage of the fact that there are sample results in XOR projects. The function f() calculates the total run of XOR with [0, a]. Take a look at this table for 4-bit numbers:

 0000 <- 0 [a] 0001 <- 1 [1] 0010 <- 3 [a+1] 0011 <- 0 [0] 0100 <- 4 [a] 0101 <- 1 [1] 0110 <- 7 [a+1] 0111 <- 0 [0] 1000 <- 8 [a] 1001 <- 1 [1] 1010 <- 11 [a+1] 1011 <- 0 [0] 1100 <- 12 [a] 1101 <- 1 [1] 1110 <- 15 [a+1] 1111 <- 0 [0] 

Where the first column is a binary representation, followed by a decimal result and its relation to its index (a) in the XOR list. This is due to the fact that all the upper bits are canceled and the lower two bits cycle every 4. So, how to get to this small lookup table.

Now consider the general range [a, b]. We can use f() to find the XOR for [0, a-1] and [0, b]. Since any XOR'd value with itself is zero, f(a-1) just cancels all the values ​​in the XOR sample less than a , leaving you with an XOR range [a, b].

Answer 2

Adding an excellent answer to FatalError, the string return f(b)^f(a-1); could be better explained. In short, this is because XOR has these wonderful properties:

• He is associative . Put the brackets wherever you want.
• It is commutative - it means that you can move operators (they can "commute")

Here and in action:

 (a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c 

Like this:

 a ^ b = c c ^ a = b 

Add and propagate two examples of other associative / commutative operators, but they do not change themselves. So why are these properties important? Well, a simple route is to expand it into what it really is, and then you can see these properties at work.

First we define what we want and call it n:

 n = (a ^ a+1 ^ a+2 .. ^ b) 

If this helps, think of XOR (^) as if it were an addition.

Let it also define a function:

 f(b) = 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ b 

b greater than a , so just reliably dropping a few extra brackets (which we can, because it is associative), we can also say the following:

 f(b) = ( 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ (a-1) ) ^ (a ^ a+1 ^ a+2 .. ^ b) 

This simplifies:

 f(b) = f(a-1) ^ (a ^ a+1 ^ a+2 .. ^ b) f(b) = f(a-1) ^ n 

Then we use this reversal property and commutativity to give us the magic line:

 n = f(b) ^ f(a-1) 

If you think of XOR as an add-on, you would drop it. XOR is XOR, what to add to subtract!

How do I come up with this myself?

Remember the properties of logical operators. Work with them almost like adding or multiplying, if that helps. It feels unusual that both (&), xor (^) and or (|) are associative, but they are!

First, launch a naive implementation, look for patterns in the output, and then start searching for rules that confirm that the pattern is correct. Simplify your implementation even further and repeat. This is probably the route that the original creator took, emphasized by the fact that it is not completely optimal (i.e., uses the switch statement, not the array).

Answer 3

I found out that the code below also works as the solution given in the question.

Maybe this is a bit optimized, but this is what I got from observing the repetition, as indicated in the accepted answer,

I would like to know / understand the mathematical proof underlying this code as described in @Luke Briggs answer

Here is the JAVA code

 public int findXORofRange(int m, int n) { int[] patternTracker; if(m % 2 == 0) patternTracker = new int[] {n, 1, n^1, 0}; else patternTracker = new int[] {m, m^n, m-1, (m-1)^n}; return patternTracker[(nm) % 4]; } 

Answer 4

I solved the recursion problem. I just divide the data set into an almost equal part for each iteration.

 public int recursion(int M, int N) { if (N - M == 1) { return M ^ N; } else { int pivot = this.calculatePivot(M, N); if (pivot + 1 == N) { return this.recursion(M, pivot) ^ N; } else { return this.recursion(M, pivot) ^ this.recursion(pivot + 1, N); } } } public int calculatePivot(int M, int N) { return (M + N) / 2; } 

Let me know your thoughts about the solution. I am pleased to receive feedback on the improvement. The proposed solution calculates XOR in 0 (log N) complexity.

thank

Answer 5

To support XOR from 0 to N, the above code needs to be changed as shown below:

 int f(int a) { int []res = {a, 1, a+1, 0}; return res[a % 4]; } int getXor(int a, int b) { return f(b) ^ f(a); } 

Answer 6

Please tell me why F (A-1)? I can not understand your explanation.