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

Yet another solution. This should handle all ints (including negative ints) except the min value of an int, which would need to be handled as a hard coded exception. This basically does division by subtraction but only using bit operators (shifts, xor, & and complement). For faster speed, it subtracts 3 * (decreasing powers of 2). In c#, it executes around 444 of these DivideBy3 calls per millisecond (2.2 seconds for 1,000,000 divides), so not horrendously slow, but no where near as fast as a simple x/3. By comparison, Coodey's nice solution is about 5 times faster than this one.

public static int DivideBy3(int a) {
    bool negative = a < 0;
    if (negative) a = Negate(a);
    int result;
    int sub = 3 << 29;
    int threes = 1 << 29;
    result = 0;
    while (threes > 0) {
        if (a >= sub) {
            a = Add(a, Negate(sub));
            result = Add(result, threes);
        }
        sub >>= 1;
        threes >>= 1;
    }
    if (negative) result = Negate(result);
    return result;
}
public static int Negate(int a) {
    return Add(~a, 1);
}
public static int Add(int a, int b) {
    int x = 0;
    x = a ^ b;
    while ((a & b) != 0) {
        b = (a & b) << 1;
        a = x;
        x = a ^ b;
    }
    return x;
}

This is c# because that's what I had handy, but differences from c should be minor.

Answer 2

Es ist wirklich ziemlich einfach.

if (number == 0) return 0;
if (number == 1) return 0;
if (number == 2) return 0;
if (number == 3) return 1;
if (number == 4) return 1;
if (number == 5) return 1;
if (number == 6) return 2;

(Ich habe natürlich etwas vom Programm der Kürze halber weggelassen.) Wenn der Programmierer müde wird, das alles auszutippen, bin ich sicher, dass er oder sie ein separates Programm schreiben könnte, um es für ihn zu generieren. Mir ist zufällig ein bestimmter Operator, /, bekannt, der seine Arbeit enorm vereinfachen würde.

Answer 3

Die Verwendung von Zählern ist eine grundlegende Lösung:

int DivBy3(int num) {
    int result = 0;
    int counter = 0;
    while (1) {
        if (num == counter)       // Modulus 0
            return result;
        counter = abs(~counter);  // ++counter

        if (num == counter)       // Modulus 1
            return result;
        counter = abs(~counter);  // ++counter

        if (num == counter)       // Modulus 2
            return result;
        counter = abs(~counter);  // ++counter

        result = abs(~result);    // ++result
    }
}

Es ist auch einfach, eine Modulus-Funktion durchzuführen, überprüfe die Kommentare.

Answer 4

Dies ist der klassische Division-Algorithmus zur Basis 2:

#include <stdio.h>
#include <stdint.h>

int main()
{
  uint32_t mod3[6] = { 0,1,2,0,1,2 };
  uint32_t x = 1234567; // Zahl zum Teilen und am Ende der Rest
  uint32_t y = 0; // Ergebnis
  int bit = 31; // aktuelles Bit
  printf("X=%u   X/3=%u\n",x,x/3); // das '/3' ist zum Testen

  while (bit>0)
  {
    printf("BIT=%d  X=%u  Y=%u\n",bit,x,y);
    // Bit dekrementieren
    int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; }
    uint32_t r = x>>bit;  // aktueller Rest im Bereich 0..5
    x ^= r<= 3) y |= 1<

Answer 5

Schreiben Sie das Programm in Pascal und verwenden Sie den DIV Operator.

Da die Frage mit c getaggt ist, können Sie wahrscheinlich eine Funktion in Pascal schreiben und sie aus Ihrem C-Programm aufrufen; die Methode dafür ist systemabhängig.

Hier ist jedoch ein Beispiel, das auf meinem Ubuntu-System mit dem Free Pascal fp-compiler Paket installiert funktioniert. (Ich mache das aus reiner, fehlgeleiteter Sturheit; Ich behaupte nicht, dass dies nützlich ist.)

divide_by_3.pas :

unit Divide_By_3;
interface
    function div_by_3(n: integer): integer; cdecl; export;
implementation
    function div_by_3(n: integer): integer; cdecl;
    begin
        div_by_3 := n div 3;
    end;
end.

main.c :

#include 
#include 

extern int div_by_3(int n);

int main(void) {
    int n;
    fputs("Geben Sie eine Zahl ein: ", stdout);
    fflush(stdout);
    scanf("%d", &n);
    printf("%d / 3 = %d\n", n, div_by_3(n));
    return 0;
}

Zum Kompilieren:

fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main

Beispielhafte Ausführung:

$ ./main
Geben Sie eine Zahl ein: 100
100 / 3 = 33