[c] Teilen Sie eine Zahl mit 3, ohne die Operatoren *, /, +, -,% zu verwenden



14 Answers

Idiotische Bedingungen erfordern eine idiotische Lösung:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE * fp=fopen("temp.dat","w+b");
    int number=12346;
    int divisor=3;
    char * buf = calloc(number,1);
    fwrite(buf,number,1,fp);
    rewind(fp);
    int result=fread(buf,divisor,number,fp);
    printf("%d / %d = %d", number, divisor, result);
    free(buf);
    fclose(fp);
    return 0;
}

Wenn auch der Dezimalteil benötigt wird, deklarieren Sie einfach das result als double und addieren Sie dazu das Ergebnis von fmod(number,divisor) .

Erklärung wie es funktioniert

  1. Das fwrite schreibt number Bytes (Nummer ist 123456 im obigen Beispiel).
  2. rewind setzt den Dateizeiger auf den Anfang der Datei zurück.
  3. fread liest maximal eine number "Records", die eine Länge von der Datei haben, und gibt die Anzahl der gelesenen Elemente zurück.

Wenn Sie 30 Bytes schreiben und die Datei in Einheiten von 3 zurücklesen, erhalten Sie 10 "Einheiten". 30/3 = 10

Question

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

Die Nummer kann signiert oder nicht signiert sein.




Noch eine andere Lösung. Dies sollte alle Eingaben (einschließlich negativer Eingaben) außer dem min-Wert eines int behandeln, der als hart codierte Ausnahme behandelt werden müsste. Dies geschieht grundsätzlich durch Subtraktion, aber nur mit Bitoperatoren (shifts, xor, & und complement). Für eine schnellere Geschwindigkeit subtrahiert es 3 * (abnehmende Potenzen von 2). In c # führt es etwa 444 dieser DivideBy3-Aufrufe pro Millisekunde (2,2 Sekunden für 1.000.000 Teilungen) aus, also nicht schrecklich langsam, aber nicht annähernd so schnell wie ein einfaches x / 3. Im Vergleich dazu ist Coodeys nette Lösung ungefähr fünfmal schneller als diese.

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;
}

Das ist c #, weil ich das praktisch hatte, aber die Unterschiede zu c sollten gering sein.




Verwenden Sie itoa , um in eine Basis-3-Zeichenfolge zu konvertieren. trit den letzten trit und konvertiere zurück zur Basis 10.

// Note: itoa is non-standard but actual implementations
// don't seem to handle negative when base != 10.
int div3(int i) {
    char str[42];
    sprintf(str, "%d", INT_MIN); // Put minus sign at str[0]
    if (i>0)                     // Remove sign if positive
        str[0] = ' ';
    itoa(abs(i), &str[1], 3);    // Put ternary absolute value starting at str[1]
    str[strlen(&str[1])] = '\0'; // Drop last digit
    return strtol(str, NULL, 3); // Read back result
}



Okay, ich denke, wir sind uns alle einig, dass das kein wirkliches Problem ist. Also nur zum Spaß, hier ist, wie es mit Ada und Multithreading zu tun ist:

with Ada.Text_IO;

procedure Divide_By_3 is

   protected type Divisor_Type is
      entry Poke;
      entry Finish;
   private
      entry Release;
      entry Stop_Emptying;
      Emptying : Boolean := False;
   end Divisor_Type;

   protected type Collector_Type is
      entry Poke;
      entry Finish;
   private
      Emptying : Boolean := False;
   end Collector_Type;

   task type Input is
   end Input;
   task type Output is
   end Output;

   protected body Divisor_Type is
      entry Poke when not Emptying and Stop_Emptying'Count = 0 is
      begin
         requeue Release;
      end Poke;
      entry Release when Release'Count >= 3 or Emptying is
         New_Output : access Output;
      begin
         if not Emptying then
            New_Output := new Output;
            Emptying := True;
            requeue Stop_Emptying;
         end if;
      end Release;
      entry Stop_Emptying when Release'Count = 0 is
      begin
         Emptying := False;
      end Stop_Emptying;
      entry Finish when Poke'Count = 0 and Release'Count < 3 is
      begin
         Emptying := True;
         requeue Stop_Emptying;
      end Finish;
   end Divisor_Type;

   protected body Collector_Type is
      entry Poke when Emptying is
      begin
         null;
      end Poke;
      entry Finish when True is
      begin
         Ada.Text_IO.Put_Line (Poke'Count'Img);
         Emptying := True;
      end Finish;
   end Collector_Type;

   Collector : Collector_Type;
   Divisor : Divisor_Type;

   task body Input is
   begin
      Divisor.Poke;
   end Input;

   task body Output is
   begin
      Collector.Poke;
   end Output;

   Cur_Input : access Input;

   -- Input value:
   Number : Integer := 18;
