Extending That XOR Trick to Billions of Rows

(nochlin.com)

54 points | by hundredwatt 3 days ago

3 comments

  • dataflow 5 hours ago
    Before 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.
  • dark-star 1 hour 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 1 hour ago
      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.

      • JPLeRouzic 46 minutes ago
        I know XOR only in the context of binary numbers. Is this "XOR trick" more general?
        • nromiun 30 minutes ago
          Every number on computers is converted to binary internally, so yes this works on decimal numbers too.