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

Verwenden Sie itoa, um in einen Basis-3-String umzuwandeln. Lassen Sie das letzte Trit fallen und konvertieren Sie zurück zur Basis 10.

// Hinweis: itoa ist nicht standardmäßig, aber tatsächliche Implementierungen
// scheinen negative Werte nicht zu handhaben, wenn die Basis != 10 ist.
int div3(int i) {
    char str[42];
    sprintf(str, "%d", INT_MIN); // Setze das Minuszeichen auf str[0]
    if (i>0)                     // Entferne das Vorzeichen, wenn positiv
        str[0] = ' ';
    itoa(abs(i), &str[1], 3);    // Setze ternären absoluten Wert beginnend bei str[1]
    str[strlen(&str[1])] = '\0'; // Letzte Ziffer entfernen
    return strtol(str, NULL, 3); // Ergebnis zurücklesen
}

Answer 2

(Hinweis: Eine bessere Version siehe unten in Edit 2!)

Dies ist nicht so knifflig, wie es scheint, weil du gesagt hast "ohne die [..] + [..] Operatoren zu verwenden". Siehe unten, wenn du das Zeichen + komplett verbieten möchtest.

unsigned div_by(unsigned const x, unsigned const by) {
  unsigned floor = 0;
  for (unsigned cmp = 0, r = 0; cmp <= x;) {
    for (unsigned i = 0; i < by; i++)
      cmp++; // das ist nicht der + Operator!
    floor = r;
    r++; // auch das nicht.
  }
  return floor;
}

dann sag einfach div_by(100,3), um 100 durch 3 zu teilen.

---

Edit: Du kannst auch den ++ Operator ersetzen:

unsigned inc(unsigned x) {
  for (unsigned mask = 1; mask; mask <<= 1) {
    if (mask & x)
      x &= ~mask;
    else
      return x & mask;
  }
  return 0; // Überlauf (beachte, dass sowohl x als auch mask hier 0 sind)
}

---

Edit 2: Etwas schnellere Version, ohne einen Operator zu verwenden, der die Zeichen +, -, *, /, % enthält.

unsigned add(char const zero[], unsigned const x, unsigned const y) {
  // das nutzt aus, dass &foo[bar] == foo+bar, wenn foo vom Typ char* ist
  return (int)(uintptr_t)(&((&zero[x])[y]));
}

unsigned div_by(unsigned const x, unsigned const by) {
  unsigned floor = 0;
  for (unsigned cmp = 0, r = 0; cmp <= x;) {
    cmp = add(0,cmp,by);
    floor = r;
    r = add(0,r,1);
  }
  return floor;
}

Wir verwenden das erste Argument der add Funktion, weil wir den Typ von Zeigern nicht ohne das Zeichen * angeben können, außer in Funktionsparamaterlisten, wo die Syntax type[] identisch mit type* const ist.

Übrigens, du kannst leicht eine Multiplikationsfunktion implementieren, indem du einen ähnlichen Trick wie den 0x55555556 Trick von AndreyT verwendest:

int mul(int const x, int const y) {
  return sizeof(struct {
    char const ignore[y];
  }[x]);
}

Answer 3

Es ist auf dem Setun-Computer leicht möglich.

Um eine Ganzzahl durch 3 zu teilen, verschieben Sie sich um 1 Stelle nach rechts.

Ich bin mir nicht sicher, ob es streng möglich ist, einen konformen C-Compiler auf einer solchen Plattform zu implementieren. Wir müssten die Regeln vielleicht etwas dehnen, indem wir "mindestens 8 Bits" als "fähig, mindestens Ganzzahlen von -128 bis +127 zu halten" interpretieren.

Answer 4

Hier ist meine Lösung:

public static int div_by_3(long a) {
    a <<= 30;
    for(int i = 2; i <= 32 ; i <<= 1) {
        a = add(a, a >> i);
    }
    return (int) (a >> 32);
}

public static long add(long a, long b) {
    long carry = (a & b) << 1;
    long sum = (a ^ b);
    return carry == 0 ? sum : add(carry, sum);
}

Zunächst beachte man, dass

1/3 = 1/4 + 1/16 + 1/64 + ...

Jetzt ist der Rest einfach!

a/3 = a * 1/3  
a/3 = a * (1/4 + 1/16 + 1/64 + ...)
a/3 = a/4 + a/16 + 1/64 + ...
a/3 = a >> 2 + a >> 4 + a >> 6 + ...

Jetzt müssen wir nur noch diese durch Bits verschobenen Werte von a zusammenzählen! Oops! Wir können jedoch nicht einfach addieren, daher müssen wir eine Additionsfunktion mit bitweisen Operatoren schreiben! Wenn Sie mit bitweisen Operatoren vertraut sind, sollte meine Lösung ziemlich einfach aussehen... aber nur für den Fall, dass Sie es nicht sind, werde ich am Ende ein Beispiel durchgehen.

Noch etwas zu beachten ist, dass ich zuerst um 30 Stellen nach links verschiebe! Dies dient dazu, sicherzustellen, dass die Brüche nicht abgerundet werden.

11 + 6

1011 + 0110  
sum = 1011 ^ 0110 = 1101  
carry = (1011 & 0110) << 1 = 0010 << 1 = 0100  
Jetzt wird rekursiv vorgegangen!

1101 + 0100  
sum = 1101 ^ 0100 = 1001  
carry = (1101 & 0100) << 1 = 0100 << 1 = 1000  
Wiederholung!

1001 + 1000  
sum = 1001 ^ 1000 = 0001  
carry = (1001 & 1000) << 1 = 1000 << 1 = 10000  
Noch einmal!

0001 + 10000
sum = 0001 ^ 10000 = 10001 = 17  
carry = (0001 & 10000) << 1 = 0

Fertig!

Es ist einfach die Addition mit Übertrag, die Sie als Kind gelernt haben!

111
 1011
+0110
-----
10001

Diese Implementierung ist fehlgeschlagen, weil wir nicht alle Begriffe der Gleichung addieren können:

a / 3 = a/4 + a/4^2 + a/4^3 + ... + a/4^i + ... = f(a, i) + a * 1/3 * 1/4^i
f(a, i) = a/4 + a/4^2 + ... + a/4^i

Angenommen, das Ergebnis von div_by_3(a) = x, dann x <= floor(f(a, i)) < a / 3. Wenn a = 3k ist, erhalten wir eine falsche Antwort.

Answer 5

Um eine 32-Bit-Nummer durch 3 zu teilen, kann man sie mit 0x55555556 multiplizieren und dann die oberen 32 Bits des 64-Bit-Ergebnisses nehmen.

Jetzt muss nur noch die Multiplikation unter Verwendung von Bitoperationen und Verschiebungen implementiert werden...