Comment

Comment by throwaway080383

As others have pointed out, there are (2^32)! such operations on 32-bit ints. However, I think it can be shown that the Kolmogorov complexity of most of these has to be

O(lg((2^32)!))

which I think is rougly 32*2^32.

In other words, you'd need about 16GB just to store the program to compute the permutation! Of course, that is not the case for the operations shown here.

So maybe implicitly the real question is, "How many reversible integer operations do you know with small Kolmogorov complexity?" Or in more practical terms, "How many reversible integer operations do you know which don't require too many lines of code?"

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton