вычисление перестановки определенных битов в числе

В рамках моей магистерской работы я получаю число (например, 5 бит) с двумя значащими битами (2-й и 4-й). Это означает, например, x1x0x, где $x \in {0,1}$ (x может быть 0 или 1) и 1,0 — биты с фиксированными значениями.

Моя первая задача — вычислить все комбинации приведенного выше числа 2^3 = 8. Это называется S_1 группа.

Затем мне нужно вычислить группу «S_2», а это все комбинации двух чисел x0x0x и x1x1x (это означает одно несовпадение в значащих битах), это должно дать нам $\bin{2}{1} * 2^3 = 2 * 2^3 = 16.

ИЗМЕНИТЬ Каждое число, x1x1x и x0x0x, отличается от исходного числа, x1x0x, одним значащим битом.

Последняя группа, S_3, это, конечно же, два несовпадения из значащих битов, это означает, что все числа, которые проходят форму x0x1x, 8 возможностей.

Вычисление может быть выполнено рекурсивно или независимо, это не проблема.

Я был бы рад, если бы кто-то мог дать отправную точку для этих вычислений, поскольку то, что у меня есть, не так эффективно.

ИЗМЕНИТЬ Возможно, я неправильно выбрал слова, используя значащие биты. Я хотел сказать, что определенные места в пятибитном числе фиксированы. Эти места я определил как конкретные биты.

EDIT Я видел уже 2 ответа, и кажется, что я должен был быть более ясным. Что меня больше интересует, так это нахождение чисел x0x0x, x1x1x и x0x1x с учетом того, что это просто пример. На самом деле группа S_1 (в данном примере x1x0x) должна состоять из не менее чем 12-битных чисел и может содержать 11 значащих битов. Тогда у меня было бы 12 групп...

Если что-то по-прежнему непонятно, спрашивайте ;)


c++ hamming-distance permutation combinatorics
person Eagle    schedule 22.02.2011    source источник
comment
Я могу не понять, но если второй и четвертый биты значимы, разве третий бит тоже не значителен?   -  person John    schedule 22.02.2011
comment
Итак, вы хотите получить количество перестановок, соответствующих вашим ограничениям, или их список?   -  person Argote    schedule 22.02.2011
comment
Я на самом деле не понимаю вопроса. Какова реальная конечная цель всего этого?   -  person Puppy    schedule 22.02.2011
comment
Согласно вашему определению, число x0x0x будет отличаться от числа x1x1x на 2 значащих бита, но вы говорите, что это означает наличие одного несоответствия в значащих битах. Что неправильно?   -  person recursive    schedule 22.02.2011
comment
@Argote, 3 группы могут быть вычислены одновременно. В конце должно получиться, что 32 возможных числа (5 бит) будут помещены в правильные группы.   -  person Eagle    schedule 22.02.2011

Ответы (3)


arrow_upward
1
arrow_downward 

#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 везде, где ваши конкретные биты равны 1. changedBits имеет 1 везде, где текущее значение i отличается от sigBits. distance подсчитывает количество измененных битов. Это настолько эффективно, насколько это возможно без предварительного расчета таблицы поиска для расчета расстояния.

person Karl Bielefeldt    schedule 22.02.2011
comment
мне понравилась идея, но sigBits и sigMask тоже нужно вычислить... вопрос в том, как мне это сделать, когда я знаю только x1x0x? - person Eagle; 22.02.2011

arrow_upward
0
arrow_downward

Конечно, на самом деле не имеет значения, каковы значения фиксированных битов, важно только то, что они фиксированы. xyxyx, где у фиксировано, а х нет, всегда будет давать 8 потенциалов. Потенциальные комбинации двух групп, где y варьируется между ними, всегда будут простым умножением, то есть для каждого состояния, в котором может находиться первая, вторая может находиться в каждом состоянии.

person Puppy    schedule 22.02.2011

arrow_upward
0
arrow_downward

Используйте битовую логику.

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

Вероятно, есть теоретико-числовое решение, но оно очень простое.

Это необходимо сделать с помощью целочисленного типа с фиксированным разрядом. Некоторые динамические языки (например, Python) будут расширять биты, если сочтут это хорошей идеей.

Это несложно, но отнимает много времени, и TDD здесь был бы особенно уместен.

person Paul Nathan    schedule 22.02.2011