4 ms·
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 o
by repiret 1y ago
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.
- deleted 1y ago[deleted]
- lblume 1y agoYou 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]
- ikurei 1y agoI 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.
- jonathrg 1y ago(wrapping) overflow doesn't affect the final result.
- OjotCewIo 1y ago> The trick works on any Abelian group (https://en.wikipedia.org/wiki/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#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?
- FBT 1y ago> ... 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.
- OjotCewIo 1y agoAwesome, thanks! :)
- stephencanon 1y agoRight. 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.
- anitil 1y agoWell there you go, I learnt something today. My spidey sense told me to be wary of overflow but I suppose I was wrong