Binärdarstellung einer Zahl mit einer einzigen Stringallokation

[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

[gammatester]

Zitat von BUG:

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.
...
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

Wahrscheinlich hast Du nicht genau hingesehen, aber bei meinem Code werden die Bits nur einmal angesehen (bis auf das höchste, aber das könnte man auch noch wegoptimieren).

Im Übrigen macht Amateurprofis NeededLength auch nichts wesentlich anderes, und ich bezweifele, ob ein Funktionsaufruf und langsames bsr schneller sind. Weiter kann man natürlich auch die finale Schleife rückwarts durchlaufen, hier also der kombinierte Code in Pur-Pascal:

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:=n downto 1 do begin
      Result[i] := Chr(Ord('0') or (x and 1));
      x := x shr 1;
    end;
  end;
end;

[p80286]

wie wäre es hiermit?

Delphi-Quellcode:

fuction GetLengthofBinString(z:longword):integer;
  i : integer;
begin
  result:=0;
  for i:=0 to 31 do
    if (z and (1 shl i))<>0 then result:=i+1;
end;

Gruß
K-H