Zwei Werte [0..16] in einem Integer festhalten

[Jonelmeier]

Hallo!

Ich habe gerade ein kleines Problem: Und zwar soll ich zwei Werte in einem Integer festhalten.
Die Werte liegen zwischen MIN_X..MAX_X und MIN_Y..MAX_Y (im konkreten Beispiel jeweils zwischen 1 und 16, das soll aber variabel bleiben).
Nun stehe ich total auf dem Schlauch!
Gibt es eine mathematische Lösung für das Problem? Wäre aber auch mit einer Idee für eine Q&D Lösung zufrieden, da ich echt keine Ahnung habe...

Gruß!

[Luckie]

Wie wäre es mit dem Datentyp TPoint?

[Jonelmeier]

Zitat:

Zitat von Luckie

Wie wäre es mit dem Datentyp TPoint?

Ich muss leider einen Integer zum speichern verwenden...das ist ja das Problem...

[himitsu]

Entweder du löst das Mathematisch

Delphi-Quellcode:

// setzen
G := A * 100 + B;

// auslesen
A := G div 100;
B := G mod 100;

oder über einen Record ... analog zu TSmallPoint (TPoint sind 2 Integer in einem Int64)

Delphi-Quellcode:

type
  TSplitt = record  
  case Integer of
    0: (g: LongInt);
    1: (a, b: Word);
  end;

// setzen
Splitt.a := A;
Splitt.b := B;
g := Splitt.g;

// auslesen
Splitt.g := G;
A := Splitt.a;
B := Splitt.b;

// auslesen
A := TSplitt(G).a;
B := TSplitt(G).b;

oder

Delphi-Quellcode:

type
  TSplitt = record  
  class function Set(A, B: Word): LongInt;
  case Integer of
    0: (g: LongInt);
    1: (a, b: Word);
  end;

class function TSplitt.Set(A, B: Word): LongInt;
begin
  TSplitt(Result).a := A;
  TSplitt(Result).b := B;
end:

// setzen
TSplitt(G).a := A;
TSplitt(G).b := B;

// setzen
G := TSplitt.Set(A, B);

// auslesen
Splitt.g := G;
A := Splitt.a;
B := Splitt.b;

// auslesen
A := TSplitt(G).a;
B := TSplitt(G).b;

Das Ganze kann man notfalls noch in Funktionen kapseln:

Typgrößen und Multiplikatoren können/müssen natürlich noch angepaßt werden.

[Meflin]

Dank der Unendlichkeit der natürlichen Zahlen ist dies tatsächlich einwandfrei mathematisch lösbar, bekannt als Cantorsche Paarungsfunktion (mit der man sogar beliebig viele natürliche Zahlen auf eine einzige umkehrbar abbilden kann).

http://upload.wikimedia.org/math/7/9...63de70c533.png

Beispiel: du willst (5,3) speichern. Das wäre dann einfach ((5 + 3) * (5 + 3 + 1)) / 2 + 3 = 39.

Zur Umkehrung benötigt man zwei Funktionen:

http://upload.wikimedia.org/math/e/3...20ce9955d8.png

http://upload.wikimedia.org/math/8/0...db720a87fe.png

Zunächst sucht man nun (durch ausprobieren?) die größte Zahl i (oben dargestellt durch die Funktion q), für die gilt f(i) <= 39. i ist in unserem Fall 8. Dann ist y = 39 - f(8) = 39 - 36 = 3.
x ergibt sich aus i - y = 8 - 3 = 5.

Noch Fragen :mrgreen: ?

edit: und unter o.g. Link findet man sogar noch Pascal-Code für die Umkehrfunktion:

Delphi-Quellcode:

procedure CantorPair(    I   : Integer;
                     Var X,Y : Integer);
{ Gibt das i-te Paar (X,Y) in Diagonalabzaehlung zurueck }
var
   J : Integer;
  
   function F(Z : Integer) : Integer;
   begin
      F := Z * (Z + 1) div 2  
   end;

   function Q(Z : Integer) : Integer;
   var
      V : Integer;
   begin
      V := 0;
      while F(V) <= Z do
         V := V + 1;
      Q := V - 1
   end;

begin
   J := Q(I);
   Y := I - F(J);
   X := J - Y;
end;

[Jonelmeier]

@himitsu: Vielen Dank für deine vielen schnellen Ideen!

