Teilen Sie eine Zahl durch 3, ohne * , / , + , - , % Operatoren zu verwenden

Question

Wie würden Sie eine Zahl durch 3 teilen, ohne die *, /, +, -, % Operatoren zu verwenden?

Die Zahl kann positiv oder negativ sein.

Answer 1

Ich würde diesen Code verwenden, um alle positiven, nicht-gleitkommazahlen zu teilen. Im Grunde möchten Sie die Divisor-Bits nach links ausrichten, um mit den Dividend-Bits übereinzustimmen. Für jedes Segment des Dividenden (Größe des Divisors) möchten Sie überprüfen, ob das Segment des Dividendens größer ist als der Divisor, dann möchten Sie nach links verschieben und im ersten Register ODERen. Dieses Konzept wurde ursprünglich 2004 erstellt (ich glaube Stanford), Hier ist eine C-Version, die dieses Konzept verwendet. Hinweis: (Ich habe es ein bisschen modifiziert)

int divide(int a, int b)
{
    int c = 0, r = 32, i = 32, p = a + 1;
    unsigned long int d = 0x80000000;

    while ((b & d) == 0)
    {
        d >>= 1;
        r--;
    }

    while (p > a)
    {
        c <<= 1;
        p = (b >> i--) & ((1 << r) - 1);
        if (p >= a)
            c |= 1;
    }
    return c; //p ist der Rest (für Modulus)
}

Beispiel Verwendung:

int n = divide( 3, 6); //Ausgabe 2

Answer 2

Wo InputValue die Zahl ist, durch die durch 3 geteilt wird

SELECT AVG(NUM) 
  FROM (SELECT InputValue NUM from sys.dual
         UNION ALL SELECT 0 from sys.dual
         UNION ALL SELECT 0 from sys.dual) divby3

Answer 3

Es scheint, dass niemand das Teilungskriterium für 3, das in binärer Darstellung dargestellt wird, erwähnt hat - die Summe der geraden Ziffern sollte der Summe der ungeraden Ziffern entsprechen (ähnlich dem Kriterium von 11 im Dezimalsystem). Es gibt Lösungen, die diesen Trick nutzen unter Überprüfen Sie, ob eine Zahl durch 3 teilbar ist.

Ich vermute, dass dies das mögliche Duplikat ist, auf das Michael Burrs Bearbeitung hingewiesen hat.

Answer 4

Um eine Zahl durch 3 zu teilen, ohne Multiplikation, Division, Rest, Subtraktion oder Addition in der Assembly-Programmiersprache zu verwenden, stehen nur die Befehle LEA (Addresseffektives Laden), SHL (nach links verschieben) und SHR (nach rechts verschieben) zur Verfügung.

Mit dieser Lösung habe ich keine Operationen verwendet, die mit den Operatoren + - * /% verbunden sind.

Ich gehe davon aus, dass die Ausgabezahl im Festkommaformat vorliegt (16 Bit für den Ganzzahlteil und 16 Bit für den Dezimalteil) und die Eingangsnummer vom Typ short int ist; ich habe jedoch die Anzahl der Ausgaben approximiert, da ich nur dem Ganzzahlteil vertrauen kann und daher einen Wert vom Typ short int zurückgebe.

65536/6 ist der Festkomma-Wert, der dem Gleitkomma-Wert 1/3 entspricht und gleich 21845 ist.

21845 = 16384 + 4096 + 1024 + 256 + 64 + 16 + 4 + 1.

Also, um die Multiplikation mit 1/3 (21845) durchzuführen, verwende ich die Befehle LEA und SHL.

short int DivideBy3( short int num )
//In : eax= 16 Bit short int Eingangsnummer (N)
//Out: eax= N/3 (32 Bit Festkommazahl-Ausgangsnummer
//          (Bit31-Bit16: Ganzzahlteil, Bit15-Bit0: Zahlen nach dem Punkt)
{
   __asm
   {
      movsx eax, num          // Erster Argument

      // 65536 / 3 = 21845 = 16384 + 4096 + 1024 + 256 + 64 + 16 + 4 + 1

      lea edx,[4*eax+eax]     // EDX= EAX * 5
      shl eax,4
      lea edx,[eax+edx]       // EDX= EDX + EAX * 16
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 64
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 256
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 1024
      shl eax,2
      lea edx,[eax+edx]       // EDX= EDX + EAX * 4096
      shl eax,2
      lea edx,[eax+edx+08000h] // EDX= EDX + EAX * 16384

      shr edx,010h
      movsx eax,dx

   }
   // Ergebnis in EAX zurückgeben
}

Es funktioniert auch mit negativen Zahlen; das Ergebnis hat eine minimale Approximation mit positiven Zahlen (-1 auf der letzten Ziffer nach dem Punkt).

Wenn Sie vorhaben, die Operatoren + - * /% nicht zu verwenden, um die Division durch 3 durchzuführen, aber die damit verbundenen Operationen verwenden können, schlage ich eine zweite Lösung vor.

int DivideBy3Bis( short int num )
//In : eax= 16 Bit short int Eingangsnummer (N)
//Out: eax= N/3 (32 Bit Festkommazahl-Ausgangsnummer
//          (Bit31-Bit16: Ganzzahlteil, Bit15-Bit0: Zahlen nach dem Punkt)
{
   __asm
   {
      movsx   eax, num        // Erster Argument

      mov     edx,21845
      imul    edx
   }
   // Ergebnis in EAX zurückgeben
}

Answer 5

3 in Basis 2 ist 11.

Machen Sie also einfach die lange Division (wie in der Mittelschule) in Basis 2 durch 11. Es ist sogar einfacher in Basis 2 als in Basis 10.

Für jede Bit-Position, beginnend mit dem wichtigsten:

Entscheiden Sie, ob das Präfix kleiner als 11 ist.

Wenn es kleiner ist, geben Sie 0 aus.

Wenn es nicht kleiner ist, geben Sie 1 aus, und dann ersetzen Sie die Präfix-Bits durch die entsprechende Änderung. Es gibt nur drei Fälle:

 11xxx ->    xxx    (d.h. 3 - 3 = 0)
100xxx ->   1xxx    (d.h. 4 - 3 = 1)
101xxx ->  10xxx    (d.h. 5 - 3 = 2)

Alle anderen Präfixe sind unerreichbar.

Wiederholen Sie dies bis zur niedrigsten Bit-Position und Sie sind fertig.