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 and the inverse can be computed efficiently. 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. Reynolds describes how to invert the result.
- 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.

**Related:** Quite some time after I wrote this post, Reynolds came up with a super nice version that reviews many similar techniques.

**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++.

Is the x86-64 CRC instruction reversible on 32-bit unsigned integers?

Good question. I suspect that it is equivalent to a 32-bit carryless multiplication with 0x1edc6f41, an invertible transformation. There is also a bit reversal (bit reflection), also invertible.

aesenc

Hrm.

How many of these operations are reversible for all integer inputs?

I’d definitely not consider shifts reversible. I’d probably not even consider addition/subtraction reversible as they aren’t reversible for all inputs. They’re “sometimes reversible” but not “always reversible”.

They are always invertible, for all integer inputs. There are programming-language issues that may interfere, such as undefined behaviors under overflow for signed integers, but they are technical issues.

Encryption is reversible, although often an IV or other padding are added. Do you think most encryption methods, or at least those that don’t require any more bits for the encrypted output, can be implemented using only the ‘primitives’ you listed?

I would be very interested in knowing whether some encryption techniques use primitives we did not include.

I guess you’re looking for operations which (maybe holding some arguments fixed) take an intX_t to an intX_t (not a larger type)?

Right. If you are allowed to generate larger types, then it is a bit too easy.

Taking the int to be a vector over Z_2, multiplication by a square non-singular matrix over Z_2.

How many?

Zero, I don’t give a sh*t…

A function mapping from {1, …, 2^n} to {1, …, 2^n} is reversible if and only if it is a one-to-one mapping. Any such mapping f(x) can be represented by the sequence (f(1), â€¦, f(2^n)). There are (2^n)! such one-to-one sequences. That is, the reversible functions are simply permutations (shufflings) of the numbers from 1 to 2^n. For example, if n = 2, there are (2^2)! = 4! = 24 reversible functions.

How many reversible operations do we know? For 32 bit integers, we know (2^32)! reversible operations.

