There is a formula for adding numbers from 1 to n and there is a notation for expression the product of numbers from 1 to n. But what about bitwise operations?

Let’s consider taking the bitwise AND from 1 to n.

We know that 1&2 = 0, and 0&x = 0 for all x. If we take the bitwise AND of numbers from 1 to n, we get the constant 0. That is not very interesting. Starting from some other number will also cause the series to eventually reach 0 and stay at 0.

What about bitwise OR? Visually, we’re accumulating bits, and as soon as we reach a power of 2, that power of 2 bit will be set thereafter. So if n is between 2^a and 2^b, f(n) = 2^b -1.

Now for the interesting part, what happens when you take the XOR of the numbers from 1 to n?

# XOR

XOR is a bit hard to reason about since bits can get set and unset. So let’s get our hands dirty digitally and the write a program to see the output.

``````def f(n):
i = 1
s = 0
while i <= n:
s ^= i
print(i, s)
i+=1

f(32)
``````

The output:

``````(1, 1)
(2, 3)
(3, 0)
(4, 4)
(5, 1)
(6, 7)
(7, 0)
(8, 8)
(9, 1)
(10, 11)
(11, 0)
(12, 12)
(13, 1)
(14, 15)
(15, 0)
(16, 16)
(17, 1)
(18, 19)
(19, 0)
(20, 20)
(21, 1)
(22, 23)
(23, 0)
(24, 24)
(25, 1)
(26, 27)
(27, 0)
(28, 28)
(29, 1)
(30, 31)
(31, 0)
(32, 32)
``````

This is an interesting pattern, and we can come up with a hypothesis for the closed form for f!

``````f(n) = n if n == 0 mod 4
f(n) = 1 if n == 1 mod 4
f(n) = n+1 if n == 2 mod 4
f(n) = 0 if n == 3 mod 4
``````

Let’s try to prove this then. A strong induction seems to be the easiest way.

So let’s show for the base case n = 0 to 3, which is trivial. Now let’s try and prove f(k).

If k == 0 mod 4, then f(k-1) = 0, and f(k) = k.

If k == 1 mod 4, then f(k-1) = k - 1, and f(k) = (k-1)^k = 1.

If k == 2 mod 4, we know the last bit of k is 0, and therefore when XOR’ed with 1 = f(k-1), we’re simply setting the last bit, so f(k) = n+1.

And finally, if k == 3 mod 4, then f(k-1) = k by induction hypothesis, and so f(k) = k ^ k = 0.

QED.

## Lemmas

Since ^ is associative, we can easily find the XORS of a range of numbers. XOR from a to b is thus f(b) - f(a-1).

# Afterthoughts

1. XOR is quite interesting and the formula for its “SUM” is elegant too :)
2. Getting the computer to compute results so the human can spot the pattern and prove it is quite a nice flow.
3. This came out as an organic discovery on a bored afternoon. Upon searching online, there’s tonnes of discussions on existing forums already.