mit Bit-Felder als Darstellung für ganze Zahlen in c

Question

In meiner C-Klasse waren wir einen Auftrag gegeben:

schreiben ein interaktives Programm (Standard Input/Output). Definieren Sie den neuen Typ set unter Verwendung von typedef, der einen Satz Ganzzahlen im Bereich 0-127 enthalten kann. Die Datenstruktur muss hinsichtlich der Speicherung möglichst effizient sein (Hinweis: Arbeiten mit Bits). Außerdem müssen Sie 6 globale Variablen A, B, C, D, E, F vom Typ set definieren. Alle Operationen an Sätzen im Programm werden auf diesen 6 Variablen ausgeführt.

Dieser Befehl read_set A,5,6,7,4,5,4,-1 liest die Eingabe von Ganzzahlen durch den Benutzer, während -1 das Ende der Benutzereingabe bedeutet. Andere Befehle, die ein Benutzer verwenden kann: print_set A - druckt den Satz in aufsteigender Reihenfolge, union_set A,B,C macht Union on 2 und speichert die Ausgabe in einem dritten Satz, intersect_set A,B,C - bestimmt den Schnittpunkt von 2 Sätzen und speichert die Ausgabe in einem dritten Satz.

Soweit ich verstehe, muss ich Bit-Felder verwenden. Ich könnte eine Tabelle mit Ganzzahlen von 0-127 erstellen. Dann könnte ich die 6 Variablen A,B,C,D,E,F mit set Typdefinition erstellen und 128 Bit-Felder für jede Variable geben. Wenn dann ein Benutzer 15 eingibt, würde ich das Bit einschalten, das 15 im Datentyp darstellt. Ich bin mir wirklich nicht sicher, ob das so ist, weil mir nicht klar ist, wie ich Bit-Felder so anordnen würde, dass ich bei Bedarf genau 15-Bit anschalten kann, müsste ich irgendwie eine ganze Zahl umwandeln Bitfeldname ... Auch print_set druckt das Set in aufsteigender Reihenfolge, also wie könnte ich Bitfelder dafür neu anordnen?

Ich hoffe wirklich, Sie haben ein paar Ideen.

Answer 1

Ja, jeder der Sätze genannt A, B, C, D, E und F durch ein paar unsigned long long ganze Zahlen wie folgt dargestellt:

typedef struct { unsigned long long high; unsigned long long low; } Set;

Siehe https://en.wikipedia.org/wiki/C_data_types

Dies gibt Sie 128 Bits von Daten in einem Set (64 Bits für die hohen Zahlen 64 bis 127 und 64 Bits für die niedrigen Zahlen 0 bis 63).

Dann brauchen Sie nur, wie dies einige Bit-Manipulation zu tun: http://www.tutorialspoint.com/ansi_c/c_bits_manipulation.htm

Für eine Zahl zwischen 0 und 63, Sie 1 nach links x-mal verschieben würden und dann festgelegt, dass etwas auf dem „niedrigen“ Bereich .

Für eine Zahl zwischen 64 und 127 würden Sie 1 x 64 mal nach links verschieben und dann dieses Bit auf das "high" -Feld setzen.

Hoffe, das hilft!

Answer 2

Die Verwendung von Bitfeldern für diese Zuweisung wird sich aufgrund von Ausrichtungsproblemen als sehr mühsam erweisen, und Sie können Arrays von Bitfeldern sowieso nicht definieren. Ich würde vorschlagen, ein Array von Bytes (unsigned char) zu verwenden und Werte in dieses Array zu packen. Ein 7-Bit-Wert, der höchstens 2 Bytes umfasst. Das Array für count Werte sollte mit einer Größe von (count + 7)/8 Bytes zugewiesen werden. Um Platz zu sparen, können Sie kleine Sätze in einem ganzzahligen und größeren Satz mit einem zugewiesenen Array speichern.

Der Datentyp würde wie folgt aussehen:

#include <stdint.h> 
#include <stdlib.h> 

typedef struct set { 
    size_t count; 
    union { 
     uintptr_t v; 
     unsigned char *a; 
    }; 
} set; 

Hier ist, wie der n-te Wert zu extrahieren:

int get_7bits(const set *s, size_t n) { 
    if (s == NULL || n >= s->count) { 
     return -1; 
    } else 
    if (n < sizeof(uintptr_t) * CHAR_BIT/7) { 
     return (s->v >> (n * 7)) & 127; 
    } else { 
     size_t i = n/7; 
     int shift = n % 7; 
     if (shift <= CHAR_BIT - 7) { 
      /* value fits in one byte */ 
      return (s->a[i] >> shift) & 127; 
     } else { 
      /* value spans 2 bytes */ 
      return ((s->a[i] | (s->a[i + 1] << CHAR_BIT)) >> shift) & 127; 
     } 
    } 
} 

Sie können die anderen Zugriffsfunktionen schreiben und Ihre Aufgabe abzuschließen.