I guess what you really want to know is, how many of these reversible operations are easy to define? I suppose circuit complexity might be the natural way to define “easy” reversible functions (https://en.wikipedia.org/wiki/Circuit_complexity). If you specify a precise measure of circuit complexity and set a threshold on circuit complexity, there would be an exact answer to the question of how many of the (2^32)! reversible functions have a complexity below the given threshold. However, calculating the exact answer is likely to be very time consuming.

This seems like a rather easy question. Did I miss something? All of these (2^32)! functions could be defined with NOR.

As you point out, there are 2^64 ! permutations on 64-bit words, and that’s about 2^64^{2^64} permutations. To identify one of them, I need about 2^{70} bits. We are talking about exabytes. So it is not practical to address reversible functions as an element of the set of all permutations.

I submit to you that this set might as well be infinite.

In practical software, we see a tiny fraction of all these reversible functions. The question is which ones do we commonly see?

What motivates this question? Why is this interesting? Are you trying to reduce energy consumption below the von Neumann-Landauer limit?

https://en.wikipedia.org/wiki/Reversible_computing

If I asked a programmer to write a reversible function over machine words… I’d get examples from the above blog post… plus, maybe, some minor variations. There are only so many ways to write reversible functions in software today. This comes from the fact that we work with a fairly limited set of operations.

Some of them are not immediately obvious. For example, XORing an odd number of rotations is invertible… but not an even number.

Why would anyone care about this? Well… these are used all over… to generate random numbers, to hash numbers and so forth.

Bitwise not ~

That’s just an instance of XOR with a constant

Rotate needs a tweak: (x >>> (32-b)) | ( x << b)

Mr Pedant: Care to explain?

If you are working with ints in Java, then

(x >>> (32-b)) | ( x << b)is strictly equivalent to(x >>> (-b)) | ( x << b). For longs, you have that(x >>> (64-b)) | ( x << b)is strictly equivalent to(x >>> (-b)) | ( x << b). So, the better form is(x >>> (-b)) | ( x << b)because it works the same no matter which words you are using.In C, it is a different matter because it has undefined behaviors. Java does not.

Oops, my mistake, you are correct.

TIL In Java, the >>> operator masks the shift amount by 31.

It virtually masks the shift, yes. In reality, at least on an Intel processor, there is no shift needed since the machine instruction only uses the least significant bits during a shift.

It is not just Java. Go, JavaScript… also work the same way.

Oh sure, I’m familiar with the x86 assembly opcodes SAR and SHR. It’s just surprising to see that limitation of a particular CPU reflected in a high level language.

My assumption was that in a high level language ((x >>> a) >>> b) === (x >>> (a+b))

And indeed, in python that is the case:

python -c “print (2**65537)>>65536” # == 2

‘Go’ seems to work the same

fmt.Println(7 >> 65536) // == 0

Source: https://golang.org/ref/spec https://golang.org

Java/Javascript OTOH? My mistake… TIL.

Here are a couple of odd ones, based on TBM. x + c * (x & -x) with an even c, which is invertible because it doesn’t change what x&-x is so the same amount can be subtracted again. Of course the addition can be replaced with XOR. Here’s “proof” (not really, but I believe the bot) for c=2, http://haroldbot.nl/?q=let+c+%3D+2%2C+y+%3D+x+%2B+c+*+%28x+%26+-x%29+in+y+-+c+*+%28y+%26+-y%29 (dev version can handle unbound c)

x + c * ((x ^ (x + 1)) + 1) seems to work for any c (if I believe the bot), for a similar reason.

I can’t think of a use for them, but I found them interesting because they don’t just add a constant, but something that can be recovered.

Seems worth explicitly noting that the inverse of multiply by odd K is the product by its modulo inverse.

I wonder if there is there any accessible coverage of bijections as properties of F_2 matrices.

Feistel permutations, as used in “Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation”: https://arxiv.org/abs/0912.5424

What is the inverse of x+ (x<<a)?

We have that

x + (x << a)is(1 + (1<. That is, we have a multiplication by an odd integer. Multiplication by an odd integer is an invertible operation modulo a power of two. Please see this follow-up post for details: https://lemire.me/blog/2017/09/18/computing-the-inverse-of-odd-integers/Thank You

As presented, the signed-shift-based rotation isn’t reversible, but a similar one is, and I’m guessing there was just a transcription error.

`(x >> b) | (x << (-b))`

produces`-1`

whenever`b == -1`

(or 63 for Java`long`

, 31 for Java`int`

) and`x`

is any negative number. But,`(x << b) ^ (x >> (-b))`

is reversible (using XOR instead of OR, and also using the structure of a left rotation, so let’s call this a signed-left-rotation). If you take the result`r`

of an earlier signed-left-rotation and you know the rotation amount`b`

, then`long n = (r >>> b) | (r << b); n ^= ((n >> -1) >>> b);`

will have`n == x`

for, as far as I can tell, any`x`

. This starts to reverse the signed-left-rotation using a typical right-rotation, then if that is a negative number, it flips the lowest`b`

bits, which completes the reversal. If I’m wrong on any of this, please let me know! There could easily be a cleaner way to do this but I don’t know what it would be.Oops, reversal code should be

`long n = (r >>> b) | (r << -b); n ^= ((n >> -1) >>> b);`

. There’s my own transcription error; I had used`Long.rotateRight(r, b)`

in my test code.I should also mention that, like xor-shift, a xor-based rotation can’t use a rotation amount of 0 (after modulo by the number of bits in type). One way around this is to special-case rotations by 0, and their reversals (Java code):

`long signedLeftRotate(long x, int b) { return (x << b) ^ (x >> (-b)) | (x & (~((-(b & 63)) >> -1))); }`

and`long reverseSignedLeftRotate(long x, int b) { long n = (x >>> b) | (x << (-b)); return n ^ (((n >> -1) >>> b) & ((-(b & 63)) >> -1)); }`

These return

`x`

if`b`

is 0, but they’re a substantial amount of extra operations to avoid a possible branch.