0

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?

3
  • 1
    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.
    – Erik Eidt
    Aug 11, 2016 at 17:42

1 Answer 1

3

The possible bit patterns for a 64 bit signed integer are exactly the same as the possible bit patterns for a 64 bit unsigned integer. So, you can just encode each bit pattern to the same output that you would encode it to if it were the bit pattern of an unsigned integer. In other words: just add 263 before encoding and subtract after decoding.

Actually, after looking at the link you provided, it's just base conversion. You can represent negative numbers in any base using the same "trick" that two's complement uses.

2
  • If I understand you correctly, you are refering to a similar approach that Base64 is using (dividing the input into groups and mapping each group to a character). I think this approach is only effective if the size of your alphabet is a number to the power of two. E.g. when you have 64 available characters, you can divide the input into groups of 6 bit, when you have 32 characters, the groups have 5 bits and so on. In my case, the size of the alphabet is only known at runtime. EDIT: I will think about your edit, but that could take a while ;)
    – ceran
    Aug 11, 2016 at 14:57
  • No, you can convert numbers to any base you want. In fact, in source code, you normally write numbers in base 10, which is not a power-of-two and the compiler converts that into base 2, and then when printing it back out again, it converts it back into base 10, all without loss of information. Aug 11, 2016 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.