Ich habe es jetzt auf die mathematische Weise gelöst:

Setzen:

Delphi-Quellcode:

MyInt := X * Max(MAX_X, MAX_Y) + Y;

Auslesen:

Delphi-Quellcode:

X := MyInt div Max(MAX_X, MAX_Y);
Y := MyInt mod Max(MAX_X, MAX_Y);

@Meflin: Nein, keine weiteren Fragen :wink:

Danke nochmal!

[himitsu]

Es müßte wohl mehr so aussehn:
MAX_Y+1 ist ja der kleinste Wert, in dessen Vielfachen X liegen muß, so daß Y noch reinpaßt.

Setzen:

Delphi-Quellcode:

MyInt := X * (MAX_Y + 1) + Y;

Auslesen:

Delphi-Quellcode:

X := MyInt div (MAX_Y + 1);
Y := MyInt mod (MAX_Y + 1);

und falls MIN_Y auch negativ sein kann:
Setzen:

Delphi-Quellcode:

MyInt := X * (Max(MAX_Y, Abs(MIN_Y)) + 1) + Y;

Auslesen:

Delphi-Quellcode:

X := MyInt div (Max(MAX_Y, Abs(MIN_Y)) + 1);
Y := MyInt mod (Max(MAX_Y, Abs(MIN_Y)) + 1);

[divBy0]

Du könntest die beiden Werten auf jeweils im High- und Low-Word speichern. 1..16 könntest du sogar 4 mal in einem Integer unterbringen, wenn ich dich nicht falsch verstanden hab.

[himitsu]

@divBy0: 1..16 paßt sogar bis zu 8 Mal in einen Interger rein.

bzw. ein Integer (4-Byte) läßt sich mit 8 Hexadezimalstellen (Base16) darstellen.

[hathor]

So kleine Werte lassen sich in einem einzigen Byte speichern:
1..16 (0..15) = 1 Nibble
2 Nibble = 1 Byte

Weil man mit Integern rechnet, kann man gut damit umgehen:

var
numberByte: integer;
highNibble,lowNibble: integer;

(Byte:=16*highNibble + lowNibble;)
numberByte:=16*highNibble + lowNibble;

highNibble:=numberByte div 16;
lowNibble:=numberByte mod 16;

[Lannes]

Hallo,

da es noch nicht erwähnt wurde, es gibt auch MakeLong() und MakeWord()

Delphi-Quellcode:

var w: Word;
    b1, b2: Byte;
begin
  b1 := 44;
  b2 := 55;
  w := MakeWord(b1, b2);
//auslesen
  b1 := LoByte(w);  
  b2 := HiByte(w);

Delphi-Quellcode:

var i: Integer;
    w1, w2: Word;
begin
  w1 := 4444;
  w2 := 5555;
  i := MakeLong(w1, w2);
//auslesen
  w1 := LoWord(i);  
  w2 := HiWord(i);

[divBy0]

Zitat:

Zitat von himitsu

@divBy0: 1..16 paßt sogar bis zu 8 Mal in einen Interger rein.

bzw. ein Integer (4-Byte) läßt sich mit 8 Hexadezimalstellen (Base16) darstellen.

Ja, das stimmt natürlich. Ich hatte dies selbst sogar schon mal genutzt... :oops:

[himitsu]

Notfalls hätte ich noch etwas:

Delphi-Quellcode:

Var P: TIntegerPack; 

P.Clear;
P.Add(MIN_X, MAX_X, X);
P.Add(MIN_Y, MAX_Y, Y);
i := P.Result;

P.Clear;
P.Add(MIN_X, MAX_X);
P.Add(MIN_Y, MAX_Y);
P.Result := i;
X := P.Value[0];
Y := P.Value[1];

Das Ergebnis dürfte Binär die kleinste Darstellung ergeben. :gruebel:

Delphi-Quellcode:

uses
  SysConst, RTLConsts, SysUtils;

const
  MinInt = Low(Integer);

