вычисление перестановки конкретных битов в числе - PullRequest
Новая
       23

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

0 голосов
/ 22 февраля 2011

Как часть моей магистерской диссертации, я получаю число (например, 5 бит) с 2 значащими битами (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 возможностей.

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

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

РЕДАКТИРОВАТЬ Возможно, я неправильно выбрал слова, используя значащие биты .Что я хотел сказать, так это то, что определенные места в пятибитном числе бит фиксированы.Те места, которые я определил как конкретные биты .

РЕДАКТИРОВАТЬ Я видел уже 2 ответа, и кажется, что я должен был быть более ясным.Что меня больше интересует, так это нахождение чисел x0x0x, x1x1x и x0x1x с учетом того, что это просто пример.В действительности, группа S_1 (в этом примере x1x0x) должна быть построена с номерами длиной не менее 12 бит и может содержать 11 значащих битов.Тогда у меня будет 12 групп ...

Если что-то все еще не ясно, спросите;)

Ответы [ 3 ]

1 голос
/ 22 февраля 2011 
#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 подсчитывает количество битов, которые изменились.Это примерно так же эффективно, как вы можете получить без предварительного расчета таблицы поиска для расчета расстояния.

0 голосов
/ 22 февраля 2011

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

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

Возможно, существует теоретико-числовое решение, но это очень просто.

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

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

0 голосов
/ 22 февраля 2011

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

...