begin
   for I in 1 .. Number loop
      Cur_Input := new Input;
   end loop;
   Divisor.Finish;
   Collector.Finish;
end Divide_By_3;



Da es sich um Oracle handelt, wie wäre es mit einer Nachschlagetabelle mit vorberechneten Antworten. :-D




#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{

    int num = 1234567;
    int den = 3;
    div_t r = div(num,den); // div() is a standard C function.
    printf("%d\n", r.quot);

    return 0;
}



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

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

Ich bin mir nicht sicher, ob es überhaupt möglich ist, einen konformen C-Compiler auf einer solchen Plattform zu implementieren. Wir müssen vielleicht die Regeln ein wenig ausdehnen, wie "mindestens 8 Bits" als "fähig interpretieren, mindestens ganze Zahlen von -128 bis +127 zu halten".




Zuerst, dass ich mir vorgestellt habe.

irb(main):101:0> div3 = -> n { s = '%0' + n.to_s + 's'; (s % '').gsub('   ', ' ').size }
=> #<Proc:0x0000000205ae90@(irb):101 (lambda)>
irb(main):102:0> div3[12]
=> 4
irb(main):103:0> div3[666]
=> 222

EDIT: Entschuldigung, ich habe das Tag C nicht bemerkt. Aber Sie können die Idee über die Formatierung von Strings verwenden, denke ich ...




Mit Hacker's Delight Magic Zahlenrechner

int divideByThree(int num)
{
  return (fma(num, 1431655766, 0) >> 32);
}

Wobei fma eine Standardbibliotheksfunktion ist, die in der Kopfzeile math.h definiert ist.




Verwenden Sie cblas , das Teil des Accelerate-Frameworks von OS X ist.

[02:31:59] [william@relativity ~]$ cat div3.c
#import <stdio.h>
#import <Accelerate/Accelerate.h>

int main() {
    float multiplicand = 123456.0;
    float multiplier = 0.333333;
    printf("%f * %f == ", multiplicand, multiplier);
    cblas_sscal(1, multiplier, &multiplicand, 1);
    printf("%f\n", multiplicand);
}

[02:32:07] [william@relativity ~]$ clang div3.c -framework Accelerate -o div3 && ./div3
123456.000000 * 0.333333 == 41151.957031



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üfen Sie die Kommentare.




Ich denke, die richtige Antwort ist:

Warum sollte ich einen Basisoperator nicht für eine grundlegende Operation verwenden?




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

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

Aber hier ist ein Beispiel, das auf meinem Ubuntu-System mit dem installierten Free Pascal fp-compiler Paket funktioniert. (Ich tue dies aus reiner fehlgeleiteter Sturheit; ich behaupte nicht, dass das 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 <stdio.h>
#include <stdlib.h>

extern int div_by_3(int n);

int main(void) {
    int n;
    fputs("Enter a number: ", stdout);
    fflush(stdout);
    scanf("%d", &n);
    printf("%d / 3 = %d\n", n, div_by_3(n));
    return 0;
}

Bauen:

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

Beispielausführung:

$ ./main
Enter a number: 100
100 / 3 = 33



Dies sollte für jeden Divisor funktionieren, nicht nur für drei. Derzeit nur für unsigned, aber zu signed sollte nicht so schwierig sein.

#include <stdio.h>

unsigned sub(unsigned two, unsigned one);
unsigned bitdiv(unsigned top, unsigned bot);
unsigned sub(unsigned two, unsigned one)
{
unsigned bor;
bor = one;
do      {
        one = ~two & bor;
        two ^= bor;
        bor = one<<1;
        } while (one);
return two;
}

unsigned bitdiv(unsigned top, unsigned bot)
{
unsigned result, shift;

if (!bot || top < bot) return 0;

for(shift=1;top >= (bot<<=1); shift++) {;}
bot >>= 1;

for (result=0; shift--; bot >>= 1 ) {
        result <<=1;
        if (top >= bot) {
                top = sub(top,bot);
                result |= 1;
                }
        }
return result;
}

int main(void)
{
unsigned arg,val;

for (arg=2; arg < 40; arg++) {
        val = bitdiv(arg,3);
        printf("Arg=%u Val=%u\n", arg, val);
        }
return 0;
}



Wäre es schummeln, den / Operator "hinter den Kulissen" zu verwenden, indem Sie eval und String-Verkettung verwenden?

Zum Beispiel, in JavaScript, können Sie tun

function div3 (n) {
    var div = String.fromCharCode(47);
    return eval([n, div, 3].join(""));
}



Related