type
  TIntegerPack = Record
  Private
    FList:  Array of Record
              Min, Max: Integer;
              Value:    Integer;
            End;
    FResult:  UInt64;
    FResSize: UInt64;
    Function  GetMin   (Index:    Integer): Integer;
    Function  GetMax   (Index:    Integer): Integer;
    Function  GetVal   (Index:    Integer): Integer;
    Procedure SetVal   (Index, X: Integer);
    Procedure SetResult(       X: UInt64);
    Function  GetSize  (Bits:     Integer): Integer;
  Public
    Function Add(Min, Max: Integer; Value: Integer = MinInt): Integer;
    Property Min  [Index: Integer]: Integer Read GetMin;
    Property Max  [Index: Integer]: Integer Read GetMax;
    Property Value[Index: Integer]: Integer Read GetVal Write SetVal;

    Property Result:  UInt64          Read FResult Write SetResult;
    Property ResSize: UInt64          Read FResSize;
    Property Bytes:   Integer Index 8 Read GetSize;
    Property Bits:    Integer Index 1 Read GetSize;

    Procedure Clear;
  End;

Function TIntegerPack.GetMin(Index: Integer): Integer;
  Begin
    If Cardinal(Index) >= Length(FList) Then
      Raise Exception.CreateResFmt(@SListIndexError, [Index]);
    Result := FList[Index].Min;
  End;

Function TIntegerPack.GetMax(Index: Integer): Integer;
  Begin
    If Cardinal(Index) >= Length(FList) Then
      Raise Exception.CreateResFmt(@SListIndexError, [Index]);
    Result := FList[Index].Max;
  End;

Function TIntegerPack.GetVal(Index: Integer): Integer;
  Begin
    If Cardinal(Index) >= Length(FList) Then
      Raise Exception.CreateResFmt(@SListIndexError, [Index]);
    Result := FList[Index].Value;
  End;

Procedure TIntegerPack.SetVal(Index, X: Integer);
  Begin
    If Cardinal(Index) >= Length(FList) Then
      Raise Exception.CreateResFmt(@SListIndexError, [Index]);
    If (X < FList[Index].Min) or (X > FList[Index].Max) Then
      Raise Exception.CreateRes(@SArgumentOutOfRange);
    FList[Index].Value := X;

    FResult := 0;
    For Index := High(FList) downto 0 do
      With FList[Index] do
        FResult := FResult * Cardinal(Max - Min + 1) + Cardinal(Value - Min);
  End;

Procedure TIntegerPack.SetResult(X: UInt64);
  Var Index: Integer;

  Begin
    For Index := 0 to High(FList) do
      With FList[Index] do Begin
        Value := X mod Cardinal(Max - Min + 1) + Min;
        X     := X div Cardinal(Max - Min + 1);
      End;
    //If X <> 0 Then Raise ...;
    FResult := 0;
    For Index := High(FList) downto 0 do
      With FList[Index] do
        FResult := FResult * Cardinal(Max - Min + 1) + Cardinal(Value - Min);
  End;

Function TIntegerPack.GetSize(Bits: Integer): Integer;
  Var X: UInt64;

  Begin
    Result := 0;
    X := FResSize;
    While X <> 0 do Begin
      X := X shr Bits;
      Inc(Result);
    End;
  End;

Function TIntegerPack.Add(Min, Max: Integer; Value: Integer = MinInt): Integer;
  Var Index: Integer;
    X, T:   Int64;

  Begin
    Result := Length(FList);
    SetLength(FList, Result + 1);
    Try
      FList[Result].Min := Min;
      FList[Result].Max := Max;

      X := 1;
      For Index := High(FList) downto 0 do
        With FList[Index] do Begin
          T := X;
          X := X * Cardinal(Max - Min + 1);
          If X div Cardinal(Max - Min + 1) <> T Then
            Raise EIntOverflow.CreateRes(@SIntOverflow);
        End;
      FResSize := X;
    Except
      SetLength(FList, High(FList));
      Raise;
    End;
    If Value = MinInt Then Value := Min;
    SetVal(Result, Value);
  End;

Procedure TIntegerPack.Clear;
  Begin
    FList    := nil;
    FResult  := 0;
    FResSize := 0;
  End;

und noch'n Beispiel:

Delphi-Quellcode:

Uses Dialogs;

Var P: TIntegerPack;

Begin
  P.Add(1, 13);
  P.Add(0, 5);
  P.Add(-2, 3);
  P.Value[0] := 7;
  P.Value[1] := 3;
  P.Value[2] := 1;
  ShowMessage(Format('%d Bytes  >  %d Bits  >  $%.*x',
    [P.Bytes, P.Bits, P.Bytes * 2, P.Result]));

  P.Add(1, 13);
  P.Add(0, 5);
  P.Add(-2, 3);
  P.Result := $0117;
  ShowMessage(Format('%d  >  %d %d %d',
    [P.Result, P.Value[0], P.Value[1], P.Value[2]]));

