The 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.
You are wrong. Just try it out yourself. TFA actually explains why it still works even in that case.
That XOR Trick (2020)
31–40 of 243 posts
Re: That XOR Trick (2020)
#32As 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…
xor reg, reg is indeed the standard way to zero out a register in x86 assembly (it's not just a compiler trick) as it is both shorter and faster than loading the register with zero via a mov . Apart from that, I'd say that a common use of XOR operations in general are interactions with hardware peripherals where manipulating bit fields are needed.
Why does mov'ing a constant end up having overhead?
Re: That XOR Trick (2020)
#33Slightly disappointed at the "two missing values" solution:
First: one needs to realize that you can solve the "missing number" problem just as well with sums. So, if you're trying to find the "one missing number" between 1 and n, you simply subtract all values from n*(n+1)/2 (the sum of all said numbers) and you end up with the missing one. (using wrap-around semantics, you don't even need to have more bits of memory than you need for the xor solution!)
Second: A common way to solve a problem with two variables is to build a system of two equations. One can compute, in a single pass, what is "a+b" and "a^b" ; solve the system, and you get both variables with no additional lookups. Now, it's true that if you get a carry from the addition, this problem might not be solvable...but, if you can afford one extra bit for the potential carry, you're all set.
Re: That XOR Trick (2020)
#34> 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
Wondering at what value of n the closed form solution uses fewer cycles than n xors, since that’ll end being the follow-up question :)
Re: That XOR Trick (2020)
#35Ah 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.
Let's try an example with n=4: 1 ^ 2 ^ 3 ^ 4 ^ A[0] ^ A[1] ^ A[2] ^ A[3] It might be early in the morning and I am missing something, but it has n-1 as its last index. Any insight is appreciated :) Edit: There is a missing number in the array, thus its last index is n-2. Thanks for the correction, OP.
But there are only 3 items in the array (for example 1, 2 and 4). So the last valid index is 2.
Re: That XOR Trick (2020)
#36A = { 1, 2, ... , k, ..., n-1, n}, for 1sum({1..n}) = n(n-1) / 2
sum(A) = n(n-1) / 2 - k
k = n(n-1) / 2 - sum(A)
Is the interview question looking for a "clever" solution? I'm confused as to why someone would ask this question in an interview? It seems like the more challenging question would be "Find a method of summing a range 1..n in less than O(n) time/space complexity." [edit] I have a dumb. This calculation can happen in O(1). Because of n(n-1)/2, we know the sum of the range, no need to examine each value in the range. [/edit]
Or, even more fun, limit the functions/instructions the interviewee can use (ex, some 4 or 5 instructions of x86/WASM/etc. machine instructions, max 1 or 2 registers, etc.) to complete the task.
Re: That XOR Trick (2020)
#37> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). I'd rather know w…
Nobody wants to see the XOR solutions. These questions are really basic and only filter out the non-programmers. Any decent programmer should be able to solve all of these without a problem.
Re: That XOR Trick (2020)
#38The 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.
[deleted]
Re: That XOR Trick (2020)
#39For lot's of other fun bithacks, see: https://graphics.stanford.edu/~seander/bithacks.html
Re: That XOR Trick (2020)
#40Earlier quoted context omitted.
Let's try an example with n=4: 1 ^ 2 ^ 3 ^ 4 ^ A[0] ^ A[1] ^ A[2] ^ A[3] It might be early in the morning and I am missing something, but it has n-1 as its last index. Any insight is appreciated :) Edit: There is a missing number in the array, thus its last index is n-2. Thanks for the correction, OP.
But there are only 3 items in the array (for example 1, 2 and 4). So the last valid index is 2.
Ah. I was about to make an edit to my comment as you are correct :) Thanks!