61–70 of 141 posts
This is nonsensical, where does the second truth table come from? Instead you just observe that, by definition, 1^0 == 0^1.
Fun fact: the xor swap fails when the variables are aliases. This was the trick used in one of the underhanded code competitions. Basically xor swapping a[i] with a[j] triggered the evil logic when i was equal to j.
The state of RC4 consists of a random permutation of bytes. Whenever it outputs a value, it further permutes the state by swapping some bytes of the state. Th xor swap trick sets one of these values to zero, whenever RC4 attempts to swap the same item within the permutation. This gradually zeros out the state, until RC4 outputs the plaintext.
The XOR solution was a valid answer, but not the only answer we would have happily accepted.
The interview question was chosen such that it's very easy to understand and quick to solve, meaning it would indicate the candidate knew at least the basics of programming in C#. Almost surprisingly, we actually had candidates applying for "senior" level positions who struggled with this.
It could be solved in a multitude of ways, e.g:
- XOR as above
- Use of a HashSet
- Use for loop and List which contains a number and its count.
- Use LINQ to group the numbers or something and then find the one with the count.
As long as what they did worked, it was a "valid" answer, we could then often discuss the chosen solution with the candidate and see how they reacted when we let them know of other valid solutions.
It was really great for not being a "one clever trick" question and could act as a springboard to slightly deeper discussions into their technical thought processes and understanding.
This was a go to interview question to be solved in C# at a place I worked at a while back which had developers allocated to projects working on pretty standard line of business systems. The XOR solution was a valid answer, but not the only answer we would have happily accepted. The interview question was chosen such that it's very easy to understand and quick to solve, meaning it would indicate the candidate knew at…
(n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1)
[ n, 1, n + 1, 0 ][n % 4]
Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear, and then keep XORing it with its successors. We start with xxxxxx00 which is our n. Then we XOR it with n + 1 which is xxxxxx01 and that clears all the x's and leaves us with 00000001. Now we XOR it with n + 2 which is xxxxxx10 and that yields xxxxxx11 which is n + 3. The cycle finishes when we now XOR it it with n + 3 which yields 00000000. So we get n, 1, n + 3, 0 and then the cycle repeats as we are back at zero and at n + 4 which is again divisible by four.
To derive "The XOR trick" I think both *associativity* and communitativity are needed. That is, one should also prove a ^ (b ^ c) = (a ^ b) ^ c. Instinctive, but non-trivial.
For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…
Earlier quoted context omitted.
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 wher…
(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?
To derive "The XOR trick" I think both *associativity* and communitativity are needed. That is, one should also prove a ^ (b ^ c) = (a ^ b) ^ c. Instinctive, but non-trivial.
Yeah that's what I was thinking, you need both
For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…