(MATHEMATIK) (DATENBANK) Zahl in 2-er Potenzen zerlegen

[Harry]

Holladiewaldfee,

ich habe vor kurzem ein Projekt übernommen, das gewisse Zustazinformationen zu einem Eintrag in der Datenbank in Form von Flags speichert. Diese Flags werden alle in einer einzigen Zahl zusammengefasst und mit dem entsprechenden Eintrag in der Datenbank gespeichert.

Jede Eigenschaft, die im Flag gespeichert wird, ist anhand einer 2er-Potenz eindeutig zu identifizieren, z.B.

1 (2^0): Leserechte
2 (2^1): Schreibrechte
4 (2^2): Sinnloser Eintrag
8 (2^3): Absoluter Quatsch
usw.

Diese Zahlen werden dann zum endgültigen Flag zusammen addiert, also z.B. ein User hat für einen absoluten Quatsch Lese- und Schreibrechte:

1 + 2 + 8 = 11

Das ist schön und gut, bloß in dem Moment wo ich einzelne Datensätze aus der Datenbank auslesen möchte, bei denen nur eine bestimmt Eigenschaft zutrifft, wird's eklig.
Im Moment ist das so gelöst, daß alle Datensätze aus der Datenbank geholt werden und dann die Zahl zerlegt wird. Dafür habe ich mir einen einfachen Algorithmus ausgedacht:

Zunächst wird floor(log_2(zahl)) berechnet. Damit erhalte ich die höchste Zweierpotenz, die in der Zahl vorkommen kann. Anschließend überprüfe ich mit Hilfe einer rückwärtslaufenden Schleife, ob eine Zweierpotenz in der Zahl Platz hat. Wenn ja, dann wird die entsprechende Zweierpotenz abgezogen. Irgendwann komme ich dann zu dem Punkt, an dem ich überprüfen kann, ob die gesuchte Zweierpotenz in der Restzahl noch Platz hat.

Beispiel:
Kommt 2^2 in 179 vor.
log_2(179) = 7.x
=> Schleife von 7 aus abwärts zählen
2^7 = 128 < 179 => 179 - 128 = 51
2^6 = 64 > 51
2^5 = 32 < 51 => 51 - 32 = 19
2^4 = 16 < 19 => 19 - 16 = 3 (Ausstieg hier)
2^3 = 8 > 3
2^2 = 4 > 3
=> 2^2 ist kein Bestandteil der Zweierpotenzenzerlegung.

Nun ist diese ganze Sache aber leider höllisch ineffektiv sobald die Anzahl der Datensätze größer wird.

Deswegen die Frage: Gibt es eine einfache mathematische Rechnung mit deren Hilfe ich feststellen kann, ob eine bestimmte Potenz von 2 in der Zerlegung einer Zahl vorkommt? "Einfach" heißt hier: Ein Einzeiler, also kein Algorithmus, der auf eine Schleife zurückgreift. Dann könnte ich die Auswahl der richtigen Datensätze nämlich schon der Datenbank überlassen. Oder gibt es evtl. sogar einen Datenbankbefehl, der diese Zerlegung für mich übernimmt?
Falls nein: Gibt es evtl. einen effektiveren Algorithmus (obiger lässt sich nur durch eine intelligentere Ausstiegsbedingung beschleunigen, also sobald der Rest kleienr 2^x ist: Ausstieg)?

Vielen Dank schonmal.

Ciao,

Harry

[Sven Rautenberg]

Moin!

Deswegen die Frage: Gibt es eine einfache mathematische Rechnung mit deren Hilfe ich feststellen kann, ob eine bestimmte Potenz von 2 in der Zerlegung einer Zahl vorkommt? "Einfach" heißt hier: Ein Einzeiler, also kein Algorithmus, der auf eine Schleife zurückgreift. Dann könnte ich die Auswahl der richtigen Datensätze nämlich schon der Datenbank überlassen. Oder gibt es evtl. sogar einen Datenbankbefehl, der diese Zerlegung für mich übernimmt?

Wenn du binäre Operationen machen kannst, also sowas wie AND und OR, dann ist dir damit im Prinzip schon geholfen.

Weil: "flagwert AND 2" ergibt entweder 0, wenn Bit 1 nicht gesetzt ist, oder einen Wert größer Null, wenn das Bit gesetzt ist.