[silver-moon-2000]

Ich stelle mir gerade die Frage, ob Ihr alle ein wenig zu kompliziert an die Sache rangegangen seid, oder ob ich es mir vielleicht doch zu leicht mache, aber ich verwende das folgende häufiger:

Zahlen zu einer "kombinieren"

Delphi-Quellcode:

kombinierteZahl := (zahl1 shl 16) + zahl2;

Zahlen wieder trennen

Delphi-Quellcode:

zahl1neu := (kombinierteZahl and FFFF0000) shr 16;
zahl2neu := kombinierteZahl and 0000FFFF;

Ok, zugegeben, damit ist der Zahlenbereich für zahl1 & zahl2 festgelegt auf 2^(SizeOf(Integer)/2), also Word = 65536, aber das sollte doch reichen, wenn man zwei Zahlen <=16 speichern will :stupid:

[edit]
ahh, siehste mal guck: MakeLong und MakeWord kannte ich noch nicht, wieder was gelernt

[divBy0]

Hatte ich doch beschrieben, mit High- und Low-Word. :-D

[silver-moon-2000]

Zitat:

Zitat von divBy0

Hatte ich doch beschrieben, mit High- und Low-Word. :-D

Aargh, sorry, noch ein Posting, das ich überlesen habe.
Scheint so, dass ich bei jedem Lesen des Threads neue Antworten in der Mitte finde, peinlich irgendwie :wall:

[himitsu]

@silver-moon-2000:
Macht ja nix, der TE kennt jetzt das Innere dieser Funktionen
und du hast ja auch gleich noch was gelernt.

Zitat:

Zitat von Jonelmeier

... das soll aber variabel bleiben).
...
Gibt es eine mathematische Lösung für das Problem?

Nun kann er sich variabel eine passende Lösung aussuchen
und verschiedene mathematische und bitverschieberische Lösungen wurden auch genannt.

[schöni]

Zitat:

Zitat von Meflin

Zunächst sucht man nun (durch ausprobieren?) die größte Zahl i (oben dargestellt durch die Funktion q), für die gilt f(i) <= 39. i ist in unserem Fall 8. Dann ist y = 39 - f(8) = 39 - 36 = 3.
x ergibt sich aus i - y = 8 - 3 = 5.

Und so isses auch in wissenschaflichen Fachbüchern erklärt. Da weiß ich aber immer noch nich, die größte Zah wovon.

Was also stellt diese magische Zahl i dar?

Und wofür steht q?

f(i) <= 39 kann zB sein: 39, 38, 37,...1, 0

Aber das sollte ja nun zu Rückberechnung der beiden gespeicherten Zahlen passen? Also bitte noch mal genauer erklären, damit ein unbedarfter das Beispeil auch nachvollziehen kann. Probieren, um die passende Zahl zu finden, reicht mir nicht. Im Extremfall probier ich dann alle zwischen 1 und 37 oder allgemein 1..X durch, was nicht gerade laufzeitfreundlich ist.

Oder ist i immer die Summe der beiden Zahlen.

Was wenn die Summe größer wird als dies Summe aus der Formel?

[Meflin]

Zitat:

Zitat von schöni

Was also stellt diese magische Zahl i dar?

Im Grunde das, was jeder Programmierer darunter versteht: Eine Schleifenvariable ;) Der offizielle Weg besteht darin, bei 0 beginnend f(i) auszurechnen, solange bis f(i) >= h (wobei h das Ergebnis der Paarungsfunktion ist). Das vorletzte (oder letzte im Fall =) Ergebnis bei Abbruch ist dann das gesuchte i.

Zitat:

Und wofür steht q?

Rein mathematisch gedacht bekommst du aus obigem Test eine Menge von Zahlen zurück, die die Bedingung (<= h) erfüllen. q ist die Funktion, die dir aus dieser Menge die Größte zurückgibt. Nicht mehr, aber auch nicht weniger.

Man kann i und damit die beiden Werte auch direkt berechnen:
i = floor(sqrt(2h) - 1/2)

(Online Formeleditor mit Einbindungsfunktion für Webseiten anybody?)