Binärdarstellung einer Zahl mit einer einzigen Stringallokation

[BUG]

Hallo,

ausgehend von diesem Thread habe ich mir überlegt, wie man eine Umwandlung in Binärdarstellung ohne Änderung der Länge des Strings hinbekommen könnte (ohne die Umrechnung einfach zweimal zu machen).

Herausgekommen ist dann dieses Monster, das die Länge der Binärdarstellung mit binärer Suche findet

Delphi-Quellcode:

function intToBin(x: cardinal) : string;
var
 offset: integer;
 nextOffset: integer;
 lbits: integer;
 i: integer;
begin
  lbits := 0;
  offset := sizeof(cardinal)*8;
  // binäre Suche der richtige Größe
  while (offset > 0) and (cardinal(1 shl (lbits+offset-1)) > x) do
  begin // Maske kann verkleinert werden
    nextOffset := offset div 2; // immer kleiner
    if ((high(cardinal) shl (lbits + nextOffset)) and x) = 0 then
    begin
      // Maske der nicht von lbits + nextOffset abgedeckten Bits überdeckt keine Bits von x
      // -> Wir kennen bessere obere Schranke :)
      offset := nextOffset;
    end else begin
      // Wir haben eine bessere untere Schranke :)
      lbits := lbits + nextOffset + 1; // lbits + nextOffset ist definitiv zu klein
      offset := offset - nextOffset - 1; // offset so anpassen, dass lbit + offest gleich bleibt
    end;
  end;
  lbits := lbits + offset;
  if lbits = 0 then inc(lbits); // mindestens eine Stelle wollen wir haben
  setLength(intToBin, lbits);
  // jetzt nur noch das eigentliche Umwandeln
  for i := 0 to lbits-1 do
  begin
    if (x and 1) = 0
      then intToBin[lbits-i] := '0'
      else intToBin[lbits-i] := '1';
    x := x shr 1;
  end;
end;

Dann mir eingefallen, dass das vermutlich viel schneller geht:

Delphi-Quellcode:

function intToBin(x: cardinal) : string;
const
  maxLength = sizeof(cardinal)*8;
var
  buffer: array[0..maxLength-1] of char;
  digits: integer;
begin
  digits := 0;
  repeat
    inc(digits);
    if (1 and x) = 0
      then buffer[maxLength-digits] := '0'
      else buffer[maxLength-digits] := '1';
    x := x shr 1;
  until (x = 0);
  setLength(intToBin, digits);
  move(&buffer[maxLength-digits], &intToBin[1], sizeof(char)*digits);
end;

Auch hier wird der Heap nur einmal gequält, dafür aber ein Buffer auf dem Stack angelegt.


Damit ich das nicht völlig umsonst geschrieben habe, könnt ihr es jetzt angucken und als Übung dafür nehmen, verworrenen Code zu lesen. Kommentare sind erlaubt

[Medium]

Stringlänge := Ceil(Lb(Zahlenwert))

Delphi-Quellcode:

var
  i, k, len: Integer;
begin
  k := 1;
  if x>0 then
  begin
    len := Ceil(Lb(x));
    SetLength(result, len);
    dec(k);
  else
  if x<0 then
  begin
    len := Ceil(Lb(x))+1;
    SetLength(result, len);
    result[k] := '-';
    x := -x;
  end
  else
  begin
    result := '0';
    Exit;
  end;

  for i := 1 to Length(result)-k do
    result[i+k] := Chr(((x shr (len-i+1)) and 1)+Ord('0'));
end;

Ungetestet und nur für 8-Bit Strings. Möglich, dass der Laufindex noch versetzt ist, aber ich will ins Bett

[Furtbichler]

Zitat von BUG:

und als Übung dafür nehmen, verworrenen Code zu lesen. Kommentare sind erlaubt

Der Code ist gar nicht so verworren, nur die Herleitung der Lösung ein klassisches Beispiel für "von Hinten durch die Brust ins Auge".

[DeddyH]

Wenn die Ausgabe immer in der tatsächlichen Bitbreite erfolgen soll:

Delphi-Quellcode:

function IntToBin(AInt: Cardinal): string;
const
  BITSPERBYTE = 8;
  BITCHARS: array[Boolean] of char = ('0', '1');
