Fastest way to calculate possible values of unsigned int with N unreliable bits?

Question

Given an unsigned int A (32 bit), and another unsigned int B, where B's binary form denotes the 10 "least reliable" bits of A, what is the fastest way to expand all 1024 potential values of A? I'm looking to do this in C.

E.g uint B is guaranteed to always have 10 1's and 22 0's in it's binary form (10 least reliable bits).

For example, let's say

A = 2323409845  
B = 1145324694

Their binary representations are:

a=10001010011111000110101110110101

b=01000100010001000100010010010110

B denotes the 10 least reliable bits of A. So each bit that is set to 1 in B denotes an unreliable bit in A.

I would like to calculate all 1024 possible values created by toggling any of those 10 bits in A.

Answer 1

You can iterate through the 1024 different settings of the bits in b like so:

unsigned long b = 1145324694;
unsigned long c;

c = 0;
do {
    printf("%#.8lx\n", c & b);
    c = (c | ~b) + 1;
} while (c);

To use these to modify a you can just use XOR:

unsigned long a = 2323409845;
unsigned long b = 1145324694;
unsigned long c;

c = 0;
do {
    printf("%#.8lx\n", a ^ (c & b));
    c = (c | ~b) + 1;
} while (c);

This method has the advantages that you don't need to precalculate any tables, and you don't need to hardcode the 1024 - it will loop based entirely on the number of 1 bits in b.

It's also a relatively simple matter to parallelise this algorithm using integer vector instructions.

Answer 2

No guarantees that this is certifiably "the fastest", but this is what I'd do. First, sieve out the fixed bits:

uint32_t const reliable_mask = ~B;
uint32_t const reliable_value = A & reliable_mask;

Now I'd preprocess an array of 1024 possible values of the unreliable bits:

uint32_t const unreliables[1024] = /* ... */

And finally I'd just OR all those together:

for (size_t i = 0; i != 1024; ++i)
{
   uint32_t const val = reliable_value | unreliables[i];
}

To get the unreliable bits, you could just loop over [0, 1024) (maybe even inside the existing loop) and "spread" the bits out to the requisite positions.

Answer 3

This follows essentially the technique used by Kerrek, but fleshes out the difficult parts:

int* getValues(int value, int unreliable_bits)
{
  int unreliables[10];
  int *values = malloc(1024 * sizeof(int));
  int i = 0;
  int mask;

The function definition and some variable declarations. Here, value is your A and unreliable_bits is your B.

  value &= ~unreliable_bits;

Mask out the unreliable bits to ensure that ORing an integer containing some unreliable bits and value will yield what we want.

  for(mask = 1;i < 10;mask <<= 1)
  {
    if(mask & unreliable_bits)
      unreliables[i++] = mask;
  }

Here, we get each unreliable bit into an individual int for use later.

  for(i = 0;i < 1024;i++)
  {
    int some_unreliables = 0;
    int j;
    for(j = 0;j < 10;j++)
    {   
      if(i & (1 << j)) 
        some_unreliables |= unreliables[j];
    }   
    values[i] = value | some_unreliables;
  }

The meat of the function. The outer loop is over each of the outputs we want. Then, we use the lowest 10 bits of the loop variable i to determine whether to turn on each unreliable bit, using the fact that the integers 0 to 1023 go through all possibilities of the lowest 10 bits.

  return values;
}

Finally, return the array we built. Here is a short main that can be used to test it with the values for A and B given in your question:

int main()
{
  int *values = getValues(0x8A7C6BB5, 0x44444496);
  int i;
  for(i = 0;i < 1024;i++)
    printf("%X\n", values[i]);
}