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

Published by

Daniel Lemire

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

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

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

      Reply

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

    Reply

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

      Reply

  4. 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?

    Reply

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

    Reply

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

    Reply

    1. 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?

      Reply

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

      Reply

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

      Reply

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

          Reply

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

            Reply

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

    Reply

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

    Reply

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

    Reply

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

    Reply

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

    Reply

Leave a Reply to Daniel Lemire Cancel reply

Your email address will not be published.

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks: 

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax

Or, you can subscribe without commenting.

You may subscribe to this blog by email.