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

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

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
  • Проголосовать: не нравится

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

just use fact that (4k)^(4k+1)^(4k+2)^(4k+3) = 0
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +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
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится
Are there any problems on online coding sites which uses this fact? If so, can you share the links?
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 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);
}
→ Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить