0

私の修士論文の一部として、2つの重要なビット（2番目と4番目）を持つ数値（たとえば5ビット）を取得します。これは、たとえばx1x0x、$x \in {0,1}$（xは0または1）であり1,0、固定値のビットであることを意味します。

私の最初のタスクは、上記の数のすべての組み合わせを計算すること2^3 = 8です。これはS_1グループと呼ばれます。

次に、「S_2」グループを計算する必要があります。これは、2つの数値のすべての組み合わせでありx0x0x、x1x1x（これは、重要なビットの1つの不一致を意味します）、これにより、が得られ$\bin{2}{1} * 2^3 = 2 * 2^3 = 16ます。

編集 各番号x1x1xとは、元の番号とは1ビット大きくx0x0x異なります。x1x0x

最後のグループ、S_3はもちろん、重要なビットからの2つの不一致です。つまり、フォームを通過するすべての数値x0x1x、8つの可能性があります。

計算は再帰的または独立して計算できますが、これは問題ではありません。

私が持っているものはそれほど効率的ではないので、誰かがこれらの計算の出発点を与えることができれば幸いです。

編集多分私は重要なビット を使用して、私の言葉を間違って選択しました。私が言いたかったのは、5ビット数の特定の場所でビットが固定されているということです。私が特定のビットとして定義した場所。

編集 私はすでに2つの答えを見ました、そしてそれは私がもっと明確にすべきだったようです。私がもっと興味を持っているのは、数字を見つけることですx0x0x。これは単なる例です。実際には、グループ（この例では）は少なくとも12ビット長の数値で構築され、11個の有効ビットを含めることができます。それなら私は12のグループを持つでしょう...x1x1xx0x1xS_1x1x0x

それでも不明な点がある場合は、お問い合わせください;）

4

3 に答える 3

1 
#include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    string format = "x1x0x";

    unsigned int sigBits = 0;
    unsigned int sigMask = 0;
    unsigned int numSigBits = 0;
    for (unsigned int i = 0; i < format.length(); ++i)
    {
        sigBits <<= 1;
        sigMask <<= 1;
        if (format[i] != 'x')
        {
            sigBits |= (format[i] - '0');
            sigMask |= 1;
            ++numSigBits;
        }
    }

    unsigned int numBits = format.length();
    unsigned int maxNum = (1 << numBits);

    vector<vector<unsigned int> > S;
    for (unsigned int i = 0; i <= numSigBits; i++)
        S.push_back(vector<unsigned int>());

    for (unsigned int i = 0; i < maxNum; ++i)
    {
        unsigned int changedBits = (i & sigMask) ^ sigBits;

        unsigned int distance = 0;
        for (unsigned int j = 0; j < numBits; j++)
        {
            if (changedBits & 0x01)
                ++distance;
            changedBits >>= 1;
        }

        S[distance].push_back(i);
    }

    for (unsigned int i = 0; i <= numSigBits; ++i)
    {
        cout << dec << "Set with distance " << i << endl;
        vector<unsigned int>::iterator iter = S[i].begin();
        while (iter != S[i].end())
        {
            cout << hex << showbase << *iter << endl;
            ++iter;
        }

        cout << endl;
    }

    return 0;
}

sigMaskあなたの特定のビットがすべてあるところに1があります。 sigBits特定のビットが 1 changedBitsの場合は 1 になります。 の現在の値がiと異なる場合は 1 になりsigBitsます。 distance変更されたビット数をカウントします。これは、距離計算用のルックアップ テーブルを事前に計算しなくても得られる効率とほぼ同じです。

于 2011-02-22T19:34:40.977 に答える
0

もちろん、固定ビット値が実際に何であるかは問題ではなく、固定されていることだけが問題です。xyxyx、yは固定され、xは固定されていない場合、常に8つのポテンシャルが生成されます。それらの間で変化する2つのグループの潜在的な組み合わせは、y常に単純な乗算になります。つまり、最初のグループが存在する可能性のある状態ごとに、2番目のグループが各状態にある可能性があります。

于 2011-02-22T19:00:42.900 に答える
0

ビットロジックを使用します。

//x1x1x
if(01010 AND test_byte) == 01010) //--> implies that the position where 1s are are 1.

おそらく数論的な解決策がありますが、これは非常に簡単です。

これは、固定ビット整数型で行う必要があります。いくつかの動的言語（たとえばPython）は、それが良い考えだと思うなら、ビットを拡張します。

これは難しいことではありませんが、時間がかかるため、ここではTDDが特に適切です。

于 2011-02-22T19:12:26.910 に答える