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