@AlexandreC. - te techniki wykorzystują jednak dodawanie (+).
topór - wykonane SOverflow
19
To była wyrocznia, więc z jakich części wyroczni wolno ci korzystać?
Hogan
8
Zidentyfikowany duplikat nie jest duplikatem. Zauważ, że kilka odpowiedzi tutaj nie używa przesunięcia ani dodawania bitów, ponieważ to pytanie nie ograniczyło rozwiązania do tych operacji.
Jest to prosta funkcja, która wykonuje żądaną operację. Wymaga to jednak +operatora, więc wystarczy, że dodasz wartości za pomocą operatorów bitowych:
// 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;}
Jak skomentował Jim, działa to, ponieważ:
n = 4 * a + b
n / 3 = a + (a + b) / 3
Tak sum += a, n = a + bi iterate
Kiedy a == 0 (n < 4), sum += floor(n / 3);tj. 1,if n == 3, else 0
Jest to prawdopodobnie odpowiedź, której szuka Oracle. Pokazuje, że wiesz, jak operatory +, -, * i / są w rzeczywistości zaimplementowane w CPU: proste operacje bitowe.
craig65535
21
Działa to, ponieważ n = 4a + b, n / 3 = a + (a + b) / 3, więc sumuj + = a, n = a + b i iteruj. Gdy a == 0 (n <4), suma + = podłoga (n / 3); tj. 1, jeśli n == 3, w przeciwnym razie 0.
Jim Balter
7
Oto znaleziona sztuczka, która dała mi podobne rozwiązanie. W systemie dziesiętnym: 1 / 3 = 0.333333powtarzające się liczby ułatwiają obliczanie za pomocą a / 3 = a/10*3 + a/100*3 + a/1000*3 + (..). W systemie binarnym jest prawie tak samo 1 / 3 = 0.0101010101 (base 2):, co prowadzi do a / 3 = a/4 + a/16 + a/64 + (..). Dzielenie przez 4 jest źródłem przesunięcia bitów. Ostatnia kontrola na num == 3 jest potrzebna, ponieważ mamy tylko liczby całkowite do pracy.
Yorick Sijsling
4
W bazie 4 robi się jeszcze lepiej: a / 3 = a * 0.111111 (base 4) = a * 4^-1 + a * 4^-2 + a * 4^-3 + (..) = a >> 2 + a >> 4 + a >> 6 + (..). Baza 4 wyjaśnia również, dlaczego tylko 3 jest zaokrąglana w górę na końcu, podczas gdy 1 i 2 można zaokrąglać w dół.
Yorick Sijsling
2
@ while1: bitowa operacja AND. Dobrze znany jest również fakt, że w tym przypadku n == 2^kjest prawda: x % n == x & (n-1)więc tutaj num & 3jest używany do wykonywania, num % 4podczas gdy %nie jest dozwolone.
aplavin
436
Warunki idiotyczne wymagają idiotycznego rozwiązania:
@ PearlNameless: nie wiesz, czego używają w środku, znajdują się w czarnej skrzynce „zdefiniowanej implementacji”. Nic nie powstrzymuje ich przed użyciem operatorów bitowych; w każdym razie są poza domeną mojego kodu, więc to nie mój problem. :)
Matteo Italia
8
@IvoFlipse od I mogę wyczyścić, dostajesz duże coś i wpychasz je w coś trzy razy za małe, a następnie sprawdzasz, jak bardzo się zmieści. To około jedna trzecia.
Pureferret
27
poprosił najlepszego programistę C (i najbardziej niezręcznego społecznie) w naszej firmie o wyjaśnienie kodu. kiedy to zrobił, powiedziałem, że to całkiem genialne. Powiedział „ten dreck nie jest rozwiązaniem” i poprosił mnie, abym opuścił biurko
cvursache
6
@cvursache Myślę, że chodzi o to, że pytanie jest tak martwe w mózgu, że dozwolona jest martwa odpowiedź mózgu. „Najlepszy programista C” w twojej firmie „równie łatwo mógłby powiedzieć„ że dreck nie jest (właściwym) pytaniem ”.
JeremyP
17
@JeremyP: dokładnie. Chodzi mi o to, że jeśli w prawdziwym życiu otrzymałbym kompilator bez obsługi arytmetyki, jedynym rozsądnym rozwiązaniem byłoby poproszenie o lepszy kompilator , ponieważ praca w takich warunkach nie ma sensu. Gdyby osoba przeprowadzająca wywiad chciała sprawdzić moją wiedzę o tym, jak wprowadzić podział za pomocą operacji bitowych, mógłby po prostu być prosty i zadać to pytanie teoretyczne; tego rodzaju „sztuczki” po prostu krzyczą na takie odpowiedzi.
@bitmask, funkcje matematyczne są zwykle implementowane bezpośrednio w asm.
SingerOfTheFall,
7
właśnie wpisałem go w mojej konsoli js, nie działa z liczbą wyższą niż 709 (może to być tylko mój system) Math.log(Math.pow(Math.exp(709),0.33333333333333333333))iMath.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, czy Twój komentarz nie zawiedzie przy założeniu, że odpowiedzi nie można napisać w języku C? W końcu pytanie ma oznaczenie „C”.
Seth Carnegie
1
@SethCarnegie Odpowiedź nie jest napisana w C, o to mi chodzi. Asembler x86 nie jest częścią standardu.
JeremyP,
1
@JeremyP to prawda, ale asmdyrektywa jest. I dodałbym, że kompilatory C nie są jedynymi, które mają wbudowane asemblery, Delphi też to ma.
Seth Carnegie,
7
@SethCarnegie asmDyrektywa jest wymieniona tylko w standardzie C99 w Załączniku J - wspólne rozszerzenia.
JeremyP,
2
Nie działa w arm-eabi-gcc.
Damian Yerrick
106
Użyj itoa, aby przekonwertować na podstawowy ciąg 3. Upuść ostatni trit i przekonwertuj z powrotem na bazę 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 Właściwie to nie wiedziałem, że itoamożna użyć dowolnej bazy. Jeśli wykonasz pełną działającą implementację za pomocą itoa, będę głosować.
Mysticial
2
Realizacja będzie zawierać /i %... :-)
R .. GitHub ZATRZYMAJ POMOC ICE
2
@R .. Podobnie jak implementacja printfwyświetlania wyniku dziesiętnego.
Damian Yerrick
57
(uwaga: patrz Edycja 2 poniżej, aby uzyskać lepszą wersję!)
Nie jest to tak trudne, jak się wydaje, ponieważ powiedziałeś „bez użycia operatorów [..] +[..] ”. Zobacz poniżej, jeśli chcesz zabronić używania tej postaci razem.+
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;}
a potem po prostu powiedzieć, div_by(100,3)podzielić 100przez 3.
Edycja : Możesz także kontynuować i zastąpić ++operatora:
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: Nieco szybsza wersja bez użycia jakiegokolwiek operatora, który zawiera +, -, *, /, %znaki .
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;}
Używamy pierwszego argumentu addfunkcji, ponieważ nie możemy wskazać typu wskaźników bez użycia *znaku, z wyjątkiem list parametrów funkcji, w których składnia type[]jest identyczna type* const.
FWIW, możesz łatwo wdrożyć funkcję mnożenia za pomocą podobnej sztuczki, aby użyć 0x55555556sztuczki zaproponowanej przez AndreyT :
int mul(intconst x,intconst y){returnsizeof(struct{charconst ignore[y];}[x]);}
Nie jestem jednak pewien, czy jest możliwe zaimplementowanie zgodnego kompilatora C na takiej platformie. Być może będziemy musieli nieco rozciągnąć reguły, na przykład interpretować „co najmniej 8 bitów” jako „zdolne do utrzymania co najmniej liczb całkowitych od -128 do +127”.
Problem polega na tym, że w C. nie >>ma operatora „przesunięcie o 1 miejsce”. Operator jest operatorem „dzielenia przez 2 ^ n”, tzn. Jest określony w kategoriach arytmetycznych, a nie reprezentacji maszyny.
R .. GitHub ZATRZYMAJ LÓD
Komputer Setun nie jest binarny w żadnym znaczeniu tego słowa, więc zestaw instrukcji musi być zdecydowanie inny. Jednak w ogóle nie znam działania tego komputera, więc nie mogę potwierdzić, czy odpowiedź jest naprawdę poprawna - ale przynajmniej ma sens - i jest bardzo oryginalna. +1
virolino,
32
Skoro pochodzi od Oracle, to co powiesz na tabelę wyszukiwania wstępnie obliczonych odpowiedzi. :-RE
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);}
Po pierwsze, zwróć uwagę na to
1/3=1/4+1/16+1/64+...
Teraz reszta jest prosta!
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+...
Teraz wszystko, co musimy zrobić, to zsumować te nieco przesunięte wartości a! Ups! Nie możemy jednak dodawać, więc zamiast tego będziemy musieli napisać funkcję dodawania za pomocą bitowych operatorów! Jeśli znasz się na nieco bitowych operatorach, moje rozwiązanie powinno wyglądać dość prosto ... ale na wszelki wypadek, przejdę przez przykład na końcu.
Kolejną rzeczą do odnotowania jest to, że najpierw przesuwam w lewo o 30! Ma to na celu upewnienie się, że ułamki nie zostaną zaokrąglone.
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!
To po prostu dodatek, którego nauczyłeś się jako dziecko!
1111011+0110-----10001
Ta implementacja nie powiodła się, ponieważ nie możemy dodać wszystkich warunków równania:
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
Załóżmy zatem, że reslut div_by_3(a)= x x <= floor(f(a, i)) < a / 3. Kiedy a = 3kotrzymujemy błędną odpowiedź.
czy to działa dla wejścia 3? 1/4, 1/16, ... wszystkie zwracają 0 dla 3, więc sumują się do 0, ale 3/3 = 1.
topór - zrobione SOverflow
1
Logika jest dobra, ale wdrożenie jest problematyczne. Przybliżenie szeregu n/3jest zawsze mniejsze niż, n/3co oznacza, że dla każdego n=3kwyniku byłby k-1zamiast k.
Xyand
@Albert, To było pierwsze podejście, które wypróbowałem, z kilkoma odmianami, ale wszystkie zawiodły w przypadku niektórych liczb podzielnych równomiernie przez 3 lub równomiernie podzielnych przez 2 (w zależności od odmiany). Więc spróbowałem czegoś prostszego. Chciałbym zobaczyć wdrożenie tego podejścia, które działa, aby zobaczyć, gdzie popieprzyłem.
topór - wykonane przy pomocy SOverflow
@hatchet, Pytanie jest zamknięte, więc nie mogę opublikować nowej odpowiedzi, ale pomysł polega na wdrożeniu binarnego div. Powinienem łatwo to sprawdzić.
Jest to powszechna sztuczka kompilatora do obejścia powolnych podziałów. Ale prawdopodobnie musisz zrobić kilka poprawek, ponieważ 0x55555556 / 2 ** 32 nie jest dokładnie 1/3.
CodesInChaos
multiply it. Czy nie oznaczałoby to użycia zabronionego *operatora?
luiscubal
8
@luiscubal: Nie, nie będzie. Właśnie dlatego powiedziałem: „Pozostało już tylko wykonać mnożenie za pomocą operacji bitowych i przesunięć ”
AnT
18
Jeszcze inne rozwiązanie. Powinno to obsługiwać wszystkie liczby całkowite (w tym liczby całkowite ujemne) oprócz wartości minimalnej liczby całkowitej, która musiałaby być traktowana jako wyjątek zakodowany na stałe. Zasadniczo robi to dzielenie przez odejmowanie, ale tylko przy użyciu operatorów bitowych (shift, xor i & i dopełnianie). Dla większej prędkości odejmuje 3 * (malejące moce 2). W c # wykonuje około 444 z tych wywołań DivideBy3 na milisekundę (2,2 sekundy na 1 000 000 podziałów), więc nie jest strasznie powolny, ale nie jest tak szybki jak zwykłe x / 3. Dla porównania, dobre rozwiązanie Coodeya jest około 5 razy szybsze niż to.
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;}
To jest c #, ponieważ miałem to pod ręką, ale różnice w stosunku do c powinny być niewielkie.
Musisz tylko odjąć odejmowanie jeden raz, ponieważ gdybyś mógł odjąć go dwa razy, mógłbyś odjąć go od poprzedniej iteracji, gdy była dwa razy większa niż obecnie.
Neil
Czy (a >= sub)liczy się jako odejmowanie?
Neil
@Neil, myślę, że masz rację. Wewnętrzna chwila mogłaby zostać zastąpiona prostą, jeśli, oszczędzając niepotrzebnego porównania z drugiej iteracji pętli. Odnośnie> = odejmowania ... Mam nadzieję, że nie, bo to uczyniłoby to dość trudnym! Rozumiem twój punkt widzenia, ale myślę, że oparłbym się na stronie, która mówi> = nie liczy się jako odejmowanie.
topór - wykonane SOverflow
@Neil, dokonałem tej zmiany, co skróciło czas o połowę (uratowałem również niepotrzebne Negaty).
(Oczywiście pominąłem część programu ze względu na zwięzłość). Jeśli programista zmęczy się pisaniem tego wszystkiego, jestem pewien, że mógłby napisać osobny program, aby go wygenerować. Zdarza mi się wiedzieć o pewnym operatorze /, co znacznie uprościłoby jego pracę.
@Enes Unal: nie dla małych liczb :) Ten algorytm jest bardzo prosty.
GJ.
Każda prymitywność obejmuje słabości :)
zabrała
11
Ten jest klasycznym algorytmem podziału w bazie 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);}
Ponieważ pytanie jest oznaczone do, prawdopodobnie możesz napisać funkcję w Pascal i wywołać ją ze swojego programu w C; metoda ta jest specyficzna dla systemu.
Ale oto przykład, który działa na moim systemie Ubuntu z Free Pascal fp-compiler zainstalowanym pakietem . (Robię to z czysto upartego uporu; nie twierdzę, że jest to przydatne).
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;}
Budować:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
++ i - operatorzy różnią się od + i - operatorzy! W języku asemblera są dwie instrukcje ADDi INCże nie mają tych samych kodów operacyjnych.
Amir Saniyan,
7
Nie sprawdziłem krzyżowo, czy ta odpowiedź jest już opublikowana. Jeśli program musi zostać rozszerzony na liczby zmiennoprzecinkowe, liczby można pomnożyć przez 10 * potrzebną liczbę dokładności, a następnie ponownie zastosować następujący kod.
#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;}
To powinno działać dla każdego dzielnika, nie tylko trzech. Obecnie tylko dla niepodpisanych, ale rozszerzenie go na podpisane nie powinno być takie trudne.
#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;}
Ponieważ chcą wiedzieć, jeśli wiesz, jak procesor działa wewnętrznie ... użycie operatora matematycznego w końcu wykona operację bardzo podobną do powyższej odpowiedzi.
RaptorX,
Albo chcą wiedzieć, czy potrafisz rozpoznać bezużyteczny problem.
Gregoire,
1
@Gregoire Zgadzam się, że nie ma aboloultley takiej potrzeby, Bit w życiu komercyjnym (Orcale) konieczne jest unikanie spełniania niepotrzebnych wymagań: Prawidłowa odpowiedź to: „To nie ma żadnego sensu, po co tracić pieniądze za to? ”)
#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);}
To był tylko szczegół implementacji, więc mogłem wpisać go jako 3.0 / 1.0 zamiast 0.333333, ale powinienem grać zgodnie z zasadami. Naprawiony!
wjl
Pierwotnie miałem go jako 3.0 / 1.0, co zrobiłem w moim teście. Używając liczby o wyższej precyzji, powinni uzyskać dość dokładny wynik. 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))
zy = 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)}
Chociaż używa +, ale ktoś już implementuje dodawanie bitowe op.
Odpowiedzi:
Jest to prosta funkcja, która wykonuje żądaną operację. Wymaga to jednak
+
operatora, więc wystarczy, że dodasz wartości za pomocą operatorów bitowych:Jak skomentował Jim, działa to, ponieważ:
n = 4 * a + b
n / 3 = a + (a + b) / 3
Tak
sum += a
,n = a + b
i iterateKiedy
a == 0 (n < 4)
,sum += floor(n / 3);
tj. 1,if n == 3, else 0
źródło
1 / 3 = 0.333333
powtarzające się liczby ułatwiają obliczanie za pomocąa / 3 = a/10*3 + a/100*3 + a/1000*3 + (..)
. W systemie binarnym jest prawie tak samo1 / 3 = 0.0101010101 (base 2)
:, co prowadzi doa / 3 = a/4 + a/16 + a/64 + (..)
. Dzielenie przez 4 jest źródłem przesunięcia bitów. Ostatnia kontrola na num == 3 jest potrzebna, ponieważ mamy tylko liczby całkowite do pracy.a / 3 = a * 0.111111 (base 4) = a * 4^-1 + a * 4^-2 + a * 4^-3 + (..) = a >> 2 + a >> 4 + a >> 6 + (..)
. Baza 4 wyjaśnia również, dlaczego tylko 3 jest zaokrąglana w górę na końcu, podczas gdy 1 i 2 można zaokrąglać w dół.n == 2^k
jest prawda:x % n == x & (n-1)
więc tutajnum & 3
jest używany do wykonywania,num % 4
podczas gdy%
nie jest dozwolone.Warunki idiotyczne wymagają idiotycznego rozwiązania:
Jeśli potrzebna jest również część dziesiętna, po prostu zadeklaruj
result
jakodouble
i dodaj do niej wynikfmod(number,divisor)
.Wyjaśnienie, jak to działa
fwrite
piszenumber
bajtów (liczba wynosi 123456 w powyższym przykładzie).rewind
resetuje wskaźnik pliku na początek pliku.fread
odczytuje maksymalnienumber
„rekordy”divisor
długości z pliku i zwraca liczbę odczytanych elementów.Jeśli napiszesz 30 bajtów, a następnie ponownie odczytasz plik w jednostkach 3, otrzymasz 10 „jednostek”. 30/3 = 10
źródło
źródło
Math.log(Math.pow(Math.exp(709),0.33333333333333333333))
iMath.log(Math.pow(Math.exp(709),Math.sin(Math.atan2(1,Math.sqrt(8)))))
źródło
Możesz użyć (zależnego od platformy) zestawu wbudowanego, np. Dla x86: (działa również dla liczb ujemnych)
źródło
asm
dyrektywa jest. I dodałbym, że kompilatory C nie są jedynymi, które mają wbudowane asemblery, Delphi też to ma.asm
Dyrektywa jest wymieniona tylko w standardzie C99 w Załączniku J - wspólne rozszerzenia.Użyj itoa, aby przekonwertować na podstawowy ciąg 3. Upuść ostatni trit i przekonwertuj z powrotem na bazę 10.
źródło
itoa
można użyć dowolnej bazy. Jeśli wykonasz pełną działającą implementację za pomocąitoa
, będę głosować./
i%
... :-)printf
wyświetlania wyniku dziesiętnego.(uwaga: patrz Edycja 2 poniżej, aby uzyskać lepszą wersję!)
Nie jest to tak trudne, jak się wydaje, ponieważ powiedziałeś „bez użycia operatorów [..]
+
[..] ”. Zobacz poniżej, jeśli chcesz zabronić używania tej postaci razem.+
a potem po prostu powiedzieć,
div_by(100,3)
podzielić100
przez3
.Edycja : Możesz także kontynuować i zastąpić
++
operatora:Edit 2: Nieco szybsza wersja bez użycia jakiegokolwiek operatora, który zawiera
+
,-
,*
,/
,%
znaki .Używamy pierwszego argumentu
add
funkcji, ponieważ nie możemy wskazać typu wskaźników bez użycia*
znaku, z wyjątkiem list parametrów funkcji, w których składniatype[]
jest identycznatype* const
.FWIW, możesz łatwo wdrożyć funkcję mnożenia za pomocą podobnej sztuczki, aby użyć
0x55555556
sztuczki zaproponowanej przez AndreyT :źródło
++
: Dlaczego nie używasz po prostu/=
?++
to także skrót: Fornum = num + 1
.+=
końcu jest skrótem donum = num + 1
.Jest to łatwo możliwe na komputerze Setun .
Aby podzielić liczbę całkowitą przez 3, przesuń w prawo o 1 miejsce .
Nie jestem jednak pewien, czy jest możliwe zaimplementowanie zgodnego kompilatora C na takiej platformie. Być może będziemy musieli nieco rozciągnąć reguły, na przykład interpretować „co najmniej 8 bitów” jako „zdolne do utrzymania co najmniej liczb całkowitych od -128 do +127”.
źródło
>>
ma operatora „przesunięcie o 1 miejsce”. Operator jest operatorem „dzielenia przez 2 ^ n”, tzn. Jest określony w kategoriach arytmetycznych, a nie reprezentacji maszyny.Skoro pochodzi od Oracle, to co powiesz na tabelę wyszukiwania wstępnie obliczonych odpowiedzi. :-RE
źródło
Oto moje rozwiązanie:
Po pierwsze, zwróć uwagę na to
Teraz reszta jest prosta!
Teraz wszystko, co musimy zrobić, to zsumować te nieco przesunięte wartości a! Ups! Nie możemy jednak dodawać, więc zamiast tego będziemy musieli napisać funkcję dodawania za pomocą bitowych operatorów! Jeśli znasz się na nieco bitowych operatorach, moje rozwiązanie powinno wyglądać dość prosto ... ale na wszelki wypadek, przejdę przez przykład na końcu.
Kolejną rzeczą do odnotowania jest to, że najpierw przesuwam w lewo o 30! Ma to na celu upewnienie się, że ułamki nie zostaną zaokrąglone.
To po prostu dodatek, którego nauczyłeś się jako dziecko!
Ta implementacja nie powiodła się, ponieważ nie możemy dodać wszystkich warunków równania:
Załóżmy zatem, że reslut
div_by_3(a)
= xx <= floor(f(a, i)) < a / 3
. Kiedya = 3k
otrzymujemy błędną odpowiedź.źródło
n/3
jest zawsze mniejsze niż,n/3
co oznacza, że dla każdegon=3k
wyniku byłbyk-1
zamiastk
.Aby podzielić liczbę 32-bitową przez 3, można ją pomnożyć,
0x55555556
a następnie pobrać 32 górne bity wyniku 64-bitowego.Teraz pozostaje tylko zaimplementować mnożenie za pomocą operacji bitowych i przesunięć ...
źródło
multiply it
. Czy nie oznaczałoby to użycia zabronionego*
operatora?Jeszcze inne rozwiązanie. Powinno to obsługiwać wszystkie liczby całkowite (w tym liczby całkowite ujemne) oprócz wartości minimalnej liczby całkowitej, która musiałaby być traktowana jako wyjątek zakodowany na stałe. Zasadniczo robi to dzielenie przez odejmowanie, ale tylko przy użyciu operatorów bitowych (shift, xor i & i dopełnianie). Dla większej prędkości odejmuje 3 * (malejące moce 2). W c # wykonuje około 444 z tych wywołań DivideBy3 na milisekundę (2,2 sekundy na 1 000 000 podziałów), więc nie jest strasznie powolny, ale nie jest tak szybki jak zwykłe x / 3. Dla porównania, dobre rozwiązanie Coodeya jest około 5 razy szybsze niż to.
To jest c #, ponieważ miałem to pod ręką, ale różnice w stosunku do c powinny być niewielkie.
źródło
(a >= sub)
liczy się jako odejmowanie?To naprawdę bardzo proste.
(Oczywiście pominąłem część programu ze względu na zwięzłość). Jeśli programista zmęczy się pisaniem tego wszystkiego, jestem pewien, że mógłby napisać osobny program, aby go wygenerować. Zdarza mi się wiedzieć o pewnym operatorze
/
, co znacznie uprościłoby jego pracę.źródło
Dictionary<number, number>
zamiast powtarzanychif
instrukcji, aby miećO(1)
złożoność czasu!Korzystanie z liczników to podstawowe rozwiązanie:
Łatwo jest również wykonać funkcję modułu, sprawdź komentarze.
źródło
Ten jest klasycznym algorytmem podziału w bazie 2:
źródło
Napisz program w Pascal i użyj
DIV
operatora.Ponieważ pytanie jest oznaczone do, prawdopodobnie możesz napisać funkcję w Pascal i wywołać ją ze swojego programu w C; metoda ta jest specyficzna dla systemu.
Ale oto przykład, który działa na moim systemie Ubuntu z Free Pascal
fp-compiler
zainstalowanym pakietem . (Robię to z czysto upartego uporu; nie twierdzę, że jest to przydatne).divide_by_3.pas
:main.c
:Budować:
Przykładowe wykonanie:
źródło
źródło
ADD
iINC
że nie mają tych samych kodów operacyjnych.Nie sprawdziłem krzyżowo, czy ta odpowiedź jest już opublikowana. Jeśli program musi zostać rozszerzony na liczby zmiennoprzecinkowe, liczby można pomnożyć przez 10 * potrzebną liczbę dokładności, a następnie ponownie zastosować następujący kod.
źródło
To powinno działać dla każdego dzielnika, nie tylko trzech. Obecnie tylko dla niepodpisanych, ale rozszerzenie go na podpisane nie powinno być takie trudne.
źródło
Czy oszustwo byłoby używać
/
operatora „za kulisami” za pomocąeval
i łączenia łańcuchów?Na przykład w Javacript możesz to zrobić
źródło
Korzystanie z BC Math w PHP :
MySQL (to wywiad z Oracle)
Pascal :
język asemblera x86-64:
źródło
Najpierw wymyśliłem.
EDYCJA: Przepraszam, nie zauważyłem tagu
C
. Ale możesz użyć pomysłu na formatowanie ciągów, tak myślę ...źródło
Poniższy skrypt generuje program C, który rozwiązuje problem bez użycia operatorów
* / + - %
:źródło
Korzystanie z kalkulatora liczb Hacker's Delight Magic
Gdzie fma jest standardową funkcją biblioteki zdefiniowaną w
math.h
nagłówku.źródło
-
ani*
?Co powiesz na to podejście (c #)?
źródło
Myślę, że poprawna odpowiedź to:
Dlaczego nie miałbym używać operatora podstawowego do wykonania podstawowej operacji?
źródło
Rozwiązanie wykorzystujące funkcję biblioteki fma () , działa dla dowolnej liczby dodatniej:
Zobacz moją kolejną odpowiedź .
źródło
Użyj cblas , zawartych w ramach Accelerate systemu OS X.
źródło
Ogólnie rozwiązaniem tego byłoby:
log(pow(exp(numerator),pow(denominator,-1)))
źródło
Pierwszy:
Następnie wymyśl, jak rozwiązać x / (1 - y):
zy = 1/4:
Chociaż używa
+
, ale ktoś już implementuje dodawanie bitowe op.źródło