Wie teile ich mit 9 nur mit shifts / add / sub?

Question

Wie teile ich mit 9 nur mit shifts / add / sub?

8

Letzte Woche war ich in einem Interview und es gab einen solchen Test:

Berechne N/9 (vorausgesetzt dass N eine positive ganze Zahl ist), benutze nur UMSCHALTEN LINKS, UMSCHALTEN RECHTS, HINZUFÜGEN, SUBSTRACT Anweisungen.

algorithm assembly cpu-architecture integer-arithmetic

Tracy 21.03.2016, 03:39

quelle

2 Antworten

Tags und Links algorithm assembly cpu-architecture integer-arithmetic

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Fehler beim Starten Öffnen Sie MPI in MPI_Init über Python

score 2 · Answer 1

finde zuerst die Darstellung von 1/9 im Binärformat 0,0001110001110001
bedeutet, es ist (1/16) + (1/32) + (1/64) + (1/1024) + (1/2048) + (1/4096) + (1/65536)
so ist (x / 9) gleich (x & gt; & gt; 4) + (x & gt; & gt; 5) + (x & gt; & gt; 6) + (x & gt; & gt; 10) + ( x & gt; & gt; 11) + (x & gt; & gt; 12) + (x & gt; & gt; 16)

Mögliche Optimierung (wenn Schleifen erlaubt sind):
wenn Sie Schleife über 0001110001110001b nach rechts verschiebt es jede Schleife,
fügen Sie "x" zu Ihrem Ergebnisregister hinzu, wenn der Übertrag für diese Schicht festgelegt wurde und verschiebe jedes Mal dein Ergebnis nach rechts, Ihr Ergebnis ist x / 9

%Vor%

(kann derzeit nicht testen, kann falsch sein)

score 1 · Answer 2

Sie können einen Fixpunkt-Mathetrick verwenden.

Sie skalieren einfach so, dass der Teil mit dem signifikanten Bruch in den ganzzahligen Bereich geht, führen Sie die fraktionale mathematische Operation durch und skalieren Sie zurück.
%Vor%
Wie Sie sehen können, skaliere ich nach 10000 . Jetzt ist der ganzzahlige Teil von 10000/9=1111 groß genug, damit ich schreiben kann:
%Vor%
Stärke von 2 skalieren

Wenn Sie Skalen mit der Stärke 2 verwenden, müssen Sie nur Bit-Shift statt Division verwenden. Sie müssen Kompromisse zwischen Genauigkeit und Eingabewertbereich eingehen. Ich habe empirisch gefunden, dass die beste Skala für 32 bit arithmetics 1<<18 so ist:
%Vor%
Der (a+1) korrigiert die Rundungsfehler wieder auf den richtigen Bereich.
Hardcodierte Multiplikation

Schreiben Sie die Multiplikationskonstante in binär
um %Vor%
Wenn Sie nun c=(a*q) berechnen müssen, verwenden Sie eine hartcodierte binäre Multiplikation: für jede 1 von q können Sie a<<(position_of_1) zur c hinzufügen. Wenn Sie etwas wie 111 sehen, können Sie es in 1000-1 umschreiben, indem Sie die Anzahl der Operationen minimieren.

Wenn Sie all das zusammensetzen, sollten Sie etwas wie diesen C ++ Code von mir haben:
%Vor%
Wenn Sie nun die Binärform sehen, wiederholt sich das Muster 111000 , so dass Sie den Code ein wenig verbessern können:
%Vor%