Hacker News Reader

Comment by analog31 | Hacker News Reader

The first thing that occurred to me is that if a number is missing from a list, the sum of that list will fall short. But I like XOR's.

View on HN

It really tickles my brain in a lovely way that it avoids all overflow risk as well

There is no overflow risk. The trick works on any Abelian group. N-bit values form an Albanian group with xor where 0 is the identity and every element is its own inverse. But N-bit values also form an Abelian group under addition with overflow, where 0 is the identity and 2s-compliment is the inverse.

If you’re working on an architecture where a single multiplication and a bit shift is cheaper than N xor’s, and where xor, add, and sub are all the same cost, then you can get a performance win by computing the sum as N(N+1)/2; and you don’t need a blog post to understand why it works.

I think they meant that XOR avoids the overflow risk, whereas doing the sum of the array to figure out which number could cause an overflow.

(wrapping) overflow doesn't affect the final result.

You can also calculate the XOR-accumulation of all values between 1 and n in O(1) using a lookup table like this:

    [n, 1, n+1, 0][n%4]

Well there you go, I learnt something today. My spidey sense told me to be wary of overflow but I suppose I was wrong

> The trick works on any Abelian group

(https://en.wikipedia.org/wiki/Abelian_group -- I'll use ⋆ as the Abelian group's operation, and ~ for inversion, below.)

I believe you are implying:

(g(1) ⋆ ... ⋆ g(n)) ⋆ ~(g(i(1)) ⋆ g(i(2)) ⋆ ... ⋆ g(i(n-1))) = g(m)

where "m" is the group element index that is not covered by "i".

However, for this to work, it is requried that you can distribute the inversion ~ over the group operation ⋆, like this:

~(g(i(1)) ⋆ g(i(2)) ⋆ ... ⋆ g(i(n-1))) = ~g(i(1)) ⋆ ~g(i(2)) ⋆ ... ⋆ ~g(i(n-1))

because it is only after this step (i.e., after the distribution) that you can exploit the associativity and commutativity of operation ⋆, and reorder the elements in

g(1) ⋆ ... ⋆ g(n) ⋆ ~g(i(1)) ⋆ ~g(i(2)) ⋆ ... ⋆ ~g(i(n-1))

such that they pairwise cancel out, and leave only the "unmatched" (missing) element -- g(m).

However, where is it stated that inversion ~ can be distributed over group operation ⋆? The above wikipedia article does not spell that out as an axiom.

Wikipedia does mention "antidistributivity":

https://en.wikipedia.org/wiki/Distributive_property#Antidist...

(which does imply the distributivity in question here, once we restore commutativity); however, WP says this property is indeed used as an axiom ("in the more general context of a semigroup with involution"). So why is it not spelled out as one for Abelian groups?

... Does distributivity of inversion ~ over operation ⋆ follow from the other Abelian group axioms / properties? If so, how?

> ... Does distributivity of inversion ~ over operation ⋆ follow from the other Abelian group axioms / properties? If so, how?

It does. For all x and y:

  (1) ~x ⋆ x = 0 (definition of the inverse)
  (2) ~y ⋆ y = 0 (definition of the inverse)
  (3) (~x ⋆ x) ⋆ (~y ⋆ y) = 0 ⋆ 0 = 0 (from (1) and (2))
  (4) (~x ⋆ ~y) ⋆ (x ⋆ y) = 0 (via associativity and commutativity)

In (4) we see that (~x ⋆ ~y) is the inverse of (x ⋆ y). That is to say, ~(x ⋆ y) = (~x ⋆ ~y). QED.

Right. Another way to see this is that for a general (possibly non-Abelian) group, the inverse of xy is y⁻¹x⁻¹ (because xyy⁻¹x⁻¹ = x1x⁻¹ = xx⁻¹ = 1 [using "1" for the identity here, as is typical for general groups], or more colloquially, "the inverse operation of putting on your socks and shoes is taking off your shoes and socks"). For an Abelian group, y⁻¹x⁻¹ = x⁻¹y⁻¹, and we're done.

Awesome, thanks! :)

True, I hadn't thought of that. I'm spoiled by Python. ;-)

Sum and xor are the same, but over different fields.

Reply on news.ycombinator.com