computing permutation of specific bits in a number

Question

As part of my master thesis, I get a number (e.g. 5 bits) with 2 significant bits (2nd and 4th). This means for example x1x0x, where $x \in {0,1}$ (x could be 0 or 1) and 1,0 are bits with fixed values.

My first task is to compute all the combinations of the above given number , 2^3 = 8. This is called S_1 group.

Then I need to compute 'S_2' group and this is all the combinations of the two numbers x0x0x and x1x1x(this means one mismatch in the significant bits), this should give us $\bin{2}{1} * 2^3 = 2 * 2^3 = 16.

EDIT Each number, x1x1x and x0x0x, is different from the Original number, x1x0x, at one significant bit.

Last group, S_3, is of course two mismatches from the significant bits, this means, all the numbers which pass the form x0x1x, 8 possibilities.

The computation could be computed recursively or independently, that is not a problem.

I would be happy if someone could give a starting point for these computations, since what I have is not so efficient.

EDIT Maybe I chose my words wrongly, using significant bits. What I meant to say is that a specific places in a five bits number the bit are fixed. Those places I defined as specific bits.

EDIT I saw already 2 answers and it seems I should have been clearer. What I am more interested in, is finding the numbers x0x0x, x1x1x and x0x1x with respect that this is a simply example. In reality, the group S_1 (in this example x1x0x) would be built with at least 12 bit long numbers and could contain 11 significant bits. Then I would have 12 groups...

If something is still not clear please ask ;)

Answer 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 has a 1 where all your specific bits are. sigBits has a 1 wherever your specific bits are 1. changedBits has a 1 wherever the current value of i is different from sigBits. distance counts the number of bits that have changed. This is about as efficient as you can get without precomputing a lookup table for the distance calculation.

Answer 2

Of course, it doesn't actually matter what the fixed-bit values are, only that they're fixed. xyxyx, where y is fixed and x isn't, will always yield 8 potentials. The potential combinations of the two groups where y varies between them will always be a simple multiplication- that is, for each state that the first may be in, the second may be in each state.

Answer 3

Use bit logic.

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

There's probably a number-theoretic solution, but, this is very simple.

This needs to be done with a fixed-bit integer type. Some dynamic languages (python for example), will extend bits out if they think it's a good idea.

This is not hard, but it is time consuming, and TDD would be particularly appropriate here.