boost::container::static_vectorのような動作をする、容量の上限Nがコンパイル時に決められた値であり、実行時に配列の要素数sizeを（上限までの範囲で）変更できるようなデータ構造を考えます。これを実現するには最低何bitの空間が必要でしょうか？

要素一つ当たり必要なビット数を、Kbitだとします。

$N=0$ の場合

これは、自明に0bitで実現可能です。

$K=0$ の場合

これは、自明に $\lfloor \log_2(N+1) \rfloor$ bitです。配列の要素数sizeが0である場合、1である場合、……Nである場合、の $N+1$ 通りを区別する必要があるためです。

それ以外の場合で、 $2^K \ge N$ の場合

この場合、 $NK + 1$ bitで実現可能です。

まず、この値が下限値であることを示します。要素一つ当たりに必要なビット数がKbitで、最大N要素入りうるので $NK$ bitは確実に必要です。 N要素入っている状態は $\left(2^K\right)^N = 2^{NK}$ 状態あり、それ以外に0要素入っている状態が少なくともありますから、最低でも $2^{NK}+1$ 通りを区別する必要があります。 $NK$ bitでは $2^{NK}$ 通りの状態しか区別できませんので、最低でも $NK+1$ bit必要ということになります。

次に、実現する方法を示します。まず、一エントリがKbitであり、N要素ある配列を普通に用意します。これには $NK$ bitが費やされます。残りの1bitは、「sizeがNと等しい」ことを表すフラグにします。容量をケチるため、フラグの状態がtrueであるかfalseであるかによって、データ構造を変化させます。具体的には、以下のようにします。

フラグがtrueである、つまりsizeがNと等しい場合、用意した配列にsize個のKbitデータを詰め込む
フラグがfalseである、つまりsizeがNより小さい場合、用意した配列にsize個のKbitデータを詰め込む。配列の末尾にはsizeを書き込む

フラグがtrueである場合、問題が発生しないことはすぐにわかります。フラグがfalseである場合について少し補足します。

「配列の末尾には」となっていますが、sizeはNより小さいので、配列の末尾一エントリは使われていません。よって、必ず使えます。
「sizeを書き込む」となっていますが、sizeとしてあり得るのは0、1、……N-1のN通りなので、（二進数として書き込むことで）Kbitで足ります。

それ以外の場合

もし、要素数取得関数size()の時間計算量が定数である必要がある*1なら、以下のケチりテクニックは使えません。なくてもよいなら、上記と同じ $NK + 1$ bitで実現する方法があります。ただし、size()の時間計算量が定数でなくなるということからもわかるように、かなり非効率な実装となります。

まず、先と同じ議論により、 $NK+1$ bitが下限値であることはすぐにわかります。

実現する方法も、先の方法とおおよそ同じです。フラグがfalseの場合の議論が成り立っていないので、以下のように変更します。

フラグがfalseである、つまりsizeがNより小さい場合、用意した配列にsize個のKbitデータを詰め込む。使っていないエントリの先頭にtrueを、他のエントリにはfalseを書き込む

少し補足します。

「使っていないエントリの先頭に」となっていますが、sizeはNより小さいので、使っていないエントリは常に存在します。
「trueを」「falseを書き込む」となっていますが、 $K>0$ であるので、そのエントリはtrueとfalseを区別できるビット幅を持っていることが保証されます。ただし、タグなしunionという、かなり危険なコードを書く必要があります。
「ほかのエントリには」となっていますが、そのようなエントリがなければ何もする必要はありません。

このように書き込んだデータ構造を解釈するには、後ろから解釈する必要があります。前から解釈することは不可能です。

後ろから解釈する、というのはつまり、フラグ→配列の末尾→配列の末尾のその前→……という順番で確認していくということです。このように確認を進めていき、最初にtrueが書き込まれていた部分までに並んでいたfalseの数が、N-sizeに対応しています。つまり、sizeの情報が一進数で書き込まれているということになります。

別の解釈もできます。フラグを「trueなら配列にはN個の要素が書き込まれている、falseなら配列には『容量の上限がN-1の"この仕組み"のデータ構造』が書き込まれている」という切り替えフラグだと解釈すると、再帰的なデータ構造になっていることが確かめられます。基底ケース（N=0）ではfalseがあり得ないので常にtrueとなっていることとも整合します。

参考：要素としてあり得る状態が $2^K$ 通り未満である場合

この場合、きっかり $NK$ bitで実現可能です。その実例は、ヌル文字（NUL）終端文字列であり、文字列以外にも一般化可能です。

このように書き込んだデータ構造は、前から解釈することになります（一種の接頭符号になっています）。

size()の時間計算量が定数でないという特徴は似ていますが、前から解釈できる特徴により、コンパイル時に容量上限を決めなくてよいという利点があります。

*1:C++のSTLコンテナの要件。size関数を持たないコンテナも存在します（例えばstd::forward_list）

よーる

容量上限付き可変長配列の空間計算量

$N=0$ の場合

$K=0$ の場合

それ以外の場合で、 $2^K \ge N$ の場合

それ以外の場合

参考：要素としてあり得る状態が $2^K$ 通り未満である場合

の場合

の場合

それ以外の場合で、の場合

それ以外の場合

参考：要素としてあり得る状態が通り未満である場合

$N=0$ の場合

$K=0$ の場合

それ以外の場合で、 $2^K \ge N$ の場合

参考：要素としてあり得る状態が $2^K$ 通り未満である場合