4 ms·
It 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?
by dark-star 1y ago
It 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?
- foota 1y agoIt'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.
- JPLeRouzic 1y agoI know XOR only in the context of binary numbers. Is this "XOR trick" more general?
- nromiun 1y agoEvery number on computers is converted to binary internally, so yes this works on decimal numbers too.
- fc417fc802 1y ago> so yes this works on decimal numbers too. Given that rounding tends to be necessary that seems extremely questionable in practice. Similar to how the equality operator in most (probably all) languages can be used with floating point numbers but in most cases that is a very bad idea.
- hyperhello 1y agoIntegers don’t have to be stored as floating point.
- fc417fc802 1y agoAnd yet a great many applications that use numbers with a decimal point will involve rounding and/or inexact matches.
- williamdclt 1y agoIt 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
- nullc 1y ago>the xor of 1 through n XOR[0...x] = (x&1^(x&2)>>1)+x*(~x&1) Of course, you don't have to do this with xor, you can do it with just addition (mod wordmax) and the well known identity attributed to gauss will support you.
- krior 1y agohttps://florian.github.io//xor-trick/ https://florian.github.io//xor-trick/ if you want detailed information and a list of possible applications.