0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Just a note, $11111111111111111111111111111111 = 2^{32}-1$, not $2^{32}$. $\endgroup$ – kccu Jan 11 at 14:31
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For certain large numbers which cannot be represented by control characters, we can represent the number as-is, which still could be less than 32 bits. $\endgroup$ – usrso Jan 11 at 15:50
  • 1
    $\begingroup$ I'm not sure what you're trying to say. Nonetheless you are trying to label $2^{32}$ objects with $2^{32}-1$ labels, so there is no way to do it without repeating a label. $\endgroup$ – kccu Jan 11 at 16:49
0
$\begingroup$

Put simply, no. There is no 'more compact' way to represent binary numbers - else we would be using it. With $32$ bits, you have $2^{32}$ combinations, and hence you can represent that many numbers. Moreover, representing $2^{32}$ different numbers requires $32$ bits, as we want a one-to-one function.

Think about it this way: if you have only $n$ bits, you have $2^{n}$ binary strings. How can you possibly represent more than $2^{n}$ numbers with only $2^{n}$ strings? This would require some strings to represent more than $1$ number, but we're looking for an injection for the binary representation to be at all meaningful.

If you try and use control characters like you've done, you'll notice that the "compacted" strings are equivalent to other valid binary strings, which illustrates the paradox that certain strings would have to map to more than one number.

$\endgroup$
  • $\begingroup$ For certain large numbers which cannot be represented by control characters, we can represent the number as-is, which still could be less than 32 bits. $\endgroup$ – usrso Jan 11 at 15:50
  • $\begingroup$ @usrso I don't think you understand the most important underlying principle: it's impossible to represent more than $2^{32}$ different numbers with only $2^{32}$ possible states. It just doesn't make sense. $\endgroup$ – FlipTack Jan 11 at 17:41
  • $\begingroup$ I think the scale we're talking on might be confusing you. Try it with 3 bits. Write the numbers 0-7 and their binary representations. Then try and represent any new number with any 'control character' system you're imagining, in 3 bits; you'll see that you've already used that combination before. $\endgroup$ – FlipTack Jan 11 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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