# Encoding a signed number using a custom alphabet

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:

1. I need to use a `BigInt` since 64 bits are not enough anymore.
2. 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?

• Your question suffers quite a bit from the X Y problem: rather than asking about the problem you're trying to solve, you're asking about your attempted solution to the unstated problem. What is the actual problem you're trying to solve? Aug 11, 2016 at 14:47
• According to the link you posted, you are essentially looking to do base conversion. That's a problem that has been well understood and solved for probably hundreds of years now. I'm confused why you think base conversion cannot be done with negative numbers? You can write down negative numbers in multiple bases just fine. Aug 11, 2016 at 14:57
• As @JörgWMittag says, 64-bit number can be encoded the same way regardless of whether you consider the number signed or unsigned, it is still just 64-bits of information. What you can't do is decode the 64-bit number and know whether the intended format was meant to be interpreted as unsigned vs. signed -- that would take an extra bit of information (in other words you'd need to support a relatively non-standard 65-bit signed numbers). You can, though, treat all numbers as 64-bit signed and thus know whether the number was positive or negative. So, just decide how many bits you need. Aug 11, 2016 at 17:42