Multiway trieの子ノードを配列表現することで，木構造における子ノードへのリンク（ポインタ）のメモリ使用量を削減しました。しかし，このままでは，要素数2^kのinternal nodeの配列とleaf nodeの配列をそれぞれ持つ必要があり，メモリ効率が非常に悪いです。internal nodeとleaf nodeは排他であるため，必ずどちらかが無駄になります。

そこで，Poptrieでは，子ノードがinternal nodeかleaf nodeかを表すビット列（vector）を応用することで，子ノード配列圧縮します。下図のように，vectorが0100のとき，internal node配列の要素数は1，leaf node配列の要素数は3になります。そして，配列のインデックスはそれぞれ，多分木の探索キーに対応するビット以下のビットの1の数から1を引いた数 および 多分木の探索キーに対応するビット以下のビットの0の数から1を引いた数 として表現することができます。これにより，子ノード配列から空のノードを排除することができ，データ構造を圧縮できます。

Poptrieでは，この1の数や0の数を高速に数えるのにpopcnt命令を使用しています。popcnt命令は，オペランド（ビット列）の1であるビットの数を数える命令です。ビット演算を組み合わせることで，上述のあるビット以下の1の数や0の数を数えることができます。

具体的には，多分木の探索キーをNとしたとき，internal node配列およびleaf node配列の対応するインデックスは，

popcnt( (2 << N) - 1) & vector ) - 1 // if ((1 << N) & vector) == 1

および

popcnt( (2 << N) - 1) & ~vector ) - 1 // if ((1 << N) & vector) == 0

となります。