Anyone interested in bit-level tricks like this, should have a copy of Hacker's Delight on their bookshelf.
That XOR Trick (2020)
71–80 of 141 posts
Re: That XOR Trick (2020)
#72Earlier quoted context omitted.
No, again, that's not my point. The code from the article is O(2n) when it could be O(n). I know we're not supposed to care about constant factors, but I've lived in a world where not micro optimizing the ever loving shit out of my software could potentially make people throw up, so this sort of stuff kind of stands out to me.
The code in the article is written in Python, whose only for loop is for-each. It is 2N XOR operations, regardless of whether you use one or two loops. I probably would have written it with a single loop, using the `enumerate` iterator adapter. But in Python, two loops is almost certainly more efficient.
for i in range(n - 1):
Is pretty much a standard for loop. Between that and
for n in numbers:
You can do pretty much the same things as a more conventional language.
You could also solve it pretty simply like this:
expected_sum = (n * (n + 1)) / 2
missing_num = expected_sum - sum(numbers)
This only iterates the list once. This would probably be my solution if I was given this task in an interview.
Re: That XOR Trick (2020)
#73About one month ago I applied XOR in a similar (but a bit more complicated way) to Redis Vector Sets implementation, in the context of sanity check of loading a vset value from the RDB file. I believe the way it works is quite interesting and kinda extends the applicability of the trick in the post.
The problem is that in vector sets, the HNSW graph has the invariant that each node has bidirectional links to a set of N nodes. If A links to B, then B links to A. This is unlike most other HNSW implementations. In mine, it is required that links are reciprocal, otherwise you get a crash.
Now, combine this with another fact: for speed concerns, Redis vector sets are not serialized as
element -> vector
However, in this specific case, there is a problem: collisions. The register may be 0 even if there are non reciprocal links in case they are fancy, that is, the non-reciprocal links are a few and they happen to XOR to 0. So, to fix this part, I use a strong (and large) hash function that will make the collision extremely unlikely.
It is nice now to see this post, since I was not aware of this algorithm when I used it a few weeks ago. Sure, at this point I'm old enough that never pretend I invented something, so I was sure this was already used in the past, but well, in case it was not used for reciprocal links testing, this is a new interview questions you may want to use for advanced candidates.
Re: That XOR Trick (2020)
#74This 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 bit corresponding to a number and one for loop to find the missing number.
And if my bit array doesn't fit in memory, then neither does the array from the problem (and certainly not the HashSet etc.).
Re: That XOR Trick (2020)
#75In ye olden days, bit manip operations were faster than algebraic operations. And sometimes even faster than a load immediate, hence XOR AX, AX instead of MOV AX, 0.
And in these modern days it matters that an algorithm can use divide and conquer and can be parallelized. Xor plays nice here. Also the lack of carry bits and less branching help in the crypto space.
Re: That XOR Trick (2020)
#76For 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,…
In your array-based equation, you say n+1, but in your explanation you say n+3. Is that a mistake?
Re: That XOR Trick (2020)
#77Earlier quoted context omitted.
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…
I 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.
(wrapping) overflow doesn't affect the final result.
Re: That XOR Trick (2020)
#78This 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
Re: That XOR Trick (2020)
#79Earlier quoted context omitted.
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…
> The trick works on any 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…
> ... 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)
Re: That XOR Trick (2020)
#80For 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.