Can we represent a binary number in a compact binary form.
For example
4294967295 (decimal) -> 11111111111111111111111111111111 (binary, 32 bits)
Can we represent this binary value in a compact binary form. i.e. less than 32 bits?
Are there ways to do stuff like representing the number in powers of 2, or setting control bits, or bit packing etc, with the resulting binary bits less than 32?
So,
11111111111111111111111111111111 (binary, 32 bits) = 2^32 - 1
would be compacted to, say, for example
101111111 (binary, 9 bits)
where the last 2 bits (MSB – 10) represent 2 and next 5 bits (11111) represent 32, next 1 bit (1) represents "-" (negative operation) and next 1 bit (1) represents 1.
Similarly,
00000000000000000000000000010011 (binary, 32 bits) = 2^4 + 3
would be compacted to, say, for example
10100011 (binary, 8 bits)
where the last 2 bits (MSB – 10) represent 2, next 3 bits (100) represent 4, the next bit (0) represents "+" (addition) and the next 2 bits (11) represents 3.
Can we do this for whole range of numbers from
00000000000000000000000000000000 (binary, 32 bits) to
11111111111111111111111111111111 (binary, 32 bits)
with each resulting number to be less than 32 bits?
Note: It is not restricted to 32 bits. We can even consider 64 bits or 128 bits or larger than that.
Thanks.
Best Answer
I'm assuming you want the "compact form" to be unique, meaning there is some unique way to recover the original number from the compact form. In this case, you are looking for an injective function from the set $\{0,1,\dots,2^{32}-1\}$ to the set of binary strings with less than $32$ bits. The domain has cardinality $2^{32}$, while the codomain has cardinality $2+2^2+\cdots+2^{31} = 2^{32}-1$. Hence no injective function can exist.