Extending That XOR Trick to Billions of Rows
nochlin.com
Extending That XOR Trick to Billions of Rows
1–10 of 25 posts
Re: Extending That XOR Trick to Billions of Rows
#2Before you get too excited, this is a probabilistic algorithm, not a deterministic one. Feels weird to call it an "extension" when you lose an absolute guarantee, but still cool nonetheless.
Re: Extending That XOR Trick to Billions of Rows
#3[deleted]
Re: Extending That XOR Trick to Billions of Rows
#4It would be nice if they explained what XOR trick that is. It seems to have something to do with finding missing numbers in a list?
Re: Extending That XOR Trick to Billions of Rows
#5It would be nice if they explained what XOR trick that is. It seems to have something to do with finding missing numbers in a list?
It's a solution to the problem: given a list of n-1 unique integers 1 through n, find the missing integer.
The trick is that when you xor all of the numbers in the list together and then xor that with the xor of 1 through n, the result is the missing number.
Re: Extending That XOR Trick to Billions of Rows
#6It would be nice if they explained what XOR trick that is. It seems to have something to do with finding missing numbers in a list?
It's a solution to the problem: given a list of n-1 unique integers 1 through n, find the missing integer. The trick is that when you xor all of the numbers in the list together and then xor that with the xor of 1 through n, the result is the missing number.
I know XOR only in the context of binary numbers. Is this "XOR trick" more general?
Re: Extending That XOR Trick to Billions of Rows
#7Earlier quoted context omitted.
It's a solution to the problem: given a list of n-1 unique integers 1 through n, find the missing integer. The trick is that when you xor all of the numbers in the list together and then xor that with the xor of 1 through n, the result is the missing number.
I know XOR only in the context of binary numbers. Is this "XOR trick" more general?
Every number on computers is converted to binary internally, so yes this works on decimal numbers too.
Re: Extending That XOR Trick to Billions of Rows
#8It would be nice if they explained what XOR trick that is. It seems to have something to do with finding missing numbers in a list?
https://florian.github.io//xor-trick/ if you want detailed information and a list of possible applications.
Re: Extending That XOR Trick to Billions of Rows
#9Earlier quoted context omitted.
It's a solution to the problem: given a list of n-1 unique integers 1 through n, find the missing integer. The trick is that when you xor all of the numbers in the list together and then xor that with the xor of 1 through n, the result is the missing number.
I know XOR only in the context of binary numbers. Is this "XOR trick" more general?
It works on the binary representation so it actually works for any data type, even composite types! It won't resolve pointers/references/aliases of course
Re: Extending That XOR Trick to Billions of Rows
#10A rough sketch for a more direct way to extend the XOR trick to finding more than two differences:
For e.g. 3 differences: instead of a binary xor (i.e. binary-digit-wise sum mod 2), do a binary-digit-wise sum mod 3 (negating one input); a 0 (mod 3) sum result for a given bit means that the bit is the same in all entries, and 1 (mod 3) or 2 (mod 3) mean that you can partition on the bit, resulting in partitions with sizes `sum` and `input_different_element_count - sum`; then you repeat this recursively until they reach containing just 1 difference. (rounding the modulo up to the next power of two instead of odd modulos for the summing is perfectly fine, the final infinite-precision sum is in the range of [0; diffcount] anyway)
Extends trivially to more than 3 differences, and collapses to the basic trick for 2 differences. The accumulator size is O(log(diffcount) * element_size), but the recursive partitioning takes O(n) space or O(diffcount * n) time (plus some logarithm something maybe). Tradeoffs are probably reasonably possible, but the basic hashset approach can reduce its O(n) space requirement at the cost of taking >O(n) time too by partitioning on a hash.