@AlexandreC. - Teknik-teknik tersebut menggunakan penjumlahan (+).
kapak - dilakukan dengan SOverflow
19
Ini oracle jadi bagian oracle apa yang diizinkan untuk Anda gunakan?
Hogan
8
Duplikat yang diidentifikasi bukan duplikat. Perhatikan bahwa beberapa jawaban di sini tidak menggunakan sedikit pun pergeseran atau penambahan karena pertanyaan ini tidak membatasi solusi untuk operasi tersebut.
Ini adalah fungsi sederhana yang melakukan operasi yang diinginkan. Tapi itu membutuhkan +operator, jadi yang harus Anda lakukan adalah menambahkan nilai dengan operator bit:
// 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;}
Seperti yang dikomentari Jim, ini bekerja, karena:
n = 4 * a + b
n / 3 = a + (a + b) / 3
Jadi sum += a, n = a + b, dan iterate
Kapan a == 0 (n < 4), sum += floor(n / 3);yaitu 1,if n == 3, else 0
Ini mungkin jawaban yang dicari Oracle. Ini menunjukkan Anda tahu bagaimana +, -, * dan / operator benar-benar diimplementasikan pada CPU: operasi bitwise sederhana.
craig65535
21
Ini bekerja karena n = 4a + b, n / 3 = a + (a + b) / 3, jadi jumlah + = a, n = a + b, dan iterate. Ketika a == 0 (n <4), jumlah + = lantai (n / 3); yaitu, 1 jika n == 3, kalau tidak 0.
Jim Balter
7
Inilah trik yang saya temukan yang memberi saya solusi serupa. Dalam desimal 1 / 3 = 0.333333:, angka yang berulang membuatnya mudah untuk dihitung menggunakan a / 3 = a/10*3 + a/100*3 + a/1000*3 + (..). Dalam biner itu hampir sama 1 / 3 = 0.0101010101 (base 2):, yang mengarah ke a / 3 = a/4 + a/16 + a/64 + (..). Membagi dengan 4 adalah tempat bit shift berasal. Pemeriksaan terakhir pada num == 3 diperlukan karena kami hanya memiliki bilangan bulat untuk dikerjakan.
Yorick Sijsling
4
Dalam basis 4 itu akan lebih baik: a / 3 = a * 0.111111 (base 4) = a * 4^-1 + a * 4^-2 + a * 4^-3 + (..) = a >> 2 + a >> 4 + a >> 6 + (..). Basis 4 juga menjelaskan mengapa hanya 3 yang dibulatkan pada akhirnya, sedangkan 1 dan 2 dapat dibulatkan ke bawah.
Yorick Sijsling
2
@ while1: bitwise DAN operasi. Juga, fakta yang terkenal adalah bahwa untuk n == 2^kyang berikut ini benar:, x % n == x & (n-1)jadi di sini num & 3digunakan untuk melakukan num % 4sementara %tidak diizinkan.
@earlNameless: Anda tidak tahu apa yang mereka gunakan di dalam, mereka berada di kotak hitam "implementasi yang ditentukan". Tidak ada yang menghentikan mereka untuk hanya menggunakan operator bitwise; Lagi pula, mereka berada di luar domain kode saya, jadi itu bukan masalah saya. :)
Matteo Italia
8
@IvoFlipse dari saya dapat membersihkan, Anda mendapatkan sesuatu yang besar dan mendorongnya menjadi sesuatu yang tiga kali terlalu kecil, dan kemudian melihat berapa banyak yang pas. Itu sekitar sepertiga.
Pureferret
27
tanya programmer C terbaik (dan paling canggung secara sosial) di perusahaan kami untuk menjelaskan kode. setelah itu, saya katakan itu cukup cerdik. Dia mengatakan 'minuman keras ini bukan solusi' dan meminta saya untuk meninggalkan mejanya
cvursache
6
@cvursache Saya pikir intinya adalah bahwa pertanyaannya adalah mati otak, bahwa jawaban mati otak diperbolehkan. "Pemrogram C terbaik" di perusahaan Anda "dapat dengan mudah mengatakan" bahwa kecerobohan bukan pertanyaan (yang pantas) "
JeremyP
17
@ JeremyP: persis. Maksud saya adalah jika dalam kehidupan nyata saya diberi kompiler tanpa dukungan untuk aritmatika , satu-satunya hal yang masuk akal adalah meminta kompiler yang lebih baik , karena bekerja dalam kondisi itu tidak masuk akal. Jika pewawancara ingin memeriksa pengetahuan saya tentang bagaimana menerapkan divisi dengan operasi bitwise, ia bisa langsung dan menanyakannya sebagai pertanyaan teoretis; "latihan trik" semacam ini hanya berteriak untuk jawaban seperti ini.
Ini mungkin benar-benar berfungsi jika dibulatkan dengan benar dan jika jumlahnya tidak terlalu besar.
Mysticial
252
Versi yang ditingkatkan: log (pow (exp (number), sin (atan2 (1, sqrt (8)))))
Alan Curry
@ Bitmask, fungsi matematika biasanya diimplementasikan langsung dalam asm.
SingerOfTheFall
7
saya hanya mengetiknya di konsol js saya, tidak bekerja dengan angka lebih tinggi dari 709 (mungkin hanya sistem saya) Math.log(Math.pow(Math.exp(709),0.33333333333333333333))danMath.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 tidakkah komentar Anda gagal dengan asumsi bahwa jawabannya tidak dapat ditulis dalam C? Bagaimanapun juga, pertanyaan itu ditandai "C".
Seth Carnegie
1
@SethCarnegie Jawabannya tidak ditulis dalam C adalah poin saya. assembler x86 bukan bagian dari standar.
JeremyP
1
@ JeremyP itu benar, tetapi asmarahannya. Dan saya akan menambahkan bahwa kompiler C bukan satu-satunya yang memiliki inline assembler, Delphi juga memilikinya.
Seth Carnegie
7
@SethCarnegie asmArahan hanya disebutkan dalam standar C99 di bawah Lampiran J - ekstensi umum.
JeremyP
2
Gagal pada arm-eabi-gcc.
Damian Yerrick
106
Gunakan itoa untuk mengonversi ke string base 3. Jatuhkan trit terakhir dan ubah kembali ke 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 Saya sebenarnya tidak tahu yang itoabisa menggunakan basis sewenang-wenang. Jika Anda melakukan implementasi kerja yang lengkap menggunakan itoasaya akan mengungguli.
Mysticial
2
Implementasi akan berisi /dan %... :-)
R .. GitHub BERHENTI MEMBANTU ICE
2
@ R .. Begitu juga implementasi printfuntuk menampilkan hasil desimal Anda.
Damian Yerrick
57
(catatan: lihat Edit 2 di bawah untuk versi yang lebih baik!)
Ini tidak sesulit kedengarannya, karena Anda mengatakan "tanpa menggunakan operator [..] +[..] ". Lihat di bawah, jika Anda ingin melarang menggunakan karakter bersama-sama.+
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;}
lalu katakan saja div_by(100,3)untuk membagi 100dengan 3.
Sunting : Anda dapat melanjutkan dan mengganti ++operator juga:
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: Sedikit lebih cepat versi tanpa menggunakan operator manapun yang berisi +, -, *, /, %karakter .
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;}
Kami menggunakan argumen pertama dari addfungsi karena kami tidak dapat menunjukkan tipe pointer tanpa menggunakan *karakter, kecuali dalam daftar parameter fungsi, di mana sintaks type[]identik dengan type* const.
FWIW, Anda dapat dengan mudah menerapkan fungsi multiplikasi menggunakan trik serupa untuk menggunakan 0x55555556trik yang diusulkan oleh AndreyT :
int mul(intconst x,intconst y){returnsizeof(struct{charconst ignore[y];}[x]);}
Saya tidak yakin apakah sangat mungkin untuk mengimplementasikan kompiler C yang sesuai pada platform semacam itu. Kita mungkin harus meregangkan aturan sedikit, seperti menafsirkan "setidaknya 8 bit" sebagai "mampu menahan setidaknya bilangan bulat dari -128 ke +127".
Masalahnya adalah Anda tidak memiliki operator "shift right by 1 place" di C. >>Operator adalah operator "division by 2 ^ n", artinya ditentukan dalam hal aritmatika, bukan representasi mesin.
R .. GitHub BERHENTI MEMBANTU ICE
Komputer Setun bukan biner dalam arti kata, jadi set instruksi pasti berbeda. Namun, saya sama sekali tidak akrab dengan pengoperasian komputer itu, jadi saya tidak dapat mengkonfirmasi apakah responsnya benar - tetapi setidaknya masuk akal - dan sangat asli. +1
virolino
32
Karena ini dari Oracle, bagaimana dengan tabel pencarian jawaban yang dihitung sebelumnya. :-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);}
Pertama, perhatikan itu
1/3=1/4+1/16+1/64+...
Sekarang, sisanya sederhana!
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+...
Sekarang yang harus kita lakukan adalah menambahkan nilai bit bergeser dari! Ups! Kami tidak dapat menambahkan, jadi alih-alih, kami harus menulis fungsi tambah menggunakan operator bit-wise! Jika Anda terbiasa dengan operator bit-bijaksana, solusi saya harus terlihat cukup sederhana ... tetapi jika Anda tidak, saya akan membahas contoh di akhir.
Satu hal yang perlu diperhatikan adalah saya pertama kali bergeser ke kiri sebanyak 30! Ini untuk memastikan bahwa pecahan tidak dibulatkan.
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!
Ini hanya membawa tambahan yang Anda pelajari sejak kecil!
1111011+0110-----10001
Implementasi ini gagal karena kami tidak dapat menambahkan semua persyaratan persamaan:
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
Misalkan reslut dari div_by_3(a)= x, lalu x <= floor(f(a, i)) < a / 3. Ketika a = 3k, kami mendapat jawaban yang salah.
apakah itu berfungsi untuk input 3? 1/4, 1/16, ... semua mengembalikan 0 untuk 3, jadi akan berjumlah 0, tetapi 3/3 = 1.
kapak - dilakukan dengan SOverflow
1
Logikanya bagus tetapi implementasinya bermasalah. Serangkaian aproksimasi n/3selalu kurang dari n/3yang berarti bahwa untuk setiap n=3khasil akan menjadi k-1bukan k.
Xyand
@Albert, Ini adalah pendekatan pertama yang saya coba, dengan beberapa variasi, tetapi mereka semua gagal pada angka-angka tertentu yang dapat dibagi dengan 3 atau secara merata dibagi dengan 2 (tergantung pada variasi). Jadi saya mencoba sesuatu yang lebih mudah. Saya ingin melihat implementasi dari pendekatan ini yang berfungsi, untuk melihat di mana saya mengacau.
kapak - dilakukan dengan SOverflow
@hatchet, Pertanyaannya sudah ditutup jadi saya tidak bisa mengirim jawaban baru tetapi idenya adalah untuk mengimplementasikan binary div. Saya harus mudah mencarinya.
Ini adalah trik kompiler umum untuk mengatasi divisi yang lambat. Tetapi Anda mungkin perlu melakukan beberapa perbaikan, karena 0x55555556 / 2 ** 32 tidak persis 1/3.
CodesInChaos
multiply it. Bukankah itu menyiratkan menggunakan *operator terlarang ?
luiscubal
8
@luiscubal: Tidak, tidak akan. Inilah sebabnya saya mengatakan: "Sekarang yang tersisa untuk dilakukan adalah menerapkan perkalian menggunakan operasi bit dan shift "
AnT
18
Namun solusi lain. Ini harus menangani semua int (termasuk int negatif) kecuali nilai minimum int, yang perlu ditangani sebagai pengecualian kode keras. Ini pada dasarnya melakukan pembagian dengan mengurangi tetapi hanya menggunakan operator bit (shift, xor, & dan pelengkap). Untuk kecepatan yang lebih cepat, ini mengurangi 3 * (mengurangi kekuatan 2). Dalam c #, ia mengeksekusi sekitar 444 dari panggilan DivideBy3 ini per milidetik (2,2 detik untuk 1.000.000 pembagian), jadi tidak terlalu lambat, tapi tidak sedekat kecepatan x / 3 sederhana. Sebagai perbandingan, solusi bagus Coodey adalah sekitar 5 kali lebih cepat daripada yang ini.
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;}
Ini adalah c # karena itulah yang saya miliki, tetapi perbedaan dari c harus kecil.
Anda hanya perlu mencoba untuk mengurangi sub sekali, karena jika Anda bisa mengurangkannya dua kali maka Anda bisa menguranginya iterasi sebelumnya ketika itu dua kali lebih besar dari sekarang.
Neil
Apakah (a >= sub)dihitung sebagai pengurangan?
Neil
@Neil, saya pikir Anda mungkin benar. Sementara bagian dalam dapat diganti dengan sederhana jika, menyimpan perbandingan yang tidak dibutuhkan dari iterasi kedua loop. Mengenai> = menjadi pengurangan ... Saya harap tidak, karena itu akan membuat melakukan ini cukup sulit! Saya mengerti maksud Anda, tetapi saya pikir saya akan bersandar pada sisi yang mengatakan> = tidak dihitung sebagai pengurangan.
kapak - dilakukan dengan SOverflow
@ Neil, saya membuat perubahan itu, yang memotong waktu menjadi dua (juga menghemat Negate yang tidak dibutuhkan).
(Tentu saja saya telah menghapus beberapa program demi singkatnya.) Jika programmer bosan mengetik semua ini, saya yakin dia bisa menulis program terpisah untuk membuatnya untuknya. Saya kebetulan mengetahui operator tertentu /,, yang akan sangat menyederhanakan pekerjaannya.
@ Enes Unal: bukan untuk angka kecil :) Algoritma ini sangat mendasar.
GJ.
Setiap keprimitifan mencakup kelemahan :)
dimulai
11
Ini adalah algoritma pembagian klasik di 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);}
Tulis program dalam Pascal dan gunakan DIVoperator.
Karena pertanyaan ini ditandai c, Anda mungkin dapat menulis fungsi dalam Pascal dan memanggilnya dari program C Anda; metode untuk melakukannya adalah spesifik sistem.
Tapi ini adalah contoh yang berfungsi pada sistem Ubuntu saya dengan fp-compilerpaket Free Pascal diinstal. (Saya melakukan ini karena sikap keras kepala yang salah tempat; saya tidak mengklaim bahwa ini berguna.)
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;}
Untuk membangun:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
++ dan - operaors berbeda dari + dan - operaors! Dalam bahasa assembly ada dua instruksi ADDdan INCmereka tidak memiliki opcode yang sama.
Amir Saniyan
7
Tidak memeriksa ulang apakah jawaban ini sudah dipublikasikan. Jika program perlu diperluas ke angka mengambang, angka tersebut dapat dikalikan dengan 10 * jumlah presisi yang diperlukan dan kemudian kode berikut dapat diterapkan kembali.
#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;}
Ini harus bekerja untuk semua pembagi, tidak hanya tiga. Saat ini hanya untuk yang tidak ditandatangani, tetapi memperpanjangnya untuk ditandatangani seharusnya tidak terlalu sulit.
#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;}
Bagaimana ini tidak menggunakan -maupun *Operator?
bitmask
4
Bagaimana dengan pendekatan ini (c #)?
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;}
Karena yang ingin mereka ketahui adalah jika Anda tahu cara kerja prosesor secara internal ... menggunakan operator matematika pada akhirnya akan melakukan operasi yang sangat mirip dengan jawaban di atas.
RaptorX
Atau mereka ingin tahu apakah Anda bisa mengenali masalah yang tidak berguna.
Gregoire
1
@ Gregoire Saya setuju, Ada aboloultley tidak perlu melakukan implementasi seperti itu, Bit dalam kehidupan komersial (Orcale) tidak perlu untuk menghindari memenuhi persyaratan yang tidak berguna: Jawaban yang benar adalah: "Ini tidak masuk akal sama sekali, mengapa kehilangan uang untuk itu? ")
#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);}
Yah, itu hanya detail implementasi sehingga saya bisa mengetiknya sebagai 3.0 / 1.0 bukannya 0.333333, tapi saya harus bermain sesuai aturan. Tetap!
wjl
Saya awalnya memilikinya sebagai 3.0 / 1.0, yang tidak dalam pengujian saya. Dengan menggunakan angka presisi yang lebih tinggi, mereka harus mendapatkan hasil yang cukup akurat. gist.github.com/3401496
Kemudian cari tahu bagaimana menyelesaikan x / (1 - y):
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))
dengan 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)}
Meskipun menggunakan +, tetapi seseorang sudah mengimplementasikan add by bitwise op.
Jawaban:
Ini adalah fungsi sederhana yang melakukan operasi yang diinginkan. Tapi itu membutuhkan
+
operator, jadi yang harus Anda lakukan adalah menambahkan nilai dengan operator bit:Seperti yang dikomentari Jim, ini bekerja, karena:
n = 4 * a + b
n / 3 = a + (a + b) / 3
Jadi
sum += a
,n = a + b
, dan iterateKapan
a == 0 (n < 4)
,sum += floor(n / 3);
yaitu 1,if n == 3, else 0
sumber
1 / 3 = 0.333333
:, angka yang berulang membuatnya mudah untuk dihitung menggunakana / 3 = a/10*3 + a/100*3 + a/1000*3 + (..)
. Dalam biner itu hampir sama1 / 3 = 0.0101010101 (base 2)
:, yang mengarah kea / 3 = a/4 + a/16 + a/64 + (..)
. Membagi dengan 4 adalah tempat bit shift berasal. Pemeriksaan terakhir pada num == 3 diperlukan karena kami hanya memiliki bilangan bulat untuk dikerjakan.a / 3 = a * 0.111111 (base 4) = a * 4^-1 + a * 4^-2 + a * 4^-3 + (..) = a >> 2 + a >> 4 + a >> 6 + (..)
. Basis 4 juga menjelaskan mengapa hanya 3 yang dibulatkan pada akhirnya, sedangkan 1 dan 2 dapat dibulatkan ke bawah.n == 2^k
yang berikut ini benar:,x % n == x & (n-1)
jadi di sininum & 3
digunakan untuk melakukannum % 4
sementara%
tidak diizinkan.Kondisi idiot membutuhkan solusi idiot:
Jika juga bagian desimal diperlukan, cukup deklarasikan
result
sebagaidouble
dan tambahkan hasilnyafmod(number,divisor)
.Penjelasan tentang cara kerjanya
fwrite
menulisnumber
byte (jumlah menjadi 123.456 dalam contoh di atas).rewind
mengatur ulang penunjuk file ke bagian depan file.fread
membaca maksimumnumber
"catatan" yangdivisor
panjangnya dari file, dan mengembalikan jumlah elemen yang dibacanya.Jika Anda menulis 30 byte kemudian membaca kembali file dalam unit 3, Anda mendapatkan 10 "unit". 30/3 = 10
sumber
sumber
Math.log(Math.pow(Math.exp(709),0.33333333333333333333))
danMath.log(Math.pow(Math.exp(709),Math.sin(Math.atan2(1,Math.sqrt(8)))))
sumber
Anda dapat menggunakan perakitan inline (tergantung platform), mis. Untuk x86: (juga berfungsi untuk angka negatif)
sumber
asm
arahannya. Dan saya akan menambahkan bahwa kompiler C bukan satu-satunya yang memiliki inline assembler, Delphi juga memilikinya.asm
Arahan hanya disebutkan dalam standar C99 di bawah Lampiran J - ekstensi umum.Gunakan itoa untuk mengonversi ke string base 3. Jatuhkan trit terakhir dan ubah kembali ke basis 10.
sumber
itoa
bisa menggunakan basis sewenang-wenang. Jika Anda melakukan implementasi kerja yang lengkap menggunakanitoa
saya akan mengungguli./
dan%
... :-)printf
untuk menampilkan hasil desimal Anda.(catatan: lihat Edit 2 di bawah untuk versi yang lebih baik!)
Ini tidak sesulit kedengarannya, karena Anda mengatakan "tanpa menggunakan operator [..]
+
[..] ". Lihat di bawah, jika Anda ingin melarang menggunakan karakter bersama-sama.+
lalu katakan saja
div_by(100,3)
untuk membagi100
dengan3
.Sunting : Anda dapat melanjutkan dan mengganti
++
operator juga:Edit 2: Sedikit lebih cepat versi tanpa menggunakan operator manapun yang berisi
+
,-
,*
,/
,%
karakter .Kami menggunakan argumen pertama dari
add
fungsi karena kami tidak dapat menunjukkan tipe pointer tanpa menggunakan*
karakter, kecuali dalam daftar parameter fungsi, di mana sintakstype[]
identik dengantype* const
.FWIW, Anda dapat dengan mudah menerapkan fungsi multiplikasi menggunakan trik serupa untuk menggunakan
0x55555556
trik yang diusulkan oleh AndreyT :sumber
++
: Mengapa Anda tidak menggunakan saja/=
?++
juga merupakan jalan pintas: Untuknum = num + 1
.+=
akhirnya jalan pintas untuknum = num + 1
.Mudah dilakukan di komputer Setun .
Untuk membagi bilangan bulat dengan 3, geser ke kanan dengan 1 tempat .
Saya tidak yakin apakah sangat mungkin untuk mengimplementasikan kompiler C yang sesuai pada platform semacam itu. Kita mungkin harus meregangkan aturan sedikit, seperti menafsirkan "setidaknya 8 bit" sebagai "mampu menahan setidaknya bilangan bulat dari -128 ke +127".
sumber
>>
Operator adalah operator "division by 2 ^ n", artinya ditentukan dalam hal aritmatika, bukan representasi mesin.Karena ini dari Oracle, bagaimana dengan tabel pencarian jawaban yang dihitung sebelumnya. :-D
sumber
Inilah solusi saya:
Pertama, perhatikan itu
Sekarang, sisanya sederhana!
Sekarang yang harus kita lakukan adalah menambahkan nilai bit bergeser dari! Ups! Kami tidak dapat menambahkan, jadi alih-alih, kami harus menulis fungsi tambah menggunakan operator bit-wise! Jika Anda terbiasa dengan operator bit-bijaksana, solusi saya harus terlihat cukup sederhana ... tetapi jika Anda tidak, saya akan membahas contoh di akhir.
Satu hal yang perlu diperhatikan adalah saya pertama kali bergeser ke kiri sebanyak 30! Ini untuk memastikan bahwa pecahan tidak dibulatkan.
Ini hanya membawa tambahan yang Anda pelajari sejak kecil!
Implementasi ini gagal karena kami tidak dapat menambahkan semua persyaratan persamaan:
Misalkan reslut dari
div_by_3(a)
= x, lalux <= floor(f(a, i)) < a / 3
. Ketikaa = 3k
, kami mendapat jawaban yang salah.sumber
n/3
selalu kurang darin/3
yang berarti bahwa untuk setiapn=3k
hasil akan menjadik-1
bukank
.Untuk membagi angka 32-bit dengan 3 orang dapat mengalikannya dengan
0x55555556
dan kemudian mengambil 32 bit atas dari hasil 64 bit.Sekarang yang harus dilakukan adalah mengimplementasikan perkalian menggunakan operasi bit dan pergeseran ...
sumber
multiply it
. Bukankah itu menyiratkan menggunakan*
operator terlarang ?Namun solusi lain. Ini harus menangani semua int (termasuk int negatif) kecuali nilai minimum int, yang perlu ditangani sebagai pengecualian kode keras. Ini pada dasarnya melakukan pembagian dengan mengurangi tetapi hanya menggunakan operator bit (shift, xor, & dan pelengkap). Untuk kecepatan yang lebih cepat, ini mengurangi 3 * (mengurangi kekuatan 2). Dalam c #, ia mengeksekusi sekitar 444 dari panggilan DivideBy3 ini per milidetik (2,2 detik untuk 1.000.000 pembagian), jadi tidak terlalu lambat, tapi tidak sedekat kecepatan x / 3 sederhana. Sebagai perbandingan, solusi bagus Coodey adalah sekitar 5 kali lebih cepat daripada yang ini.
Ini adalah c # karena itulah yang saya miliki, tetapi perbedaan dari c harus kecil.
sumber
(a >= sub)
dihitung sebagai pengurangan?Ini sangat mudah.
(Tentu saja saya telah menghapus beberapa program demi singkatnya.) Jika programmer bosan mengetik semua ini, saya yakin dia bisa menulis program terpisah untuk membuatnya untuknya. Saya kebetulan mengetahui operator tertentu
/
,, yang akan sangat menyederhanakan pekerjaannya.sumber
Dictionary<number, number>
alih - alih berulangif
sehingga Anda dapat memilikiO(1)
kompleksitas waktu!Menggunakan penghitung adalah solusi dasar:
Juga mudah untuk melakukan fungsi modulus, periksa komentar.
sumber
Ini adalah algoritma pembagian klasik di basis 2:
sumber
Tulis program dalam Pascal dan gunakan
DIV
operator.Karena pertanyaan ini ditandai c, Anda mungkin dapat menulis fungsi dalam Pascal dan memanggilnya dari program C Anda; metode untuk melakukannya adalah spesifik sistem.
Tapi ini adalah contoh yang berfungsi pada sistem Ubuntu saya dengan
fp-compiler
paket Free Pascal diinstal. (Saya melakukan ini karena sikap keras kepala yang salah tempat; saya tidak mengklaim bahwa ini berguna.)divide_by_3.pas
:main.c
:Untuk membangun:
Eksekusi sampel:
sumber
sumber
ADD
danINC
mereka tidak memiliki opcode yang sama.Tidak memeriksa ulang apakah jawaban ini sudah dipublikasikan. Jika program perlu diperluas ke angka mengambang, angka tersebut dapat dikalikan dengan 10 * jumlah presisi yang diperlukan dan kemudian kode berikut dapat diterapkan kembali.
sumber
Ini harus bekerja untuk semua pembagi, tidak hanya tiga. Saat ini hanya untuk yang tidak ditandatangani, tetapi memperpanjangnya untuk ditandatangani seharusnya tidak terlalu sulit.
sumber
Apakah curang menggunakan
/
operator "di belakang layar" dengan menggunakaneval
dan merangkai tali?Misalnya, dalam Javacript, Anda bisa melakukannya
sumber
Menggunakan BC Math dalam PHP :
MySQL (ini adalah wawancara dari Oracle)
Pascal :
bahasa assembly x86-64:
sumber
Pertama yang saya pikirkan.
EDIT: Maaf, saya tidak melihat tag
C
. Tetapi Anda dapat menggunakan gagasan tentang pemformatan string, saya kira ...sumber
Script berikut menghasilkan program C yang memecahkan masalah tanpa menggunakan operator
* / + - %
:sumber
Menggunakan kalkulator angka Magic Hack Delight
Di mana fma adalah fungsi perpustakaan standar yang didefinisikan dalam
math.h
header.sumber
-
maupun*
Operator?Bagaimana dengan pendekatan ini (c #)?
sumber
Saya pikir jawaban yang tepat adalah:
Mengapa saya tidak menggunakan operator dasar untuk melakukan operasi dasar?
sumber
Solusi menggunakan fungsi perpustakaan fma () , bekerja untuk semua angka positif:
Lihat jawaban saya yang lain .
sumber
Gunakan cblas , termasuk sebagai bagian dari kerangka kerja Mempercepat OS X.
sumber
Secara umum, solusi untuk ini adalah:
log(pow(exp(numerator),pow(denominator,-1)))
sumber
Pertama:
Kemudian cari tahu bagaimana menyelesaikan x / (1 - y):
dengan y = 1/4:
Meskipun menggunakan
+
, tetapi seseorang sudah mengimplementasikan add by bitwise op.sumber