数え上げ符号

数学・アルゴリズム

NビットのうちM個が'1'となる符号を考えましょう。このような符号の列挙を『数え上げ符号』といいます。研究でこれが必要になったのだけど、実装例がやたら少なくて少々困ってもうた。少ない資料を基にエンコード・デコードを書いたので貼っておきます。どうぞご参考に（責任はとりません）。

const int L=16;//コードワード長。32bitsだと17あたりが組み合わせ数の限界？。

//可能であればルックアップテーブル化がオススメ
inline unsigned int choose(unsigned int n,unsigned int r)
{
    return (n>=r)?comb(n,r):0;
}
//エンコード（x:コードワード、r:1の数）
unsigned int enumerate(unsigned int x,int r)
{
    unsigned int y=0;
    for(int k=L-1;k>=0;k--)
        if((x>>k)&1)
            y+=choose(k,r--);
    return y;
}
//デコード（y:数え上げ符号、r:1の数）
unsigned int enumerateInv(unsigned int y,int r)
{
    unsigned int x=0;
    for(int k=L-1;k>=0;k--)
    {
        if(y<choose(k,r))
            continue;
        x|=(1<<k);
        y-=choose(k,r);
        r--;
    }
    return x;
}

ただし、comb(n,r)は組み合わせの数を返す関数です。引数の値が小さいのであれば、comb()やchoose()はテーブル参照に置き換えた方が断然高速です。ちゃんとした測定はしてませんが、処理時間が半分近くに減少しました。

参考資料