News for hackers. Stuff that matters.
Re:How many reversible integer operations do you know? by rcthompson on Sunday January 14, 2018 @10:31AM (#16144632)
Since the domain and range of any integer operation are the same, the only way for such an operation to be reversible is if it maps every input to a different output. That means that the set of reversible integer operations is exactly the set of permutations on the integers (for a specified number of bits). So how many unique permutations are there for the set of 32-bit integers, which is a set of size 2^32? That would be (2^32)!, a very large number indeed.

Incidentally, multiplying by an odd integer works because when working in mod N space, multiplying by any number that is coprime with N yields a permutation, and since for 32-bit integers N = 2^32, the only prime factor of N is 2, which means that N is coprime with all odd integers. (I'm assuming unsigned integers and wrap-around behavior on over/underflow.)

There are no comments on this comment yet.