@AlexandreC. - Diese Techniken verwenden jedoch Addition (+).
Beil - fertig mit SOverflow
19
Dies war Orakel. Welche Teile des Orakels durften Sie verwenden?
Hogan
8
Das identifizierte Duplikat ist kein Duplikat. Beachten Sie, dass einige Antworten hier weder Bitverschiebung noch Addition verwenden, da diese Frage keine Lösung für diese Operationen einschränkte.
Dies ist eine einfache Funktion, die die gewünschte Operation ausführt. Da jedoch der +Operator erforderlich ist , müssen Sie nur noch die Werte mit Bitoperatoren hinzufügen:
// replaces the + operatorint add(int x,int y){while(x){int t =(x & y)<<1;
y ^= x;
x = t;}return y;}int divideby3(int num){int sum =0;while(num >3){
sum = add(num >>2, sum);
num = add(num >>2, num &3);}if(num ==3)
sum = add(sum,1);return sum;}
Wie Jim kommentierte, funktioniert dies, weil:
n = 4 * a + b
n / 3 = a + (a + b) / 3
So sum += a, n = a + bund iterate
Wenn a == 0 (n < 4), sum += floor(n / 3);dh 1,if n == 3, else 0
Dies ist wahrscheinlich die Antwort, nach der Oracle sucht. Es zeigt Ihnen, wie die Operatoren +, -, * und / tatsächlich auf der CPU implementiert sind: einfache bitweise Operationen.
craig65535
21
Dies funktioniert, weil n = 4a + b, n / 3 = a + (a + b) / 3, also Summe + = a, n = a + b und Iteration. Wenn a == 0 (n <4) ist, ist Summe + = Boden (n / 3); dh 1 wenn n == 3, sonst 0.
Jim Balter
7
Hier ist ein Trick, den ich gefunden habe und der mir eine ähnliche Lösung gebracht hat. In Dezimalzahlen: 1 / 3 = 0.333333Die sich wiederholenden Zahlen erleichtern die Berechnung mit a / 3 = a/10*3 + a/100*3 + a/1000*3 + (..). In der Binärdatei ist es fast dasselbe: 1 / 3 = 0.0101010101 (base 2)was dazu führt a / 3 = a/4 + a/16 + a/64 + (..). Durch Teilen durch 4 kommt die Bitverschiebung. Die letzte Überprüfung von num == 3 ist erforderlich, da wir nur Ganzzahlen haben, mit denen wir arbeiten können.
Yorick Sijsling
4
In Base 4 wird es noch besser : a / 3 = a * 0.111111 (base 4) = a * 4^-1 + a * 4^-2 + a * 4^-3 + (..) = a >> 2 + a >> 4 + a >> 6 + (..). Die Basis 4 erklärt auch, warum am Ende nur 3 aufgerundet wird, während 1 und 2 abgerundet werden können.
Yorick Sijsling
2
@ while1: Es ist bitweise UND-Operation. Eine bekannte Tatsache ist auch, dass für n == 2^kFolgendes gilt : x % n == x & (n-1), wird hier num & 3also verwendet, um auszuführen, num % 4solange dies %nicht erlaubt ist.
Aplavin
436
Idiotische Bedingungen erfordern eine idiotische Lösung:
@earlNameless: Sie wissen nicht, was sie im Inneren verwenden, sie befinden sich in der Blackbox "Implementierung definiert". Nichts hindert sie daran, nur bitweise Operatoren zu verwenden. Auf jeden Fall befinden sie sich außerhalb der Domäne meines Codes, das ist also nicht mein Problem. :)
Matteo Italia
8
@IvoFlipse von Ich kann putzen, du bekommst ein großes Etwas und schiebst es in etwas dreimal zu Kleines und siehst dann, wie viel hineinpasst. Das ist ungefähr ein Drittel.
Pureferret
27
bat den besten C-Programmierer (und den sozial umständlichsten) in unserem Unternehmen, den Code zu erklären. Nachdem er es getan hatte, sagte ich, es sei ziemlich genial. Er sagte, "dieser Dreck ist keine Lösung" und bat mich, seinen Schreibtisch zu verlassen
siehe Verletzung
6
@cvverletzung Ich denke der Punkt ist, dass die Frage so hirntot ist, dass eine hirntote Antwort erlaubt ist. Der "beste C-Programmierer" in Ihrem Unternehmen "hätte genauso gut sagen können," dass Dreck keine (richtige) Frage ist ".
JeremyP
17
@ JeremyP: genau. Mein Punkt ist, dass, wenn ich im wirklichen Leben einen Compiler ohne Unterstützung für Arithmetik bekommen würde, es nur sinnvoll wäre, nach einem besseren Compiler zu fragen , da das Arbeiten unter diesen Bedingungen keinen Sinn ergibt. Wenn der Interviewer mein Wissen über die Implementierung von Division mit bitweisen Operationen überprüfen wollte, konnte er einfach sein und es als theoretische Frage stellen. Diese Art von "Trickübungen" schreien nur nach Antworten wie diesen.
@bitmask, mathematische Funktionen werden normalerweise direkt in asm implementiert.
SingerOfTheFall
7
Ich habe es gerade in meine JS-Konsole eingegeben, es funktioniert nicht mit einer Nummer höher als 709 (möglicherweise ist es nur mein System) Math.log(Math.pow(Math.exp(709),0.33333333333333333333))undMath.log(Math.pow(Math.exp(709),Math.sin(Math.atan2(1,Math.sqrt(8)))))
Shaheer
208
#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);return0;}
@JeremyP scheitert Ihr Kommentar nicht unter der Annahme, dass die Antwort nicht in C geschrieben werden kann? Die Frage ist immerhin mit "C" markiert.
Seth Carnegie
1
@ SethCarnegie Die Antwort ist nicht in C geschrieben ist mein Punkt. Der x86-Assembler ist nicht Teil des Standards.
JeremyP
1
@JeremyP das stimmt, aber die asmDirektive ist. Und ich würde hinzufügen, dass C-Compiler nicht die einzigen sind, die Inline-Assembler haben, Delphi hat das auch.
Seth Carnegie
7
@SethCarnegie Die asmRichtlinie wird nur in der Norm C99 unter Anhang J - Allgemeine Erweiterungen erwähnt.
JeremyP
2
Schlägt in arm-eabi-gcc fehl.
Damian Yerrick
106
Verwenden Sie itoa , um eine Basis-3-Zeichenfolge zu konvertieren. Lass den letzten Trit fallen und konvertiere zurück zu 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 digitreturn strtol(str, NULL,3);// Read back result}
@cshemby Ich wusste eigentlich nicht, dass itoadas eine beliebige Basis verwenden könnte. Wenn Sie eine vollständige funktionierende Implementierung mit durchführen, itoawerde ich abstimmen.
Mysticial
2
Die Implementierung wird enthalten /und %... :-)
R .. GitHub STOP HELPING ICE
2
@R .. Ebenso die Implementierung von printfzur Anzeige Ihres Dezimalergebnisses.
Damian Yerrick
57
(Hinweis: Eine bessere Version finden Sie unter Bearbeiten 2 unten!)
Dies ist nicht so schwierig, wie es sich anhört, weil Sie "ohne Verwendung der Operatoren [..] +[..] " gesagt haben . Siehe unten, wenn Sie die Verwendung des Charakters insgesamt verbieten möchten .+
unsigned div_by(unsignedconst x,unsignedconst by){unsigned floor =0;for(unsigned cmp =0, r =0; cmp <= x;){for(unsigned i =0; i < by; i++)
cmp++;// that's not the + operator!
floor = r;
r++;// neither is this.}return floor;}
dann nur sagen , div_by(100,3)zu dividieren 100durch 3.
Bearbeiten : Sie können den ++Operator auch ersetzen :
unsigned inc(unsigned x){for(unsigned mask =1; mask; mask <<=1){if(mask & x)
x &=~mask;elsereturn x & mask;}return0;// overflow (note that both x and mask are 0 here)}
Edit 2: Etwas schnellere Version ohne jeden Operator, der die enthält +, -, *, /, %Zeichen .
unsigned add(charconst zero[],unsignedconst x,unsignedconst y){// this exploits that &foo[bar] == foo+bar if foo is of type char*return(int)(uintptr_t)(&((&zero[x])[y]));}unsigned div_by(unsignedconst x,unsignedconst 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 addFunktion, da wir den Zeigertyp ohne Verwendung des *Zeichens nicht bezeichnen können , außer in Funktionsparameterlisten, in denen die Syntax type[]identisch ist mit type* const.
FWIW, Sie können eine Multiplikationsfunktion einfach mit einem ähnlichen Trick implementieren, um den 0x55555556von AndreyT vorgeschlagenen Trick zu verwenden :
int mul(intconst x,intconst y){returnsizeof(struct{charconst ignore[y];}[x]);}
Ich bin mir nicht sicher, ob es durchaus möglich ist, einen konformen C-Compiler auf einer solchen Plattform zu implementieren. Möglicherweise müssen wir die Regeln etwas erweitern, z. B. "mindestens 8 Bits" als "in der Lage, mindestens ganze Zahlen von -128 bis +127 zu halten" interpretieren.
Das Problem ist, dass Sie in C keinen Operator "Verschiebung um 1 Stelle nach rechts" haben. Der >>Operator ist der Operator "Division durch 2 ^ n", dh er wird in Bezug auf die Arithmetik und nicht in Bezug auf die Maschinendarstellung angegeben.
R .. GitHub STOP HELPING ICE
Der Setun-Computer ist in keiner Weise binär, daher muss der Befehlssatz definitiv anders sein. Ich bin jedoch überhaupt nicht mit der Bedienung dieses Computers vertraut, daher kann ich nicht bestätigen, ob die Antwort wirklich korrekt ist - aber zumindest sinnvoll - und sehr originell ist. +1
Virolino
32
Wie wäre es mit einer Nachschlagetabelle mit vorberechneten Antworten, da es von Oracle stammt? :-D
publicstaticint div_by_3(long a){
a <<=30;for(int i =2; i <=32; i <<=1){
a = add(a, a >> i);}return(int)(a >>32);}publicstaticlong add(long a,long b){long carry =(a & b)<<1;long sum =(a ^ b);return carry ==0? sum : add(carry, sum);}
Beachten Sie zunächst, 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 bitverschobenen Werte von a addieren! Hoppla! Wir können jedoch nicht hinzufügen, daher müssen wir stattdessen eine Add-Funktion mit bitweisen Operatoren schreiben! Wenn Sie mit bitweisen Operatoren vertraut sind, sollte meine Lösung ziemlich einfach aussehen ... aber falls Sie dies nicht tun, werde ich am Ende ein Beispiel durchgehen.
Eine andere Sache zu beachten ist, dass ich zuerst um 30 nach links verschiebe! Dies soll sicherstellen, dass die Brüche nicht abgerundet werden.
11+61011+0110
sum =1011^0110=1101
carry =(1011&0110)<<1=0010<<1=0100Now you recurse!1101+0100
sum =1101^0100=1001
carry =(1101&0100)<<1=0100<<1=1000Again!1001+1000
sum =1001^1000=0001
carry =(1001&1000)<<1=1000<<1=10000One last time!0001+10000
sum =0001^10000=10001=17
carry =(0001&10000)<<1=0Done!
Es ist einfach eine Ergänzung, die Sie als Kind gelernt haben!
1111011+0110-----10001
Diese Implementierung ist fehlgeschlagen, da nicht alle Begriffe der Gleichung hinzugefügt werden 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, die Auflösung von div_by_3(a)= x ist dann x <= floor(f(a, i)) < a / 3. Wann a = 3kbekommen wir eine falsche Antwort.
funktioniert es für die Eingabe von 3? 1/4, 1/16, ... alle geben 0 für 3 zurück, würden also 0 ergeben, aber 3/3 = 1.
Beil - fertig mit SOverflow
1
Die Logik ist gut, aber die Implementierung ist problematisch. Die Seriennäherung von n/3ist immer kleiner als, n/3was bedeutet, dass für jedes n=3kErgebnis k-1stattdessen wäre k.
Xyand
@ Albert, Dies war der erste Ansatz, den ich versuchte, mit ein paar Variationen, aber alle scheiterten entweder an bestimmten Zahlen, die gleichmäßig durch 3 teilbar oder gleichmäßig durch 2 teilbar waren (abhängig von der Variation). Also habe ich etwas Unkomplizierteres versucht. Ich würde gerne eine Implementierung dieses Ansatzes sehen, die funktioniert, um zu sehen, wo ich es vermasselt habe.
Beil - fertig mit SOverflow
@hatchet, Die Frage ist geschlossen, daher kann ich keine neue Antwort posten, aber die Idee ist, binäres Div zu implementieren. Ich sollte es leicht nachschlagen können.
Dies ist ein gängiger Compilertrick, um langsame Teilungen zu umgehen. Aber Sie müssen wahrscheinlich einige Korrekturen vornehmen, da 0x55555556 / 2 ** 32 nicht genau 1/3 ist.
CodesInChaos
multiply it. Würde das nicht bedeuten, den verbotenen *Operator zu verwenden?
luiscubal
8
@luiscubal: Nein, das wird es nicht. Deshalb sagte ich: "Jetzt müssen wir nur noch die Multiplikation mit Bitoperationen und Verschiebungen implementieren "
AnT
18
Noch eine andere Lösung. Dies sollte alle Ints (einschließlich negativer Ints) mit Ausnahme des Min-Werts eines Int behandeln, der als fest codierte Ausnahme behandelt werden müsste. Dies erfolgt grundsätzlich durch Subtraktion, jedoch nur unter Verwendung von Bitoperatoren (Verschiebungen, xor & und Komplement). Für eine schnellere Geschwindigkeit subtrahiert es 3 * (abnehmende Potenzen von 2). In c # werden ungefähr 444 dieser DivideBy3-Aufrufe pro Millisekunde ausgeführt (2,2 Sekunden für 1.000.000 Teilungen), 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.
publicstaticintDivideBy3(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;}publicstaticintNegate(int a){returnAdd(~a,1);}publicstaticintAdd(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;}
Dies ist c #, weil ich das zur Hand hatte, aber die Unterschiede zu c sollten gering sein.
Sie müssen nur einmal versuchen, Sub zu subtrahieren, denn wenn Sie es zweimal hätten subtrahieren können, hätten Sie es bei der vorherigen Iteration subtrahieren können, als es doppelt so groß war wie jetzt.
Neil
Zählt (a >= sub)als Subtraktion?
Neil
@Neil, ich denke du hast vielleicht recht. Das innere while könnte durch ein einfaches if ersetzt werden, wodurch ein nicht benötigter Vergleich aus der zweiten Iteration der Schleife gespeichert wird. In Bezug auf> = Subtraktion sein ... Ich hoffe nicht, denn das würde es ziemlich schwierig machen! Ich verstehe Ihren Standpunkt, aber ich denke, ich würde mich auf die Seite stützen, die sagt, dass> = nicht als Subtraktion zählt.
Beil - fertig mit SOverflow
@Neil, ich habe diese Änderung vorgenommen, die die Zeit halbiert (auch nicht benötigte Negate gespeichert).
(Ich habe der Kürze halber natürlich einen Teil des Programms weggelassen.) Wenn der Programmierer es satt hat, dies alles abzutippen, 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 Bediener bekannt, der /seine Arbeit immens vereinfachen würde.
@Enes Unal: nicht für kleine Zahlen :) Dieser Algorithmus ist sehr einfach.
GJ.
Jede Primitivität beinhaltet Schwächen :)
Totten
11
Dies ist der klassische Divisionsalgorithmus in Basis 2:
#include<stdio.h>#include<stdint.h>int main(){uint32_t mod3[6]={0,1,2,0,1,2};uint32_t x =1234567;// number to divide, and remainder at the enduint32_t y =0;// resultint bit =31;// current bit
printf("X=%u X/3=%u\n",x,x/3);// the '/3' is for testingwhile(bit>0){
printf("BIT=%d X=%u Y=%u\n",bit,x,y);// decrement bitint h =1;while(1){ bit ^= h;if( bit&h ) h <<=1;elsebreak;}uint32_t r = x>>bit;// current remainder in 0..5
x ^= r<<bit;// remove R bits from Xif(r >=3) y |=1<<bit;// new output bit
x |= mod3[r]<<bit;// new remainder inserted in X}
printf("Y=%u\n",y);}
Schreiben Sie das Programm in Pascal und verwenden Sie den DIVOperator.
Da ist die Frage markiert ckönnen Sie wahrscheinlich eine Funktion in Pascal schreiben und von Ihrem C-Programm aus aufrufen; Die Methode hierfür ist systemspezifisch.
Aber hier ist ein Beispiel, das auf meinem Ubuntu-System mit dem fp-compilerinstallierten Free Pascal- Paket funktioniert . (Ich mache das aus purer 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<stdio.h>#include<stdlib.h>externint 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));return0;}
Bauen:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
++ und - Operatoren unterscheiden sich von + und - Operatoren! In Assembler - Sprache gibt es zwei Befehle ADDund INCdass sie nicht gleiche Opcodes haben.
Amir Saniyan
7
Es wurde nicht überprüft, ob diese Antwort bereits veröffentlicht wurde. Wenn das Programm auf Gleitkommazahlen erweitert werden muss, können die Zahlen mit der erforderlichen Genauigkeit von 10 * multipliziert werden, und dann kann der folgende Code erneut angewendet werden.
#include<stdio.h>int main(){int aNumber =500;int gResult =0;int aLoop =0;int i =0;for(i =0; i < aNumber; i++){if(aLoop ==3){
gResult++;
aLoop =0;}
aLoop++;}
printf("Reulst of %d / 3 = %d", aNumber, gResult);return0;}
Dies sollte für jeden Divisor funktionieren, nicht nur für drei. Derzeit nur für nicht signierte, aber die Erweiterung auf signierte 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)return0;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);}return0;}
privateint dividedBy3(int n){List<Object> a =newObject[n].ToList();List<Object> b =newList<object>();while(a.Count>2){
a.RemoveRange(0,3);
b.Add(newObject());}return b.Count;}
Denn was sie wissen wollen, ist, wenn Sie wissen, wie der Prozessor intern funktioniert ... Wenn Sie einen mathematischen Operator verwenden, wird am Ende eine Operation ausgeführt, die der obigen Antwort sehr ähnlich ist.
RaptorX
Oder sie möchten wissen, ob Sie ein nutzloses Problem erkennen können.
Gregoire
1
@ Gregoire Ich stimme zu, es gibt absolut keine Notwendigkeit, eine solche Implementierung durchzuführen. Im kommerziellen Leben (Orcale) ist es notwendig, die Erfüllung nutzloser Anforderungen zu vermeiden: Die richtige Antwort lautet: "Das macht überhaupt keinen Sinn, warum Geld verlieren dafür? ")
#include<stdio.h>#include<math.h>int main(){int number =8;//Any +ve no.int temp =3, result =0;while(temp <= number){
temp = fma(temp,1,3);//fma(a, b, c) is a library function and returns (a*b) + c.
result = fma(result,1,1);}
printf("\n\n%d divided by 3 = %d\n", number, result);}
Nun, das war nur ein Implementierungsdetail, also konnte ich es als 3.0 / 1.0 anstelle von 0.333333 eingeben, aber ich sollte mich an die Regeln halten. Fest!
wjl
Ich hatte es ursprünglich als 3.0 / 1.0, was in meinem Test tat. Durch die Verwendung einer Zahl mit höherer Genauigkeit sollten sie ein einigermaßen genaues Ergebnis erhalten. gist.github.com/3401496
x/(1-1/y)= x *(1+y)/(1-y^2)= x *(1+y)*(1+y^2)/(1-y^4)=...= x *(1+y)*(1+y^2)*(1+y^4)*...*(1+y^(2^i))/(1-y^(2^(i+i))= x *(1+y)*(1+y^2)*(1+y^4)*...*(1+y^(2^i))
mit y = 1/4:
int div3(int x){
x <<=6;// need more precise
x += x>>2;// x = x * (1+(1/2)^2)
x += x>>4;// x = x * (1+(1/2)^4)
x += x>>8;// x = x * (1+(1/2)^8)
x += x>>16;// x = x * (1+(1/2)^16)return(x+1)>>8;// as (1-(1/2)^32) very near 1,// we plus 1 instead of div (1-(1/2)^32)}
Es wird zwar verwendet +, aber jemand implementiert bereits add by bitwise op.
Antworten:
Dies ist eine einfache Funktion, die die gewünschte Operation ausführt. Da jedoch der
+
Operator erforderlich ist , müssen Sie nur noch die Werte mit Bitoperatoren hinzufügen:Wie Jim kommentierte, funktioniert dies, weil:
n = 4 * a + b
n / 3 = a + (a + b) / 3
So
sum += a
,n = a + b
und iterateWenn
a == 0 (n < 4)
,sum += floor(n / 3);
dh 1,if n == 3, else 0
quelle
1 / 3 = 0.333333
Die sich wiederholenden Zahlen erleichtern die Berechnung mita / 3 = a/10*3 + a/100*3 + a/1000*3 + (..)
. In der Binärdatei ist es fast dasselbe:1 / 3 = 0.0101010101 (base 2)
was dazu führta / 3 = a/4 + a/16 + a/64 + (..)
. Durch Teilen durch 4 kommt die Bitverschiebung. Die letzte Überprüfung von num == 3 ist erforderlich, da wir nur Ganzzahlen haben, mit denen wir arbeiten können.a / 3 = a * 0.111111 (base 4) = a * 4^-1 + a * 4^-2 + a * 4^-3 + (..) = a >> 2 + a >> 4 + a >> 6 + (..)
. Die Basis 4 erklärt auch, warum am Ende nur 3 aufgerundet wird, während 1 und 2 abgerundet werden können.n == 2^k
Folgendes gilt :x % n == x & (n-1)
, wird hiernum & 3
also verwendet, um auszuführen,num % 4
solange dies%
nicht erlaubt ist.Idiotische Bedingungen erfordern eine idiotische Lösung:
Wenn auch der Dezimalteil benötigt wird, deklarieren Sie einfach
result
alsdouble
und fügen Sie das Ergebnis von hinzufmod(number,divisor)
.Erklärung, wie es funktioniert
fwrite
Schreibvorgängenumber
Bytes (Zahl ist 123456 in dem obigen Beispiel).rewind
Setzt den Dateizeiger auf die Vorderseite der Datei zurück.fread
liest maximalnumber
"Datensätze"divisor
mit einer Länge aus der Datei und gibt die Anzahl der gelesenen Elemente zurück.Wenn Sie 30 Bytes schreiben und dann die Datei in Einheiten von 3 zurücklesen, erhalten Sie 10 "Einheiten". 30/3 = 10
quelle
quelle
Math.log(Math.pow(Math.exp(709),0.33333333333333333333))
undMath.log(Math.pow(Math.exp(709),Math.sin(Math.atan2(1,Math.sqrt(8)))))
quelle
Sie können (plattformabhängige) Inline-Assembly verwenden, z. B. für x86: (funktioniert auch für negative Zahlen)
quelle
asm
Direktive ist. Und ich würde hinzufügen, dass C-Compiler nicht die einzigen sind, die Inline-Assembler haben, Delphi hat das auch.asm
Richtlinie wird nur in der Norm C99 unter Anhang J - Allgemeine Erweiterungen erwähnt.Verwenden Sie itoa , um eine Basis-3-Zeichenfolge zu konvertieren. Lass den letzten Trit fallen und konvertiere zurück zu Basis 10.
quelle
itoa
das eine beliebige Basis verwenden könnte. Wenn Sie eine vollständige funktionierende Implementierung mit durchführen,itoa
werde ich abstimmen./
und%
... :-)printf
zur Anzeige Ihres Dezimalergebnisses.(Hinweis: Eine bessere Version finden Sie unter Bearbeiten 2 unten!)
Dies ist nicht so schwierig, wie es sich anhört, weil Sie "ohne Verwendung der Operatoren [..]
+
[..] " gesagt haben . Siehe unten, wenn Sie die Verwendung des Charakters insgesamt verbieten möchten .+
dann nur sagen ,
div_by(100,3)
zu dividieren100
durch3
.Bearbeiten : Sie können den
++
Operator auch ersetzen :Edit 2: Etwas schnellere Version ohne jeden Operator, der die enthält
+
,-
,*
,/
,%
Zeichen .Wir verwenden das erste Argument der
add
Funktion, da wir den Zeigertyp ohne Verwendung des*
Zeichens nicht bezeichnen können , außer in Funktionsparameterlisten, in denen die Syntaxtype[]
identisch ist mittype* const
.FWIW, Sie können eine Multiplikationsfunktion einfach mit einem ähnlichen Trick implementieren, um den
0x55555556
von AndreyT vorgeschlagenen Trick zu verwenden :quelle
++
: Warum verwenden Sie nicht einfach/=
?++
ist auch eine Abkürzung: Fürnum = num + 1
.+=
ist endlich eine Abkürzung fürnum = num + 1
.Auf dem Setun-Computer ist dies problemlos möglich .
Um eine ganze Zahl durch 3 zu teilen, verschieben Sie sie um 1 Stelle nach rechts .
Ich bin mir nicht sicher, ob es durchaus möglich ist, einen konformen C-Compiler auf einer solchen Plattform zu implementieren. Möglicherweise müssen wir die Regeln etwas erweitern, z. B. "mindestens 8 Bits" als "in der Lage, mindestens ganze Zahlen von -128 bis +127 zu halten" interpretieren.
quelle
>>
Operator ist der Operator "Division durch 2 ^ n", dh er wird in Bezug auf die Arithmetik und nicht in Bezug auf die Maschinendarstellung angegeben.Wie wäre es mit einer Nachschlagetabelle mit vorberechneten Antworten, da es von Oracle stammt? :-D
quelle
Hier ist meine Lösung:
Beachten Sie zunächst, dass
Jetzt ist der Rest einfach!
Jetzt müssen wir nur noch diese bitverschobenen Werte von a addieren! Hoppla! Wir können jedoch nicht hinzufügen, daher müssen wir stattdessen eine Add-Funktion mit bitweisen Operatoren schreiben! Wenn Sie mit bitweisen Operatoren vertraut sind, sollte meine Lösung ziemlich einfach aussehen ... aber falls Sie dies nicht tun, werde ich am Ende ein Beispiel durchgehen.
Eine andere Sache zu beachten ist, dass ich zuerst um 30 nach links verschiebe! Dies soll sicherstellen, dass die Brüche nicht abgerundet werden.
Es ist einfach eine Ergänzung, die Sie als Kind gelernt haben!
Diese Implementierung ist fehlgeschlagen, da nicht alle Begriffe der Gleichung hinzugefügt werden können:
Angenommen, die Auflösung von
div_by_3(a)
= x ist dannx <= floor(f(a, i)) < a / 3
. Wanna = 3k
bekommen wir eine falsche Antwort.quelle
n/3
ist immer kleiner als,n/3
was bedeutet, dass für jedesn=3k
Ergebnisk-1
stattdessen wärek
.Um eine 32-Bit-Zahl durch 3 zu teilen, kann man sie mit multiplizieren
0x55555556
und dann die oberen 32 Bits des 64-Bit-Ergebnisses nehmen.Jetzt müssen Sie nur noch die Multiplikation mit Bitoperationen und Verschiebungen implementieren ...
quelle
multiply it
. Würde das nicht bedeuten, den verbotenen*
Operator zu verwenden?Noch eine andere Lösung. Dies sollte alle Ints (einschließlich negativer Ints) mit Ausnahme des Min-Werts eines Int behandeln, der als fest codierte Ausnahme behandelt werden müsste. Dies erfolgt grundsätzlich durch Subtraktion, jedoch nur unter Verwendung von Bitoperatoren (Verschiebungen, xor & und Komplement). Für eine schnellere Geschwindigkeit subtrahiert es 3 * (abnehmende Potenzen von 2). In c # werden ungefähr 444 dieser DivideBy3-Aufrufe pro Millisekunde ausgeführt (2,2 Sekunden für 1.000.000 Teilungen), 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.
Dies ist c #, weil ich das zur Hand hatte, aber die Unterschiede zu c sollten gering sein.
quelle
(a >= sub)
als Subtraktion?Es ist wirklich ganz einfach.
(Ich habe der Kürze halber natürlich einen Teil des Programms weggelassen.) Wenn der Programmierer es satt hat, dies alles abzutippen, 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 Bediener bekannt, der
/
seine Arbeit immens vereinfachen würde.quelle
Dictionary<number, number>
anstelle von wiederholtenif
Anweisungen eine verwenden, umO(1)
zeitliche Komplexität zu erzielen!Die Verwendung von Zählern ist eine grundlegende Lösung:
Es ist auch einfach, eine Modulfunktion auszuführen, überprüfen Sie die Kommentare.
quelle
Dies ist der klassische Divisionsalgorithmus in Basis 2:
quelle
Schreiben Sie das Programm in Pascal und verwenden Sie den
DIV
Operator.Da ist die Frage markiert ckönnen Sie wahrscheinlich eine Funktion in Pascal schreiben und von Ihrem C-Programm aus aufrufen; Die Methode hierfür ist systemspezifisch.
Aber hier ist ein Beispiel, das auf meinem Ubuntu-System mit dem
fp-compiler
installierten Free Pascal- Paket funktioniert . (Ich mache das aus purer Sturheit; ich behaupte nicht, dass dies nützlich ist.)divide_by_3.pas
::main.c
::Bauen:
Beispielausführung:
quelle
quelle
ADD
undINC
dass sie nicht gleiche Opcodes haben.Es wurde nicht überprüft, ob diese Antwort bereits veröffentlicht wurde. Wenn das Programm auf Gleitkommazahlen erweitert werden muss, können die Zahlen mit der erforderlichen Genauigkeit von 10 * multipliziert werden, und dann kann der folgende Code erneut angewendet werden.
quelle
Dies sollte für jeden Divisor funktionieren, nicht nur für drei. Derzeit nur für nicht signierte, aber die Erweiterung auf signierte sollte nicht so schwierig sein.
quelle
Wäre es ein Betrug, den
/
Operator "hinter den Kulissen" mithilfe voneval
String-Verkettung zu verwenden?In Javacript können Sie dies beispielsweise tun
quelle
Verwenden von BC Math in PHP :
MySQL (es ist ein Interview von Oracle)
Pascal :
x86-64 Assemblersprache:
quelle
Zuerst habe ich mir etwas ausgedacht.
EDIT: Sorry, ich habe das Tag nicht bemerkt
C
. Aber Sie können die Idee der String-Formatierung verwenden, denke ich ...quelle
Das folgende Skript generiert ein C-Programm, das das Problem ohne Verwendung der Operatoren löst
* / + - %
:quelle
Verwenden des Hacker Delight Magic Zahlenrechners
Wobei fma eine im
math.h
Header definierte Standardbibliotheksfunktion ist .quelle
-
weder den noch den*
Operator?Wie wäre es mit diesem Ansatz (c #)?
quelle
Ich denke die richtige Antwort ist:
Warum sollte ich keinen Basisoperator verwenden, um eine Basisoperation auszuführen?
quelle
Die Lösung mit der Bibliotheksfunktion fma () funktioniert für jede positive Zahl:
Siehe meine andere Antwort .
quelle
Verwenden Sie cblas , die Teil des Accelerate-Frameworks von OS X sind.
quelle
Im Allgemeinen wäre eine Lösung hierfür:
log(pow(exp(numerator),pow(denominator,-1)))
quelle
Zuerst:
Dann finde heraus, wie man x / (1 - y) löst:
mit y = 1/4:
Es wird zwar verwendet
+
, aber jemand implementiert bereits add by bitwise op.quelle