# How many reversible integer operations do you know?

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?

1. Trivially, you can add or subtract by a fixed quantity. To reverse the operation, just flip the sign or switch from add to subtract.
2. You can compute the exclusive or (XOR) with a fixed quantity. This operation is its own inverse.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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).
9. (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++. ### Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

## 31 thoughts on “How many reversible integer operations do you know?”

1. Jim Apple says:

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

1. Daniel Lemire says:

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.

2. Snobby says:

aesenc

3. Cecil says:

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”.

1. Daniel Lemire says:

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.

4. Jonathan Graehl says:

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?

1. Daniel Lemire says:

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

5. David Tweed says:

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)?

1. Daniel Lemire says:

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

6. Jim Apple says:

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

7. jld says:

How many?
Zero, I don’t give a sh*t…

8. Peter Turney says:

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.

1. Daniel Lemire says:

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?

1. Daniel Lemire says:

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.

9. toa says:

Bitwise not ~

1. harold says:

That’s just an instance of XOR with a constant

10. Mr Pedant says:

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

1. Daniel Lemire says:

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.

1. Mr Pedant says:

Oops, my mistake, you are correct.
TIL In Java, the >>> operator masks the shift amount by 31.

1. Daniel Lemire says:

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.

1. Mr Pedant says:

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.

11. harold says:

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.

12. Marc Reynolds says:

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.

13. Jim Apple says:

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

14. Sid says:

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

1. Sid says:

Thank You

15. Tommy Ettinger says:

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.

16. Tommy Ettinger says:

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.

17. Tommy Ettinger says:

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.