Hi,

I have a summation of xors - a (0 to n), b (0 to m) -> sum(a^b).
ie
for a in range(0, n):
for b in range(0, m):
total+= a^b

if it were multiplication i could just do
(n+1)n/2 * (m+1)m/2

is there a similar simplification i can use for the boolean logic?

 

This makes pretty much zero sense.

How about presenting a simple example, say with n=4, so that we can figure out what you mean?

 

Hi,

sure

m = 4
n = 2
for a in range(0, m):
for b in range(0, n):
total += a^b

a,b
0,0 = 0
0,1 = 1
0,2 = 2
1,0 = 1
1,1 = 0
1,2 = 3
2,0 = 2
2,1 = 3
2,2 = 0
3,0 = 3
3,1 = 2
3,2 = 1
4,0 = 4
4,1 = 5
4,2 = 6

total = 34

if the operator were * instead of xor
a,b
0,0 = 0
0,1 = 0
0,2 = 0
1,0 = 0
1,1 = 1
1,2 = 2
2,0 = 0
2,1 = 2
2,2 = 4
3,0 = 0
3,1 = 3
3,2 = 6
4,0 = 0
4,1 = 4
4,2 = 8
total = 30
2(2+1)/2 = 3
4(4+1)/2 = 10
= 3*10 = 30
thus for the multiplication i go from (n+1)(m+1) multiplications and (m+1)(n+1) additions, to 3 multiplications, 2 additions, and 2 divisions. Ie from O(mn) to O(1). I should be able to get a similar reduction for the sum of xors.

 

Okay, I see what you are doing and it is what I figured you were probably getting at.

Since the XOR is a linear operation, my guess is that you won't find something simple via algebraic manipulation. You will probably need to look for patterns and reductions.

For instance, if you have m>n, is there anything you can learn from breaking it up into the sum of [0:n]x[0:n] and the sum of [n+1:m]x[0:n]

You might also look at counting how many times each bit position survives the XOR.