How to encode 3 integers into 2 integers?-CodePudding

I have three integers (x1,x2,x3) all in [0,255]. I need to encode them into two integers (a, and b) such that I can deterministically decode them back. The constraint is that the size of the new integers needs to be small. So I can do a=256*x1 x2, but this makes a much larger than xi.

Any way to encode integers such that the resulting numbers stay small? I am not defining what small is, as I want as small as possible.

A similar problem is to encode these 3 numbers into just 1. Again the new integer needs to be as small as possible. Any way to do this?

CodePudding user response：

Welcome to information theory / the pigeonhole principle. If you wish to encode x different values, you need to have enough bits to distinguish between x different things. In your case there are 256 = 2**8 possibilities (using ** for exponentiation) for each of x1, x2, and x3. Therefore there are 2**24 possibilities for the combination. Therefore you will need 2**24 combinations. So 24 bits.

Your first encoding can be achieved using 12 bit numbers in the range 0-4095. And your encoding can be done as follows (where % is the remainder operation and // is integer division, as they are in Python3):

a = (x1) * 256   x2
b = (x1//16) * 256   x2

with a decoding of:

x1 = (a//256)   (b//4096)
x2 = a%6
x3 = a%6

Encoding into 1 number again needs 2**24 possibilities, so that number needs to be in the range 0..16777215. And the encoding this time is:

c = x1   256*x2   65536*x3

with a decoding of

x1 = c%6
x2 = (c//256)%6
x3 = c//65536

There are various other encodings/decodings that you can achieve. But they can't be achieved with smaller ranges of numbers than that.

CodePudding user response：

The first observation is that in general this cannot be done. It would be nice to store three bytes in only two bytes. But that does not work. If the ranges of x1, x2, x3 are 0..255, you actually need 8 bit for each of them. So in total you have 24 bits of data. If you want to store x1, x2, x3 in only two numbers, these must be both 12 bit numbers. Which means, a and b must both be in range 0 .. 4095. One such operation is for example as follows.

    0 -> 0 
    1 -> 1
    2 -> 2
x1  3 -> 3
    4 -> 4
    5 -> 5
    6 -> 6
___ 7 -> 7   a
    0 -> 8
    1 -> 9
    2 -> 10
    3 -> 11 ___
x2  4 -> 0
    5 -> 1
    6 -> 2
___ 7 -> 3   b
    0 -> 4
    1 -> 5
    2 -> 6
    3 -> 7
x3  4 -> 8
    5 -> 9
    6 -> 10
    7 -> 11

The formula for extracting the lower 4 bits is the rest of the division by 16. The formula for extracting the upper 4 bits is the division without the rest. Moving bits to the correct position is a multiplication by a power of 2. With these operations or with bit shift operations, the conversion can be implemented in a programming language or tested in Excel.

I recommend you to play a bit around with the Windows calculator or a similar tool. This can convert integer numbers from decimal into the binary format and back. Then you get a feeling how numbers are represented and what the bits mean. And you can try out all these operations.

A more effective way of doing this is impossible in general. The ranges for a and b must be bigger than the ranges of the x values. So that may be the end of the game.

In real live there are sometimes situation where you can compress data. If you for example know that your numbers are never odd, then you don't have to store the bit number 0. If you for example know that x1 is always bigger than 31 but never in the range 80..180, then this means you have for x1 only these possible situations: 32..79, 161..255. These are only 123 values. If you for example know that one of x1,x2,x3 is always zero, then you have to store only two of them. In all these cases you may not need always 8 bits for representing this.

If you find enough such properties of you numbers, it may be possible that you can encode x1, x2, x3 in a,b of the range 0..255. But this is only a very special situation and hypothetical as we don't know even your use case. I normally would not expect that you could achieve satisfactorily what you asked for.