That XOR Trick (2020)
florian.github.io
That XOR Trick (2020)
1–10 of 243 posts
Re: That XOR Trick (2020)
#2A great disturbance in the force, as if millions of gatekeeping interviewer voices suddenly cried out in terror and were suddenly silenced.
Re: That XOR Trick (2020)
#3> XOR all values between 1 and n
An O(n) algorithm!? You'd expect there to be a closed-form solution for this, analogous to summing a series using n*(n-1)/2.
OEIS to the rescue. http://oeis.org/A077140 gives ((n+1)%2)*n + (n+(n%2))//2 % 2
Re: That XOR Trick (2020)
#4As mentioned in this article, x ^ x == 0. Fun fact, this is frequently used by compilers as a "cheap" way to zero out a register.
In addition, there are comparatively few cases in programming where we XOR. Sure, it happens in things like games quite a lot, but the main use is actually _cryptography_.
Between these two facts (more like hints really), I managed to reverse engineer the bulk of a piece of malware I was given to analyse in a an internship. I was handed the malware, a copy of IDA Pro, and given a few days to see what I could find. All I could remember when presented with a wall of hex encoded machine code were the hints above. I looked for XORs of different values, assumed it was crypto, and extrapolated from there. Found a routine happening three times in quick succession and guessed it was triple-DES. Then I guessed that writing your own 3DES from scratch was unlikely, so googled for crypto libraries and happened to find one that nearly matched (I think an earlier/unmodified version), and worked my way up tagging the operations until I got to the purpose, exfiltrating various registry keys and browser history to [somewhere].
It was a fun exercise, and therefore these facts will stay with me for far longer than they are accurate I'm sure!
Re: That XOR Trick (2020)
#5I hope this article takes off so that my company will have to change its initial code screen. We make no use of xor in our rather large codebase (I’ve checked) yet pin a lot on whether an interviewee is aware of this trivia.
Re: That XOR Trick (2020)
#6As mentioned in this article, x ^ x == 0. Fun fact, this is frequently used by compilers as a "cheap" way to zero out a register. In addition, there are comparatively few cases in programming where we XOR. Sure, it happens in things like games quite a lot, but the main use is actually _cryptography_. Between these two facts (more like hints really), I managed to reverse engineer the bulk of a piece of malware I was g…
I feel like xor comes up all the time in programming! Perhaps generations that have almost entirely focuses on web front and backends never have use for it, but libraries underneath it all certainly are.
Re: That XOR Trick (2020)
#7As mentioned in this article, x ^ x == 0. Fun fact, this is frequently used by compilers as a "cheap" way to zero out a register. In addition, there are comparatively few cases in programming where we XOR. Sure, it happens in things like games quite a lot, but the main use is actually _cryptography_. Between these two facts (more like hints really), I managed to reverse engineer the bulk of a piece of malware I was g…
A somewhat common use of XOR is p != q. It is actually an XOR.
Another useful way to think of XOR is "either p or q is true, but not both, and not neither."
Re: That XOR Trick (2020)
#8The xor swap can be dangerous: if variables have the same value, they xor to zero so you end up losing the values of both variables.
Re: That XOR Trick (2020)
#9You can actually extend the XOR trick for missing elements to any fixed number!
The standard (non-XOR) low-memory solution calculates the sum of x, x^2, x^3, ..., x^n, which gives enough information to find the missing elements as the roots of an n degree polynomial.
We can just do the same thing in the finite field F_{2^k}, where k is the bitwidth of the integers. Addition in this field corresponds to a bitwise XOR, so the first term gives exactly the 1-missing case!
I don't remember how to actually solve the resulting polynomial over the finite field though.
Re: That XOR Trick (2020)
#10Ah off by one errors are hard:
> 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 1]
should be
> 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 2]
Because a 0 indexed array of length n-1, has n-2 as it's last index. After all, it's missing a value.