var
  BitPos: byte;
  CurrentBit: Cardinal;
begin
  SetLength(Result, SizeOf(AInt) * BITSPERBYTE);
  CurrentBit := 1;
  for BitPos := Length(Result) downto 1 do
    begin
      Result[BitPos] := BITCHARS[(AInt and CurrentBit) = CurrentBit];
      CurrentBit := CurrentBit shl 1;
    end;
end;

[Aphton]

Die Anzahl der Stellen kann man doch einfach so ermitteln:

Delphi-Quellcode:

var
  digits: Integer;
begin
  digits := ceil(log(Value)/log(2));
  {...}
end;

Oder geht es gar nicht darum?

Delphi-Quellcode:

function IntToBin(Value: Integer): String;
var
  i: Integer;
  j: Double;
const
  BitValues: Array[Boolean] of Char = ('0', '1');
begin
  if Value = 0 then
    Result := '0'
  else
  begin
    j := Log2(Value);
    i := Ceil(j);
    if IsZero(Frac(j)) then inc(i);
    SetLength(Result, i);
    while i > 0 do
    begin
      Result[i] := BitValues[(Value and 1) = 1];
      Value := Value shr 1;
      dec(i);
    end;
  end;
end;

[Medium]

Doch, siehe meinen Beitrag. Und Furtis

[jfheins]

Also diese Aufgabenstellung lässt sich sicher wieder auf 5 Seiten auswalzen ^^

Falls der Code einfach zu verstehen sein soll, würde ich die Lösung mit dem Logarithmus bevorzugen.
Result := Ceil(Math.Log2(Value));

Wenn das zu langsam ist, könntest du es mit der FPU versuchen:
1. Gibt es wohl einen Opcode für den Log2: FYL2X
2. Schreibe die Zahl in ein FPU Register und lese (durch einen Bitshift oder so) den Exponenten aus. (Trick 17 ^^)

[gammatester]

Noch ein Vorschlag, das Prinzip: Ermittele das höchste gesetzte Bit, allokiere den String und verarbeite die restlichen Bits.

Delphi-Quellcode:

function IntToBin(x: cardinal): string;
var
  i,n: integer;
  m: cardinal;
begin
  if x=0 then Result := '0'
  else begin
    {Teil 1: Bestimme höchstes gesetztes Bit}
    m := cardinal($80000000);
    n := 32;
    while m and x = 0 do begin
      dec(n);
      m := m shr 1;
    end;
    {Teil 2: Allokieren und Bits abarbeiten, n>0 da x<>0!}
    Setlength(Result,n);
    for i:=1 to n do begin
      if m and x <> 0 then Result[i] := '1'
      else Result[i] := '0';
      m := m shr 1;
    end;
  end;
end;

[Amateurprofi]

warum einfach und schnell wenns auch kompliziert und langsam geht?

Delphi-Quellcode:

FUNCTION IntToBin(v:cardinal):string;
FUNCTION NeededLength(v:cardinal):integer;
asm
      bsr   eax,eax
      jnz   @1
      xor   eax,eax
@1:   add   eax,1
end;
var i:integer;
begin
   i:=NeededLength(v);
   SetLength(result,i);
   repeat
      result[i]:=Chr(Ord('0') or v and 1);
      dec(i);
      v:=v shr 1;
   until i=0;
end;

[BUG]

Zitat von gammatester:

Noch ein Vorschlag, das Prinzip: Ermittele das höchste gesetzte Bit, allokiere den String und verarbeite die restlichen Bits.

Das ist das Prinzip (fast) aller hier vorgestellten Codes

Mein Gedanken für die binäre Suche war, das man nicht alle Bits zweimal angucken muss. Der Aufwand für einen Schleifendurchlauf ist vielleicht etwas zu hoch.

Zitat von jfheins:

Gibt es wohl einen Opcode für den Log2 FYL2X

Ich würde doch hoffen, das lb den benutzt.

Wenn ich es einsetzen müsste, würde ich wohl den Vorschlag von Amateurprofi wählen: keine Gleitkommazahlen und ohne Umwege. Aber kein pures Delphi/Pascal