Ternärsystem

[Onraku]

Hallo zusammen,
dies ist mein erster Beitrag hier, obgleich ich schon seit etwa 2 Wochen hier "rumschnüffel".
An dieser Stelle noch kurz einen Dank für das C-Tutorial, welches mir den Einstieg in eure Welt um vieles erleichterte.

Nun zum Thema, Ternärsysteme: Mir geht es im Grunde darum eine Matrix zu speichern, bzw. zu bearbeiten, im welcher es drei Zustände geben kann. Wozu? Ich möchte Nonogramme erstellen und lösen. Im Prinzip ist die Speicherung ganzen aber ähnlich zu einem TicTacToe-Spiel, von welchem ich im weiteren auch erstmal ausgehe.

Mein erster Gedanke war einfach ein Array zu benutzen, hier [3][3], alsklein wie möglich lässt sich immer noch ein char hinterlegen. Das macht dann 3*3*8 = 72 Bit. OK, aber in einem Riesennonogramm kommt schon einiges mehr zusammen, erst recht wenn das ganze Ding dann noch die dritte Dimension für sich entdeckt.

Wenn es nur darum ginge den "Soll"-Zustand eines Nonogramms zu speichern, könnte ich das rein binär machen: 9 Felder ergeben 9 Bit, und damit ein Achtel des Speicherbedarf. Dazu kommt der Vorteil, dass ich mit Bitoperatoren hantieren könnte.
Aber ich will ja drei Zustände speichern, AN, AUS und Vielleicht, oder im Sinne von TicTacToe: AUS, X und O.
Wikipedia hat hier einen interessanten Artikel zum Thema "Dreiwertige Logik" wobei es verschiedene Systeme gibt, welche sich bei der Implikation unterscheiden.

Aber wie nutze ich das ganze nun für mich? Wie kann ich äquivalent zu binären Bitoperatoren ternär an meinen Zuständen manipulieren?
Vielleicht hat ja jemand Erfahrung mit sowas, oder kann mir das Brett vorm Kopf vor die Füße legen damit ich merke dass ich auf dem Holzweg bin...

/edit
Vielleicht ist das hier besser bei "Mathematik" aufgehoben?!?

[oenone]

Du kannst auch zwei Bit pro Feld nehmen, um alle Zustände eindeutig abzubilden. Für 9 Felder wären das dann 18 Bit. Quasi die Werte 00, 01, und 10 - und du hast noch einen vierten Zustand übrig, den du nicht brauchst. Oder du spaltest es in zwei Arrays auf: ein Array für X, ein Array für O. Wenn keines oder beide gesetzt sind, dann befindest du dich im dritten Zustand (auch hier hast du effektiv vier Zustände).

[cloidnerux]

Hallo zusammen,
dies ist mein erster Beitrag hier, obgleich ich schon seit etwa 2 Wochen hier "rumschnüffel".
An dieser Stelle noch kurz einen Dank für das C-Tutorial, welches mir den Einstieg in eure Welt um vieles erleichterte

Willkommen im Forum.
Schön zu hören das dir unser C-Tutorial gefallen hat.
Wie bist du auf uns gestoßen?

Aber wie nutze ich das ganze nun für mich? Wie kann ich äquivalent zu binären Bitoperatoren ternär an meinen Zuständen manipulieren?

Binär und Ternär vertragen sich nicht, ganz einfach weil 2 und 3 verschiedene Primzahlen sind^^
Wegen Speicherbedarf:
4GB Ram kosten 20€, 1 char belegt 1 byte, das bedeutet du kannst 1024 chars in einem kbyte ablegen, 2^20 in einem Megabyte und 2^30 in in einem Gigabyte. da du ja 4 Gigabyte hast, wird das ganze zu 2^32 chars die du speichern kannst, das sind 4.294.967.296 chars, also ne ganze menge.
Selbst wenn du ein tensor mit 10^3 * 10^3 * 10^3 Elementen hast, hast du Insgesamt nur 10^9 elemente, also gerade mal 1.000.000.000 Stück und es passen nochmal 4 mal so viel in deinen Ram.
Also wegen Speicherplatz brauchst du dir egt keine Sorgen machen.

Wenn es sien muss, kannst du ja immer noch ein Byte in jeweils 2 Bit zerteilen, die dir Mühe machen mit Bit-Operationen die Zustände zu ändern und dir gedanken machen über Verwaltungssysteme, damit hättest du dann 4 mal so viel Speicherplatz gewonnen.

