Most operations on a computer are not reversible… meaning that once done, you can never go back. For example, if you divide integers by 2 to get a new integer, some information is lost (whether the original number was odd or even). With fixed-size arithmetic, multiplying by two is also irreversible because you lose the value of the most significant bit.

Let us consider fixed-size integers (say 32-bit integers). We want functions that take as input one fixed integer and output another fixed-size integer.

How many reversible operations do we know?

- Trivially, you can add or subtract by a fixed quantity. To reverse the operation, just flip the sign or switch from add to subtract.
- You can compute the exclusive or (XOR) with a fixed quantity. This operation is its own inverse.
- You can multiply by an odd integer. You’d think that reversing such a multiplication could be accomplished by a simple integer division, but that is not the case. Still, it is reversible. By extension, the carryless (or polynomial) multiplication supported by modern processors can also be reversible.
- You can rotate the bits right or left using the
`ror`or`rol`instructions on an Intel processor or with a couple of shifts such as`(x >>> (-b)) | ( x << b))`or`(x << (-b)) | ( x >>> b))`in Java. To reverse, just rotate the other way. If you care about signed integers, there is an interesting variation that is also invertible: the "signed" rotate (defined as`(x >> (-b)) | ( x << b))`in Java) which propagates the signed bit of two's complement encoding. - You can XOR the rotations of a value as long as you have an odd number of them.
- You can compute the addition of a value with its shifts (e.g.,
`x + ( x << a)`). This is somewhat equivalent to multiplication by an odd integer. - You can compute the XOR of a value with its shifts (e.g.,
`x ^ ( x >> a)`or`x ^ ( x << a)`). This is somewhat equivalent to a carryless (or polynomial) multiplication. - You can reverse the bytes of an integer (
`bswap`on Intel processors). This function is its own inverse. You can also reverse the order of the bits (`rbit`on ARM processors). - (New!) Jukka Suomela points out that you can do bit interleaving (e.g., interleave the least significant 16 bits with most significant 16 bits) with instructions such as
`pdep`on Intel processors. You can also compute the lexicographically-next-bit permutation.

You can then compose these operations, generating new reversible operations.

**Pedantic note**: some of these operations are not reversible on some hardware and in some programming languages. For example, signed integer overflows are undefined in C and C++.