Блог пользователя EGYPT

Exclusive or "Xor" range ?
Автор EGYPT, 14 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

just use fact that (4k)^(4k+1)^(4k+2)^(4k+3) = 0
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится
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
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Are there any problems on online coding sites which uses this fact? If so, can you share the links?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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);
}
→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить