Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

EGYPT's blog

Exclusive or "Xor" range ?
By EGYPT, 15 years ago, In English

I ask if i can calculate xor  to all numbers in a specific range without using loop

for example if  i have 

start=3  
end =3211233432145321;

the result  start ^ start+1 ^ start+2 ^ start+3.........end-1^end

Thanks in advanced.

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
15 years ago, hide # |
← Rev. 2  
Vote: I like it +39 Vote: I do not like it

just use fact that (4k)^(4k+1)^(4k+2)^(4k+3) = 0
→ Reply
15 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it
Let's introduce 
f(x) = x ^ (x-1) ^ (x-2) ^ ... ^ 1
Then anwer would be 
f(end) ^ f(start - 1)
Let's now learn to calculate f(x) fast enough. First, notice that f(4*k - 1) = 0 (provable by induction). So to calculate f(x) you only need to take at most 4 last numbers and xor them.
Finally, 
f(4*k) = 4*k
f(4*k + 1) = 1
f(4*k + 2) = 4*k + 3
f(4*k + 3) = 0
→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    you mention that you need only last 4 numbers so to calculate f(x)

    f(x)=(x-3)^(x-2)^(x-1)^(x)

    i test it by using this function vs bruteforce solution but the result different.


    typedef long long LL;
    LL solve(LL n)
    {
    LL res=(n-3)^(n-2)^(n-1)^n;
    return res;
    }
    solve(123456789)

    res=123456789

    ========================================

    vs 

    LL res=1;
    for(LL i=2;i<=123456789;i++)
    res^=i;
    res=1
    so please correct me if i'm wrong ,Thanks
    → Reply
15 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it
Are there any problems on online coding sites which uses this fact? If so, can you share the links?
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
In fact, the problem can be solved just by magic:

int Xor(int a, int b) {
return a * (a & 1) ^ b * !(b & 1) ^ !!(((a ^ b) + 1) & 2);
}
→ Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I wrote C++ code for this: https://github.com/liruqi/topcoder/blob/master/leetcode/exclusive-or-of-numbers-range.cpp

→ Reply