Entsprechend kannst du auch alle anderen Bits testen. Auch Kombinationen von Bits lassen sich testen, erfordern dann aber natürlich die differenziertere Berücksichtigung des Ergebnisses.

Auf die gleiche Weise lassen sich Bits löschen und setzen:
Setzen: flagwert = flagwert OR 2 setzt Bit 1
Löschen: flagwert = flagwert AND NOT 2 löscht Bit 1

Wichtig ist bei den Operationen, dass es sich hier nicht um logische Verknüpfungen handelt, sondern um bitweise Verknüpfungen von Integer-Werten.

Um die Einzelabfrage, welche Aktion bei welchem gesetzten oder gelöschten Bit notwendig ist, kommst du kaum herum. Und wenn deine Datenbank binäre Operationen anbietet, kannst du die Abfrage der gesetzten (oder gelöschten) Bits schon direkt in die SQL-Abfrage packen.

- Sven Rautenberg

[Harry]

Holladiewaldfee,

Wenn du binäre Operationen machen kannst, also sowas wie AND und OR, dann ist dir damit im Prinzip schon geholfen.

Hm, tja, da hätte ich eigentlich auch selber drauf kommen können. Aber wenn man 24 Stunden täglich mit Analysis und linearer Algebra torpediert wird, vergisst man irgendwann, daß es ja auch noch so schöne Dinge wie binäre Operationen gibt ;-)

Vielen Dank, Du hast mir sehr geholfen :-)

Ciao,

Harry

[Michael Schröpl]

Hi Harry,

Hm, tja, da hätte ich eigentlich auch selber drauf kommen können. Aber wenn man 24 Stunden täglich mit Analysis und linearer Algebra torpediert wird, vergisst man irgendwann, daß es ja auch noch so schöne Dinge wie binäre Operationen gibt ;-)

Du kannst auch mit "DIV 2^(n-1)" alle rechts stehenden Bits wegschneiden und anschließend prüfen, ob das Ergebnis ungerade ist (MOD 2). Das prüft, ob das n-te Bit von rechts gesetzt ist.

Für Kombinationen von Bits ist diese Methode dann nicht mehr sonderlich effizient ...

Viele Grüße
      Michael
(PASCAL-Programmierer - dort geht die von Sven beschriebene Lösung nicht)

[Calocybe]

MoiN!

(PASCAL-Programmierer - dort geht die von Sven beschriebene Lösung nicht)

Warum nicht? Soweit ich weiss, stellt Pascal bitweise Verknuepfungen doch zur Verfuegung?

So long

[Michael Schröpl]

Hi Calocybe,

(PASCAL-Programmierer - dort geht die von Sven beschriebene Lösung nicht)
Warum nicht? Soweit ich weiss, stellt Pascal bitweise Verknuepfungen doch zur Verfuegung?

reden wir von Standard-PASCAL nach Wirth oder von irgend einer proprietären Implementierung?

Viele Grüße
      Michael

[Calocybe]

Re!

reden wir von Standard-PASCAL nach Wirth oder von irgend einer proprietären Implementierung?

Ach so, na in meinem Fall reden wir von einem ziemlich beliebigen Borland Pascal. *g*
Das Original-Pascal kennt keine Binaeroperatoren? Ist aber nicht so schoen...

So long

[Harry]

Holladiewaldfee,

Du kannst auch mit "DIV 2^(n-1)" alle rechts stehenden Bits wegschneiden und anschließend prüfen, ob das Ergebnis ungerade ist (MOD 2). Das prüft, ob das n-te Bit von rechts gesetzt ist.

Hast Du zufällig auch im Kopf, ob diese Methode schneller arbeitet als die, die Sven vorgeschlagen hat?

Im Moment mache ich jetzt die Abfrage mit ... WHERE flags&2=2 (um alle Datensätze zu finden, bei denen das Flag 2 gesetzt ist). Mit Deiner Methode wäre das dann ... WHERE DIV 2 MOD 2 = 1, oder?

Ansonsten werd ich wohl mal ein bißchen Benchmarken müssen. Rein vom Gefühl her würde ich die erste Methode für schneller halten.

Ciao,

Harry