3 ms·

What is the closed form solution of the xor-sum though?

• jwilk 4y ago
  s(n) = • n if n mod 4 = 0, • 1 if n mod 4 = 1, • n + 1 if n mod 4 = 2, • 0 if n mod 4 = 3. Or alternatively: • s(4n) = 4n • s(4n + 1) = 1 • s(4n + 2) = 4n + 3 • s(4n + 3) = 0 Proof by induction: • s(4n + 1) = s(4n) ⊕ (4n + 1) = 4n ⊕ (4n + 1) = 1 • s(4n + 2) = s(4n + 1) ⊕ (4n + 2) = 1 ⊕ (4n + 2) = 4n + 3 • s(4n + 3) = s(4n + 2) ⊕ (4n + 3) = (4n + 3) ⊕ (4n + 3) = 0 • s(4n + 4) = s(4n + 3) ⊕ (4n + 4) = 0 ⊕ (4n + 4) = 4n + 4
• aliceryhl 4y ago
  You already have to spend the time to go through the list. Just add up the xor as you iterate through the list.