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

How to find the xor of numbers in a range
Автор silent_sky, история, 6 лет назад, По-английски

Given two integers $$$A$$$ and $$$B$$$, find $$$A$$$ $$$\oplus$$$ $$$($$$ $$$A$$$ $$$+$$$ $$$1$$$ $$$)$$$ $$$\oplus$$$ $$$($$$ $$$A$$$ $$$+$$$ $$$2$$$ $$$)$$$ $$$\oplus$$$ $$$\dots$$$ $$$\oplus$$$ $$$B$$$ where $$$A$$$ $$$<=$$$ $$$B$$$

No, not in linear time

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

»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

You can use a trick, that 1 xor 2 xor .. xor (4 * x — 1) = 0.

And A xor A + 1 xor .. xor B = (1 xor 2 xor .. xor (A — 1)) xor (1 xor 2 .. xor B)

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

https://mirror.codeforces.com/blog/entry/2154

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

The XOR sum of numbers from 1 to m equals:

m   if m%4 is 0
1   if m%4 is 1
m+1 if m%4 is 2
0   if m%4 is 3
→ Ответить