Encoding two numbers in a 4-bit binary string

Question

For example, I have two numbers ranging from 0 to 15. And I wonder if there is any way to encode these two numbers in just 4-bit binary string (or possibly 5-bit)? It is known that 4 bits are needed to represent any single number from 0 to 15, but maybe you could think of your own operation on binary strings, and then recover the input numbers back from the result. For example, if I add 0010 + 1011 as standard, I get1101. But with the result of adding it is impossible to predict the components of the sum completely and unambiguously. Cases would have to be considered. But maybe some other own defined action? Was anyone wondering about something like that?

I know that the above question may not meet some portal conditions, but treat this question purely abstractly :)

There are 2^7 possibilities and you want to represent all of them in 2^4 states? — Pham Trung
– Pham Trung, Commented Feb 20, 2018 at 10:47
2^4 < 16 + 16, it's impossible to fit the information into 4 bits. 2^5 bits have the required range, you just need to decide on the right encoding. — deceze
– deceze ♦, Commented Feb 20, 2018 at 10:48
Use a predefined mapping. Then you can define 16 different pairs of numbers, each one in the range of (0..15,0..15). For reasons mentioned above, you cannot encode all possible ranges. What you ask is quite like "I can write on one side of a page and on the other. Is there a third side?" — Jongware
– Jongware, Commented Feb 20, 2018 at 10:51
@deceze how to represent two 4-bit binary numbers by just 5 bit? for example (0101 and 1100), considering there are 16*16/2 unique pairs? — Pham Trung
– Pham Trung, Commented Feb 20, 2018 at 10:51

Imran · Accepted Answer · 2018-02-20 13:37:10Z

2

You need at least 8 bits to encode two numbers from 0 to 15. This is because you have (2^4)*(2^4) = 2^8 possible inputs (or 2^7 if order does not matter), and by the pigeonhole principle any encoding you use that is less than 8 (or 7) bits will result in a collision, making it impossible to reconstruct your inputs in all cases.

To encode two 4-bit numbers into 8-bits just concatenate them:

def encode(x,y):
    return (x << 4) + y

And to decode just read the appropriate bits:

def decode(z):
    return z >> 4, z & 0xF

Demo:

>>> encode(11,12)
188
>>> decode(188)
(11, 12)
>>>

And if you want to convert to and from a binary string in between you can do:

>>> bin(188)
'0b10111100'
>>> int('0b10111100', 2)
188

edited Feb 20, 2018 at 13:37

answered Feb 20, 2018 at 11:18

Imran

13.6k8 gold badges69 silver badges82 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

javidcf · Accepted Answer · 2018-02-20 13:50:09Z

0

(...) maybe you could think of your own operation on binary strings, and then recover the input numbers back from the result.

No, that is not possible if you are using the same number of bits for both the operands and the result. See, for example, with 4 bits, like you say, you have 16 possible values, from 0 to 15. If you define a binary operation, assuming it is commutative (otherwise it would be even harder), the number of 2-combinations of those 16 elements (the number of possible pairs of inputs) is 120, and that is without even counting the 16 extra possibilities of using the same input twice. Hence, if you only have 16 possible values in your result, on average every possible result will correspond to between 7 and 8 possible pairs of inputs. No matter what operation you define, you would need at least 7 bits in your result to be able to reconstruct the input.

Another question is whether you can determine the set of potential inputs that produced some results. That corresponds to the concepts of number partitioning for addition or integer factorization for multiplication, for example.

answered Feb 20, 2018 at 13:50

javidcf

59.9k7 gold badges87 silver badges134 bronze badges

1 Comment

javidcf Over a year ago

Or, in other words, you are basically trying to encode more than 4 bits within 4 bits, which obviously is not gonna work.

Collectives™ on Stack Overflow

Encoding two numbers in a 4-bit binary string

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related