MfG cloidnerux.

[Onraku]

Danke für die schnellen antworten.
Um den Speicherbedarf gehts mir auch nur sekundär. Was mich halt fasziniert hat ist das Konzept der Bitverschiebung, bzw. die Operatoren allgemein. Naja, und die Tatsache dass ich z.B. Dirty Oertis Avatar als 111100010 darstellen kann, was einfach dem Dezimalwert 482 entspricht. Und wenn ich ein Feld mehr ausmale, oben rechts, hab ich 486. Das wollte ich gerne auf eine 3er Basis übertragen.

Wenn es sien muss, kannst du ja immer noch ein Byte in jeweils 2 Bit zerteilen, die dir Mühe machen mit Bit-Operationen die Zustände zu ändern und dir gedanken machen über Verwaltungssysteme, damit hättest du dann 4 mal so viel Speicherplatz gewonnen.

Die Mühe? Ich stelle mir das einfacher vor, als mit nem Array zu hantieren. Naja der Zugriff ist schon einfacher, aber das Speichern der Levels gefällt mir binär einfach besser.

Kleiner Ausblick in die (also vllt. meine) Zukunft. Eine Umsetzung auf einem Handheld, NDS, oder GBA, wäre mit zwei binären Zahlen dank der verschiedenen Ebenen oder Hintergründe nicht mehr so schwer. Hier spielt auch der Speicher wieder eine größere Rolle.

MfG Onraku

[cloidnerux]

Was mich halt fasziniert hat ist das Konzept der Bitverschiebung, bzw. die Operatoren allgemein

Dann kannst du dir ja mal den 4-Bit Volladdierer im Wiki ansehen, der Funktioniert nur mit sowas auf Hardware ebene
http://www.proggen.org/doku.php?id=elec ... ects:adder

Naja, und die Tatsache dass ich z.B. Dirty Oertis Avatar als 111100010 darstellen kann, was einfach dem Dezimalwert 482 entspricht.

Das Funktioniert aber nur, wenn du vorher vereinbart hast, wie diese Zahlenfolge verarbeitet werden muss, damit daraus eine 160x160 Pixel Matrix mit jeweils 3 Byte pro Pixel werden um es dann so anzuzeigen, wie es ist.

Das wollte ich gerne auf eine 3er Basis übertragen.

Du kannst gerne in deinem Zahlensystem Rechnen, nur dein Computer tut es eben nicht, und damit werden Probleme auftreten, weil du im Endeffekt immer wieder auf eine Binäre Basis zurückgreifen musst.

Kleiner Ausblick in die (also vllt. meine) Zukunft. Eine Umsetzung auf einem Handheld, NDS, oder GBA, wäre mit zwei binären Zahlen dank der verschiedenen Ebenen oder Hintergründe nicht mehr so schwer. Hier spielt auch der Speicher wieder eine größere Rolle.

Und was genau willst du nochmal Implementieren, hab das gerade nicht so ganz mitbekommen.

Und nochmal zum Speicher: Du hast für alles erstmal genug Speicher. Erst wenn es größer wird, wird es Probleme geben, aber zu dem Zeitpunkt sollte es kein Problem für dich sein, Möglichkeiten zur Reduzierung der Größe anzuwenden.

MfG cloidnerux.

[Dirty Oerti]

Und nochmal zum Speicher: Du hast für alles erstmal genug Speicher.

Das enttäuscht mich jetzt aber schon etwas

Ich finde es sehr löblich, den Speicherbedarf minimieren zu wollen.
Deshalb ist es hier auch nur zu Testzwecken wirklich sinnvoll, ein ganzes char für ein "Feld" zu verwenden.

Die einfachste Möglichkeit ist, wie schon dargestellt, einfach pro "Feld" 2 Bit zu verwenden. Dann hat man zwar einen möglichen Zustand zu viel, aber trotzdem schon viel Speicher gespart.
Und in einem Feld kann man das ganze natürlich immer noch halten:

Das Feld besteht dann halt aus (X*Y*Z)/4 Byte (aufrunden! ^^)

Adressieren kann man das dann einfach so:

Code: Alles auswählen

char array[(X_MAX*Y_MAX*Z_MAX+3) / 4];
unsigned int position = z * X_MAX * Y_MAX + y * X_MAX + x;
char feld = (  array[position/4] & (3<<(2*(position%4)))  ) >> (2*(position%4));

