Gray code is something semi-related. For hardware encoders of a position you want only one transition between states, that is, the XOR of the two to have only one bit set. Normal binary has multiple transitions between some values (e.g. three bit changes between 011 and 100). Gray code could be 000, 001, 011, 010, 110, 111, 101, 100.
That XOR Trick (2020)
91–100 of 141 posts
Re: That XOR Trick (2020)
#92For 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,…
Fascinating. It can see it work but I still can't really wrap my head around where the magic cycle length of 4 comes from.
Another interesting fact is that each time you make the xor of four consecutive numbers, beginning with an even number, the result is zero.
Example in J.
xor =: (16 + 2b0110) b.
f =: 3 : 'xor/ y + i. 4'
f"0 ] 2 * 1 + i. 100
Summing a hundred millions: +/ f"0 ] 2 * i 100000000 gives zero (it takes a few seconds). So it seems the stated property holds for every even n.
Re: That XOR Trick (2020)
#93> XOR on the same argument: x ^ x = 0
For those who do/did assembly, this is the common way to set a register to zero in x86 assembly (probably not only) because the instruction does not need an operand, so is shorter, and executes in one cycle only.
Re: That XOR Trick (2020)
#94Re: That XOR Trick (2020)
#95Pet peeve: It is common to describe XOR as a special logical operator ("either or"), but it is arguably easier to just describe it as ≠ (!=, not equal) for Boolean inputs.
However, then it is clearly still easier to just phrase everything in terms of = (equality) instead!
Equality is for binary inputs is also called XNOR, biconditional, iff, ↔, etc, which is the negation of XOR. But thinking of it immediately as "=" is much more straightforward.
Another advantage of = over ≠/xor is that equality is not just commutative and associative, it's intuitively obvious that it is associative. The associativity of ≠/xor is less obvious. Moreover, equality is also transitive, unlike inequality/xor.
Overall, equality seems a much more natural concept to reason with, yet I don't know of any languages which have a bitwise equality/XNOR/↔ operator, i.e. one that operates on integers rather than Booleans.
Re: That XOR Trick (2020)
#96[dead]
Re: That XOR Trick (2020)
#97One can generalize this to k missing numbers the same way as we typically do for the addition case by using finite fields:
XOR is equivalent to addition over the finite field F_2^m. So, in this field, we're calculating the sum. If we have two numbers missing, we calculate the sum and sum of squares, so we know:
x + y
x^2 + y^2
From which we can solve for x and y. (Note all the multiplications are Galois Field multiplications, not integer!)
Similarly for k numbers we calculate sums of higher powers and get a higher order polynomial equation that gives our answer. Of course, the same solution works over the integers and I'd imagine modular arithmetic as well (I haven't checked though).
Re: That XOR Trick (2020)
#98This 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…
you are missing the most obvious one, no? Sum both lists and take the difference, that's the missing number, since the items are guaranteed unique
[deleted]
Re: That XOR Trick (2020)
#99Tldr. I'm sorting that array all day baby
Re: That XOR Trick (2020)
#100This 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…
> "You are given an array A of n - 1 integers" It's an array of integers so it fits in memory (otherwise it wouldn't be called an array). As it fits in memory, n cannot be that big. I'd still ask for more requirements, TopCoder problem style: I want to know how big n can be that the array fits in memory. I didn't know that XOR trick. My solution would be a bit arrays with n bits and two for loops: one to light each b…
You could make the problem harder with "you are given a stream of n - 1 integers". N could then be any number, unbound by available memory.
That makes the problem harder which makes it more interesting, a lot of the solutions wouldn't work anymore (this isn't necessarily a good interview question though)