EGYPT's blog

Exclusive or "Xor" range ?
By EGYPT, 14 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?
14 years ago, # |
← 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
14 years ago, # |
  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
  • 14 years ago, # ^ |
      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
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      for(int i=n-n%4;i<=n;++i)
      //calc xor

      or


      int f(int n){
      switch(n%4){
      case 0: return n;
      case 1: return 1;
      case 2: return n+1;
      default: return 0;
      }
      }
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Expressions "at most 4 last numbers" and "only last 4 numbers" are different. In fact, you need to take exactly (x+1)%4 last numbers.
      → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      outdated
      → Reply
14 years ago, # |
  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
14 years ago, # |
  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
»
9 years ago, # |
  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