When encoding a sequence of bits into a string (using an alphabet that is not yet known at compile time and with the goal that the resulting string is as short as possible and that this whole process is reversible), you can use the "divmod approach", see e.g. this post.
From my understanding, this appraoch only works for positive numbers. In my case, I want to encode 64 bit signed integers (Java's
Long), so the numbers can be both positive and negative.
So far, I've been using a "trick" to ensure all numbers are positive by adding two new bits: I just set the 65th bit to 1 and the 66th bit to 0. This means that positive numbers stay positive and negative numbers become positive (because the leading ones of the two's complement are obliterated). However, this approach has two disadvantages:
- I need to use a
BigIntsince 64 bits are not enough anymore.
- Since the 65th bit is always 1, the resulting strings are of course not as short as possible.
What else could I do to encode a 64bit signed integer? Is there a variant of the "divmod aprroach" that works with signed numbers?