This is a followup to an answer I posted on stackoverflow about calculating a cumulative operation.
Are there any other invertible operations on integers besides addition (+), subtraction (-) and XOR where if you have N integers, you can compute a generalized sum (actual sum in case of addition) and the order does not matter?
There's multiplication and division but multiplication isn't invertible, and division doesn't yield valid results for 0 operands.
Yes, in fact uncountably many. This is because if $a \oplus b$ is such an operation and $f : \mathbb{Z} \to \mathbb{Z}$ is a bijection, then $f^{-1} (f(a) \oplus f(b))$ is also such an operation, and there are uncountably many permutations of $\mathbb{Z}$. (Edit: this argument actually requires slightly more work, since it's not obvious that $f^{-1}( f(a) \oplus f(b)) \neq a \oplus b$ for enough $f$. But the argument below is better.)
That was a little tongue-in-cheek. If I understand your question correctly, you are basically asking for examples of countable abelian groups. The integers $\mathbb{Z}$ under addition form such a group, as does the direct sum of countably many copies of the cyclic group $\mathbb{Z}/2\mathbb{Z}$ (this is the XOR example), but, for example, the rationals $\mathbb{Q}$ under addition also form such a group, and there are more complicated examples. One can take the direct sum of any countable collection of examples and get another example, which incidentally shows that there are uncountably many examples even up to isomorphism.
There is a reasonable classification of abelian groups which are finitely generated, all of which are finite or countable. The infinitely generated case was discussed at this math.SE question.
In case that was a little too abstract, there is a generalization of XOR for every positive integer $b > 1$ defined as follows: write your (non-negative) integers in base $b$, and add their digits without carrying.
Not quite sure what you mean by invertible, or why you want it - it does not seem necessary for your accumulator definition. So ignoring that for now ....
How about min, max ? Or count ?
If you admit composite accumulators with additional state, then you can have average (mean), because you can store { count, mean } and update:
count' = count + 1
mean' = (count*mean + n) / count'
or perhaps store { count, sum, mean } where
count' = count + 1
sum' = sum + n
mean' = sum' / count'
It seems like you want a monoid: an associative binary operator with an identity. The identity value is the starting value of your accumulator. The associative property means the order of application is irrelevant. For more information see An Introduction to the Bird-Meertens Formalism, by Jeremy Gibbons.
In functional programming, your problem is equivalent to finding list homomorphisms, which are functions of lists (f) that can be expressed with a monoid (#) and the list concatenation operator (++), such that:
f (a ++ b) = (f a) # (f b)
i.e. applying a function to the whole list can be decomposed into applying the function to 2 sublists and combining the 2 results with a new binary operator. The Third Homomorphism Theorem (see another paper by Gibbons) states that if you can find two implementations for the function f, one accumulating from the left (foldl) and one accumulating from the right (foldr) then you can find the monoid operator and the function can be calculated in any order, or in parallel. An excellent paper on the subject is Automatic Inversion Generates Divide-and-Conquer Parallel Programs.
Mik