Du siehst, das ist etwas verzwickt. Kann auch sein, dass ich jetzt einen Fehler drinn hab, aber das Grundprinzip passt so

[Onraku]

Hm, blödes Deutsch...
Es hat dreimal Lesen gedauert bis ich dich verstanden hab. Im weiteren werde ich "Feld" nicht mehr benutzen, sondern "Array" und "Element" um Missverständnissen vorzubeugen.
Was den Code angeht ist mir eine Sache noch unklar:

Code: Alles auswählen

    char array[(X_MAX*Y_MAX*Z_MAX+3) / 4];
    unsigned int position = z * X_MAX * Y_MAX + y * X_MAX + x;
    char feld = (  array[position/4] & (3<<(2*(position%4)))  ) >> (2*(position%4));

Die Arraygröße ist klar, sowie die Position, wobei in einem 3*3*3 Tensor X_MAX = 3, also die Anzahl der Elemente in einer Dimension ist, und nicht 2 als Maximalwert (0;1;2) in dieser Dimension.

Aber nun: array[position/4] zeigt mir in welchem char ich ein Element wiederfinde.
3 schaltet mir ein "Doppelbit" auf 11, hier gehen auch 0, 1 und 2, je nach dem was ich machen möchte.
<<(2*(position%4) schiebt das ganze auf die richtige "Doppelbitposition" im Byte, und mit & schalte ich den neuen Zustand dazu.
Aber was soll " >> (2*(position%4))"?
Fall 2*2*2 Tensor: letztes Element, also Position 7:
Befindet sich im array[1], durch (3<<(2*(position%4))) schreibe ich dort 1100 0000 hinein. Soweit klar, jetzt bin ich dort wo ich hin wollte. Mit " >> (2*(position%4))" wird das doch wieder zu 0000 0011, also der Position 4.

Das macht für mich nur beim Auslesen Sinn, hier sehe ich den Zustand 3.
Hätte ich aber Pos.7 und Pos.6 auf 3, also 11 geschaltet und will 6 auslesen, steht dann dort 0000 1111 also 15. Den Zustand will ich ja gar nicht. Oder kann ich mir nur die ersten beiden Bit alleine ansehen?

Du siehst, das ist etwas verzwickt.

Genau DAS seh ich immerhin. Hab mir das echt leichter vorgestellt. Ein char Array zu erstellen und effektiv nur 1/8 des Platz zu nutzen ist wirklich viel einfacher, ud wird letztendlich auch meinen Weg darstellen, dennoch will ich hinter die Bitoperatoren steigen, und ich dachte dieses Projekt wäre eine gute Gelegenheit dazu.

Willkommen im Forum.
Schön zu hören das dir unser C-Tutorial gefallen hat.
Wie bist du auf uns gestoßen?

Googlesuche, nach C-Bibliotheksdokumentation mit Beispielen.
Zuerst nutzte ich Tutorials.at, bzw ein Galileo OpenBook, aber dort waren mir die Refezenzen zu allgemein, vor allem da in den Funktionen eher Zeiger genutzt werden, kam ich mit dieser Beschreibung ohne Beispiel nicht gut zurecht. Mittlerweile geht es, und so wird das Buch noch zum Nachschlagen benutzt. Zwischendurch kam auch c-howto.de dazu. Wobei mir das Tutorial nicht so gefallen hat, wohl aber die Übungen, die jedes Kapitel abschließen. Sowas ist hier ja scheinbar auch geplant. Das halte ich für eine gute Ergänzung zu dem sonst sehr anschaulichen und gut strukturierten Tutorial hier. Zumal hier die Anbindung des Forums dem Ganzen noch die Krone aufsetzt. Wo andere ein Buch schreiben, friss oder stirb, hat man hier die Möglichkeit sich "das Steak einmal durchschneiden zu lassen, wenn es (noch) nicht ganz in den Mund will".

[Kerli]

Als Alternative gibt es auch noch die sogenannten Bitfields. Dabei kann man angeben aus wie vielen Bits eine Variable in einer Struktur besteht:

Code: Alles auswählen

struct byte_4
{
  // jeder member braucht 2 Bit
  int v1 : 2;
  int v2 : 2;
  int v3 : 2;
  int v4 : 2;
};

// ...

byte_4 memory[42];

// werte ([0-3]) zuweisen
memory[10].v1 = 2;
memory[3].v3 = 3;
// ...

Man muss dabei jedoch aufpassen da dieser Ansatz auch ein paar Gefahren birgt. So ist zum Beispiel das Memorylayout kompilerabhängig, so dass ein Lesen und Schreiben über die Grenzen einzelner Member hinaus nicht portabel ist. Weitere Probleme können im Zusammenhang mit Paralleler Programmierung auftreten, da der Bitweise Zugriff auf Variablen für die CPU oft nicht möglich ist, und somit bei gleichzeitigem Schreiben in das selbe Byte (oder eine andere gewisse Mindestgröße) trotz Mutex Probleme auftreten können.

[Dirty Oerti]

Ein char Array zu erstellen und effektiv nur 1/8 des Platz zu nutzen ist wirklich viel einfacher, ud wird letztendlich auch meinen Weg darstellen

Das finde ich schade, das ist wirklich nur Verschwendung von Speicherplatz.

Aber was soll " >> (2*(position%4))"?

Das ist wirklich nur zum Auslesen gedacht. Das Beispiel soll ja auch nur den Zugriff, sprich das Lesen verdeutlichen.
Dadurch hast du am Ende entweder den Zustand 0, 1, 2 oder 3.
Egal an welcher Bitstelle die entsprechenden Bits vorher standen.

Zum Schreiben würdest du dann ja auch nicht nur & verwenden.
Du könntest dir z.B. was mit 2 mal & basteln.

Code: Alles auswählen

array[position/4] = (array[position/4] & ~(3<<(2*(position%4)))) | (WRITE_ME << (2*(position%4)));

Kein Anspruch auf Korrektheit Es geht bestimmt auch einfacher, aber iwie kommt es mir gerade nicht in den Sinn.
Was ich mache:

Das entsprechende Element im Array verknüpfe ich bitweise UND mit dem bitweise invertierten Muster, das durch Verschiebung der 3 an die entsprechende Stelle entsteht.
Einfacher:
Die 2 Bits, die ich beschreiben will, sind 0, alle anderen 1. Wende ich nun bitweise UND auf dieses Muster und das Element des Arrays an, dann werden genau die beiden Bits, die ich beschreiben will, erst einmal auf 0 gesetzt.

Im Anschluss kann ich dann mit bitweise ODER die beiden Bits beschreiben.

Klar?

*Fehler ausgebessert *

[cloidnerux]

Vlt kann ich noch etwas helfen, hab dank vieler Stunden AVR-Programmierung etwas Erfahrung mit Bitoperationen-

Wir führen erst einmal 3 Operationen ein: Lesen, Löschen, Schreiben-
Beim Lesen, möchten wir ein char Zurückbekommen, das die beiden bits an der Position 0 und 1 enthält.
Löschen bedeutet: Die Bits an der gegeben Stelle zu 0 schreiben
Schreiben bedeutet: Löschen und dann die neuen Informationen schreiben.

Dann definieren wir noch 2 Hilfsvariablen(Ich werde in den Unteren Beispielen darauf verzichten, die Deklarationen erneut auszuführen):

Code: Alles auswählen

int arrayPos = position/4; //Die Position im Array
char arraySubPos = position % 4; //Die position innerhalb des entsprechenden chars.

Nun schauen wir uns erstmal die Operation "lesen" an:
Wir müssen dabei folgendes machen:

• Die beiden Bits im Array isolieren
• DIe beiden Bits an die erste Position im char schieben

Das machen wir wie folgt:

Code: Alles auswählen

char read(int position)
{
    char result = array[arrayPos];   //Erstmal nur das entsprechende element im Array finden
    result &= (3 << (arraySubPos * 2)); //Hier schieben wir die Binäre Folge 11 so lange nach Links bis sie auf die stelle der gesuchten bits im array zeigt und UND-Verknüpfen das, sodass wir diese stelle Isolieren
    return (result >> (arraySubPos * 2)); //Hier schieben wir die entsprechenden Bits an die erste stelle
}

Betrachten wir nun schnell das Löschen:

Code: Alles auswählen

void delete(int position)
{
    array[arrayPos] &= ~(3 << (arraySubPos * 2)); //Hier UND-Verknüpfen wir das ganze so, das die entsprechenden Stelle im char auf 0 gesetzt werden
}

Und dann noch das Schreiben:

Code: Alles auswählen

void write(int position, char value)
{
    delete(position);
    array[arrayPos] |= (value << (arraySubPos * 2));
}

Wenn du fragen hast, einfach stellen