0
$\begingroup$

When you typically talk about binary strings, you basically say that they have $2^n$ values. So 10 is 2, 11111111 is 255, etc.

But this is based on how we use the string. What we are doing in that situation is "take all possible combinations of individual slots of alphabet $\{0,1\}$ as a single set". This gives us 256 possible values in an 8-bit string, etc..

We can also use it differently. Instead of saying "give me all the combinations of an $n$ length string", we can say "fill the values from left to right with 1, and use those as the set". So you have:

1
11
111
....
1...n

So if you only allow 8 slots, then you only have 8 unique values, as opposed to 256. So we can use the same system to encode two different amounts of numbers, or two different sets/ranges of values (8 vs. 256). This comes up when programming a lot. For example, you can only encode 8 flags into an 8-bit number, but 256 integers into an 8-bit number.

So this got me wondering if you can encode more than 256 values into an 8-bit number, or more generally, more than $2^n$ values in an $n$-bit number. But the catch is, you should also be able to get the values out of the string. More on that next.

In some sense you can have more digits in there, as in this.... Take every 1 digit number + 2 digit $2^2$ numbers + 3 digit $2^3$ numbers + 4 digit $2^4$ numbers + 5 digit $2^5$ numbers, + ... n digit $2^n$ numbers. I'm not sure the equation to calculate this final value, but it's more than 256, since 256 is simply the last number in the equation at $2^8$.

But the problem is I don't think you can get the values out of the string. At least it seems hard or that you can't.

The question is if there is actually a way to use these extra values we've squeezed out of the $n$-length string, so that we can store more information in that amount of space. The way this would look is, you might have $10101010$ be the ID of some record, while $101010$ is the ID of another record, which comes from 10101010. To take it further, instead of the value coming at the end of the bit string (which makes sense because that is how you sum the bit string value), you could put it in the middle, which gives you even more possible values. As in 10101010.

There is probably some math equation to calculate how many potential unique combinations/values there are like this, but I'm wondering if they exist such that you could also use them for unique encoding. That is, that you could encode 10101010 and 10101010 and 10101010 into the same 8-bit string, while still giving you at least (if not way more than) 256 values like the basic $2^n$ $n$-bit encoding.

If it's not possible, I'd like to know why.

$\endgroup$

closed as unclear what you're asking by JMoravitz, Servaes, lulu, Lord Shark the Unknown, Leucippus Feb 12 at 5:42

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ I'm confused. Since there are only $2^n$ length-$n$ binary strings, there's no possible way to represent elements of a $>2^n$-element set by length-$n$ binary strings in a recoverable way: if $\vert A\vert>\vert B\vert$, then any map from $A$ to $B$ is non-injective. Or are you asking something more complicated? $\endgroup$ – Noah Schweber Feb 12 at 0:18
  • 2
    $\begingroup$ Not sure I follow. Say the length is $2$. Are you suggesting that we consider $\emptyset, 0,1$ in addition to the strings of length $2$? But then of course you have more cases since you've added the length as a new bit of data. Or are you saying something else? $\endgroup$ – lulu Feb 12 at 0:19
0
$\begingroup$

You can only encode as many different values as you have different strings. If you allow strings from $0$ to $n$ bits there are $2^{n+1}-1$ of them, so you can encode that many values. You really should consider the string to have one more character which is a terminator because otherwise you don't know when the string is over. That is essentially the extra bit that gives twice as many strings.

$\endgroup$
  • $\begingroup$ I'm not convinced that you need an extra character. The abstraction certainly does not require it. An implementation may of may not. When it is needed, as in C, it will be much longer than a bit. $\endgroup$ – Ethan Bolker Feb 12 at 1:48
  • $\begingroup$ @EthanBolker: it depends on the implementation, but if you get $101$ how do you know to stop there instead of waiting for the next bit? It is similar to English words where the space following the word is the terminator. $\endgroup$ – Ross Millikan Feb 12 at 1:56
  • $\begingroup$ I think the fact that the need for an extra character is implementation dependent makes introducing it in an answer more confusing than helpful. The OP's question is (at least implicitly) about fixed length binary strings. $\endgroup$ – Ethan Bolker Feb 12 at 2:00
  • $\begingroup$ @EthanBolker: I don't think so. OP specifically mentions using strings of all lengths up to $n$. $\endgroup$ – Ross Millikan Feb 12 at 2:02

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