Div 2 durch Subtraktion

[TheAn00bis]

Hey,

Eine Zahl mit zwei zu multiplizieren, ohne die Multiplikation zu verwenden ist ja kein Problem,
ich addiere die Zahl einfach zu sich selbst, geht dass auch für die Division durch 2?

Gibt es auch eine Möglichkeit eine gerade Zahl zu halbieren, ohne die Division zu verwenden?

[BlackJack]

das könnte man mit shifts machen:

Delphi-Quellcode:

var Zahl, ZahlDiv2: Integer;
begin
Zahl := 1024;
ZahlDiv2 := Zahl shr 1; //ZahlDiv2 = 512
end;

oder allgemein

Code:

Zahl div 2^k = Zahl shr k

wenn ich mich nicht irre

wobei ich denke dass der Delphi-kompiler aus einem div 2 eh ein shr 1 machen wird.

edit: für multiplikation geht das übrigens auch:

Code:

Zahl * 2^k = Zahl shl k

[s-off]

Hallo,

Zitat von TheAn00bis:

[...]ich addiere die Zahl einfach zu sich selbst, geht dass auch für die Division durch 2?
Gibt es auch eine Möglichkeit eine gerade Zahl zu halbieren, ohne die Division zu verwenden?

mit 0,5 multiplizieren.... öhm - zu hoch für mich ^^

[BenjaminH]

Nunja, shl(x:=x shl 1;//x wird verdoppelt) bzw. shr(x:=x shr 1;//x wird halbiert) machen das, aber ich glaube das meinst du nicht.
Du könntest solange von der Zahl 1 abziehen, bis das Ergebnis mal zwei kleiner oder gleich der Ausgangszahl ist:

Delphi-Quellcode:

function DividebySubtraction(n:Integer);
Begin
  Result:=n;
  while (Result+Result)>n do
    Dec(Result);
End;

[Edit]Habs in ne Funktion gepackt
Aber was für einen Sinn soll das haben?

[Hawkeye219]

Die Lösung mit SHR funktioniert aber nur für positive Zahlen.

Gruß Hawkeye

[Dax]

Dann bauen wir uns eine Funktion SignedSHR die wie folgt aussieht

Delphi-Quellcode:

function SignedSHR(Number, By: Integer): Integer;
asm
  sar eax, edx
end;

[TheAn00bis]

Zitat von BenjaminH:

Nunja, shl(x:=x shl 1;//x wird verdoppelt) bzw. shr(x:=x shr 1;//x wird halbiert) machen das, aber ich glaube das meinst du nicht.
Du könntest solange von der Zahl 1 abziehen, bis das Ergebnis mal zwei kleiner oder gleich der Ausgangszahl ist:

Delphi-Quellcode:

function DividebySubtraction(n:Integer);
Begin
  Result:=n;
  while (Result+Result)>n do
    Dec(Result);
End;

[Edit]Habs in ne Funktion gepackt
Aber was für einen Sinn soll das haben?

Danke!

Der Algorithmus ist gut.

Zum Sinn:
Ich wollte die Multiplikation von zwei natürlichen Zahlen nur mit Addition und Subtraktion durchführen, da diese maschinentechnisch gesehen leichter zu verstehen sind; ganz im Gegensatz zur Multiplikation und Division. Mein
Algorithmus zur Multiplikation benötigt aber an zwei Stellen die Division durch 2 und ich wusste nicht, wie ich die
umsetzen kann; jetzt weiß ich es. Danke.

Edit: Wie funktioniert dieses shr denn? Irgendwie über Verschiebung?


Edit2: Achja, ich muss Binär ja nur die erste Stelle weglasse...

Edit3: Achwas, ich bin bescheuert, vergesst Edit2 bitte.

[BenjaminH]

Aber vorsicht, es wird immer abgerundet!

[kleiner Unwissender]

Soweit ich weiß kann man jede Mathematische Operation auf die Addition zurückführen (auch logarithmus).
Mein DVT Lehrer hat ein altes Buch wo das drinne Beschrieben is, aber ich selbst hab da leider keine Ahnung von. Geh doch mal in eine Bibliothek.