Schnellster Weg, um mögliche Werte von unsigniertem int mit n unzuverlässigen Bits zu berechnen?

Question

Bei einem nicht signierten int a (32 Bit) und einem anderen nicht signierten int B, wobei Bs binärer Form die 10 "am wenigsten zuverlässigen" Bits von A bezeichnet, wie können Sie alle 1024 potenziellen Werte von a? Ich möchte das in C. machen

ZB Uint B hat garantiert immer 10 1 und 22 0 in seiner binären Form (10 am wenigsten zuverlässige Bits).

Zum Beispiel sagen wir

A = 2323409845  
B = 1145324694

Ihre binären Darstellungen sind:

a=10001010011111000110101110110101

b=01000100010001000100010010010110

B bezeichnet die 10 am wenigsten zuverlässigen Bits von A. Also jedes Bit, das in B auf 1 eingestellt ist, bezeichnet ein unzuverlässiges Bit in A.

Ich möchte alle 1024 möglichen Werte berechnen, die durch Umschalten eines dieser 10 Bits in A.

Answer 1

Sie können durch die 1024 verschiedenen Einstellungen der Bits ITRETTEN b Like SO:

unsigned long b = 1145324694;
unsigned long c;

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

Um diese zu verwenden, um zu ändern a Sie können einfach XOR verwenden:

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

Diese Methode hat die Vorteile, dass Sie keine Tabellen vorzusagen müssen, und Sie müssen den 1024 nicht harten b.

Es ist auch eine relativ einfache Angelegenheit, diesen Algorithmus unter Verwendung von Ganzzahlvektoranweisungen zu parallelisieren.

Answer 2

Keine Garantie dafür, dass dies "am schnellsten" zertifiziert ist, aber das würde ich tun. Sieben Sie zunächst die festen Bits:

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

Jetzt würde ich ein Array von 1024 möglichen Werten der unzuverlässigen Bits vorarbeiten:

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

Und schließlich würde ich nur oder all diese zusammen:

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

Um die unzuverlässigen Teile zu bekommen, können Sie einfach übergehen [0, 1024) (Vielleicht sogar innerhalb der vorhandenen Schleife) und "verteilen" die Teile auf die erforderlichen Positionen.

Answer 3

Dies folgt im Wesentlichen der von Kerrek verwendeten Technik, aber die schwierigen Teile ausfertigen:

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

Die Funktionsdefinition und einige variable Deklarationen. Hier, value ist dein A und unreliable_bits ist dein B.

  value &= ~unreliable_bits;

Maskieren Sie die unzuverlässigen Bits, um sicherzustellen, dass Oring eine Ganzzahl mit einigen unzuverlässigen Bits und enthält value wird liefern, was wir wollen.

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

Hier erhalten wir jedes unzuverlässige Bit in eine individuelle INT, die später verwendet wird.

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

Das Fleisch der Funktion. Die äußere Schleife befindet sich über jeden der gewünschten Ausgänge. Dann verwenden wir die niedrigsten 10 Bit der Schleifenvariablen i Um zu bestimmen, ob jedes unzuverlässige Bit eingeschaltet werden soll, unter Verwendung der Tatsache, dass die Ganzzahlen 0 zu 1023 Gehen Sie alle Möglichkeiten der niedrigsten 10 Bit durch.

  return values;
}

Schließlich geben Sie das Array zurück, das wir gebaut haben. Hier ist ein kurzes Haupt, mit dem es verwendet werden kann, um es mit den Werten für zu testen A und B in Ihrer Frage gegeben:

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