Moyen le plus rapide pour calculer les valeurs possibles de unsigned int avec N bits peu fiables?

Question

Étant donné un A unsigned int (32 bits), et un autre unsigned int B, où la forme binaire B représente les 10 bits « moins fiables » de A, ce qui est le meilleur moyen de développer toutes les 1024 valeurs potentielles de A? Je cherche à faire en C.

uint par exemple B est assuré d'avoir toujours 10 et 22 de 1 0 dans ce format binaire de (10 bits les moins fiables).

Par exemple, supposons que

A = 2323409845  
B = 1145324694

Leurs représentations binaires sont:

a=10001010011111000110101110110101

b=01000100010001000100010010010110

B représente les 10 bits les moins fiables de A. Ainsi, chaque bit qui est mis à 1 dans B représente un bit peu fiable en a.

Je souhaite calculer toutes les valeurs possibles 1024 créées en faisant basculer l'un de ces 10 bits en a.

Answer 1

Vous pouvez parcourir les 1024 paramètres différents des bits b comme ceci:

unsigned long b = 1145324694;
unsigned long c;

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

Pour utiliser pour modifier a vous pouvez simplement utiliser 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);

Cette méthode présente les avantages que vous n'avez pas besoin de précalculer des tables, et vous ne devrez câbler 1024 -. Il boucle entièrement basé sur le nombre de bits dans 1 b

Il est aussi une question relativement simple à paralléliser cet algorithme en utilisant des instructions vectorielles entier.

Answer 2

Aucune garantie que c'est certifiably « le plus rapide », mais ce que je ferais. Tout d'abord, un tamis sur les bits fixes:

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

Maintenant, je voudrais prétraiter un tableau de 1024 valeurs possibles des bits peu fiables:

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

Et enfin, je voudrais juste OU tous ceux ensemble:

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

Pour obtenir les bits non fiables, vous pouvez simplement boucle sur [0, 1024) (peut-être même à l'intérieur de la boucle existante) et « propagation » les bits sur les positions nécessaires.

Answer 3

suit essentiellement la technique utilisée par Kerrek, mais les parties concrétise difficiles:

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

La définition de la fonction et des déclarations de variables. Ici, value est votre A et unreliable_bits est votre B.

  value &= ~unreliable_bits;

Masquez les bits peu fiable pour faire en sorte que ORing un entier contenant quelques bits peu fiables et value donnera ce que nous voulons.

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

Ici, nous obtenons chaque bit peu fiables dans un int individuel pour une utilisation ultérieure.

  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 viande de la fonction. La boucle extérieure est sur chacune des sorties que nous voulons. Ensuite, nous utilisons les plus bas 10 bits du i variable en boucle pour déterminer si pour activer chaque bit peu fiable, en utilisant le fait que les entiers 0 à aller de 1023 à travers toutes les possibilités les plus bas 10 bits.

  return values;
}

Enfin, retourne le tableau que nous avons construit. Voici un court principal qui peut être utilisé pour tester avec les valeurs de A et B donné dans votre question:

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