¿La forma más rápida de calcular los valores posibles de INT sin firmar con n bits poco confiables?

Question

Dado un int a (32 bits) sin firmar, y otro int B sin firmar, donde la forma binaria de B denota los 10 bits "menos confiables" de A, ¿cuál es la forma más rápida de expandir los 1024 valores potenciales de A? Estoy buscando hacer esto en C.

Por ejemplo, se garantiza que Uint B siempre tendrá 10 1 y 22 0 en su forma binaria (10 bits menos confiables).

Por ejemplo, digamos

A = 2323409845  
B = 1145324694

Sus representaciones binarias son:

a=10001010011111000110101110110101

b=01000100010001000100010010010110

B denota los 10 bits menos confiables de A. Por lo tanto, cada bit que se establece en 1 en B denota un bit poco confiable en A.

Me gustaría calcular los 1024 valores posibles creados al alternar cualquiera de esos 10 bits en A.

Answer 1

Puede iterar a través de las 1024 configuraciones diferentes de los bits en b al igual que:

unsigned long b = 1145324694;
unsigned long c;

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

Para usarlos para modificar a puedes usar 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);

Este método tiene las ventajas de que no necesita precalcular ninguna tabla, y no necesita codificar el 1024: se basará completamente en el número de 1 bits en b.

También es una materia relativamente simple para paralelear este algoritmo utilizando instrucciones vectoriales enteras.

Answer 2

No hay garantías de que esto sea certificadamente "el más rápido", pero esto es lo que haría. Primero, tamice los bits fijos:

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

Ahora preprocesaría una matriz de 1024 valores posibles de los bits poco confiables:

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

Y finalmente lo haría solo o todos ellos juntos:

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

Para obtener los bits poco confiables, podría pasar por alto [0, 1024) (tal vez incluso dentro del bucle existente) y "extienda" los bits a las posiciones requeridas.

Answer 3

Esto sigue esencialmente la técnica utilizada por Kerrek, pero desarrolla las partes difíciles:

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

La definición de función y algunas declaraciones variables. Aquí, value es tuyo A y unreliable_bits es tuyo B.

  value &= ~unreliable_bits;

Enmascarar los bits poco confiables para asegurarse de que orine un entero que contenga algunos bits poco confiables y value Reducirá lo que queremos.

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

Aquí, tenemos cada bit poco confiable en un intiso intencionario para usar más tarde.

  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;
  }

La carne de la función. El bucle exterior está sobre cada una de las salidas que queremos. Luego, usamos los 10 bits más bajos de la variable de bucle i para determinar si encender cada bit poco confiable, utilizando el hecho de que los enteros 0 a 1023 Realice todas las posibilidades de los 10 bits más bajos.

  return values;
}

Finalmente, devuelve la matriz que construimos. Aquí hay un breve principal que se puede usar para probarlo con los valores para A y B Dado en su pregunta:

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