@AlexandreC. - essas técnicas estão usando adição (+).
hatchet - feito com SOverflow
19
Este era o oracle, então que partes do oracle você podia usar?
Hogan
8
A duplicata identificada não é uma duplicata. Observe que várias respostas aqui não usam deslocamento ou adição de bits, pois essa pergunta não restringiu a solução a essas operações.
Esta é uma função simples que executa a operação desejada. Mas isso requer o +operador, então tudo o que você precisa fazer é adicionar os valores com operadores de bits:
// 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;}
Como Jim comentou, isso funciona, porque:
n = 4 * a + b
n / 3 = a + (a + b) / 3
Assim sum += a, n = a + be iterate
Quando a == 0 (n < 4), sum += floor(n / 3);ou seja, 1,if n == 3, else 0
Essa é provavelmente a resposta que a Oracle está procurando. Ele mostra que você sabe como os operadores +, -, * e / são realmente implementados na CPU: operações bit a bit simples.
craig65535
21
Isso funciona porque n = 4a + b, n / 3 = a + (a + b) / 3, então soma + = a, n = a + b e itera. Quando a == 0 (n <4), soma + = piso (n / 3); ou seja, 1 se n == 3, senão 0.
Jim Balter
7
Aqui está um truque que encontrei que me trouxe uma solução semelhante. Em decimal 1 / 3 = 0.333333:, os números repetidos facilitam o cálculo usando a / 3 = a/10*3 + a/100*3 + a/1000*3 + (..). Em binário é quase o mesmo 1 / 3 = 0.0101010101 (base 2):, o que leva a a / 3 = a/4 + a/16 + a/64 + (..). Dividir por 4 é a origem da mudança de bits. A última verificação de num == 3 é necessária porque só temos números inteiros para trabalhar.
Yorick Sijsling
4
Na base 4 fica ainda melhor: a / 3 = a * 0.111111 (base 4) = a * 4^-1 + a * 4^-2 + a * 4^-3 + (..) = a >> 2 + a >> 4 + a >> 6 + (..). A base 4 também explica por que apenas 3 é arredondado no final, enquanto 1 e 2 podem ser arredondados para baixo.
Yorick Sijsling
2
@ while1: é operação AND bit a bit. Além disso, um fato bem conhecido é que, pelo n == 2^kseguinte, é verdadeiro:, x % n == x & (n-1)portanto, aqui num & 3é usado para executar num % 4enquanto %não é permitido.
@earlNameless: você não sabe o que eles usam por dentro, eles estão na caixa preta de "implementação definida". Nada os impede de usar apenas operadores bit a bit; de qualquer forma, eles estão fora do domínio do meu código, então esse não é o meu problema. :)
Matteo Italia
8
O @IvoFlipse da Posso limpar, você obtém algo grande e o empurra para algo três vezes menor do que o normal , e depois vê o quanto ele se encaixa. Isso é um terço.
Pureferret
27
pediu ao melhor programador C (e mais socialmente estranho) da nossa empresa que explicasse o código. depois que ele fez, eu disse que era bastante engenhoso. Ele disse 'este dreck não é uma solução' e me pediu para deixar sua mesa
cvursache
6
@cvursache Eu acho que o ponto é que a questão é tão cerebral, que é permitida uma resposta de morte cerebral. O "melhor programador C" da sua empresa "poderia facilmente ter dito" que dreck não é uma pergunta (apropriada) ".
JeremyP
17
@ JeremyP: exatamente. Meu argumento é que, se na vida real eu recebesse um compilador sem suporte para aritmética, a única coisa sensata seria pedir um compilador melhor , porque trabalhar nessas condições não faz sentido. Se o entrevistador quis verificar meu conhecimento de como implementar a divisão com operações bit a bit, ele poderia ser direto e fazer uma pergunta teórica; esse tipo de "exercício de truque" apenas grita por respostas como essa.
Isso pode realmente funcionar se arredondado corretamente e se o número não for muito grande.
Mysticial
252
Versão aprimorada: log (pow (exp (número), sin (atan2 (1, sqrt (8)))))
Alan Curry
@bitmask, funções matemáticas geralmente são implementadas diretamente no asm.
SingerOfTheFall 10/10/12
7
Eu apenas digitei no meu console js, ele não funciona com um número maior que 709 (pode ser apenas o meu sistema) Math.log(Math.pow(Math.exp(709),0.33333333333333333333))e #Math.log(Math.pow(Math.exp(709),Math.sin(Math.atan2(1,Math.sqrt(8)))))
060
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, seu comentário não falha na suposição de que a resposta não pode ser escrita em C? A questão está marcada com "C", afinal.
Seth Carnegie
1
@SethCarnegie A resposta não está escrita em C é o meu ponto. O montador x86 não faz parte do padrão.
precisa saber é o seguinte
1
@ JeremyP isso é verdade, mas a asmdiretiva é. E eu acrescentaria que os compiladores C não são os únicos que têm montadores em linha, mas o Delphi também.
Seth Carnegie
7
@SethCarnegie A asmdiretiva é mencionada apenas na norma C99 no Apêndice J - extensões comuns.
precisa saber é o seguinte
2
Falha em arm-eabi-gcc.
Damian Yerrick
106
Use itoa para converter em uma string base 3. Solte o último ponto e converta de volta para a base 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 Na verdade, eu não sabia que itoapoderia usar uma base arbitrária. Se você fizer uma implementação de trabalho completa usando itoaEu vou votar.
Mysticial 27/07/12
2
A implementação conterá /e %... :-)
R .. GitHub Pare de ajudar o gelo
2
@R .. O mesmo acontece com a implementação de printfpara exibir seu resultado decimal.
Damian Yerrick 21/09
57
(nota: veja o Edit 2 abaixo para uma versão melhor!)
Isso não é tão complicado quanto parece, porque você disse "sem usar o [..] + operadores [..] ". Veja abaixo, se você deseja proibir o uso do +personagem todos juntos.
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;}
então diga div_by(100,3)para dividir 100por 3.
Editar : Você também pode substituir o ++operador:
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: versão ligeiramente mais rápido sem usar qualquer operador que contém o +, -, *, /,% caracteres .
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;}
Usamos o primeiro argumento do add função porque não podemos denotar o tipo de ponteiros sem usar o *caractere, exceto nas listas de parâmetros da função, onde a sintaxe type[]é idêntica type* const.
FWIW, você pode implementar facilmente uma função de multiplicação usando um truque semelhante para usar o 0x55555556truque proposto por AndreyT :
int mul(intconst x,intconst y){returnsizeof(struct{charconst ignore[y];}[x]);}
Não tenho certeza se é estritamente possível implementar um compilador C em conformidade nessa plataforma. Talvez tenhamos que esticar um pouco as regras, como interpretar "pelo menos 8 bits" como "capaz de conter pelo menos números inteiros de -128 a +127".
O problema é que você não possui um operador "shift right by 1 place" em C. O >>operador é o operador "division by 2 ^ n", ou seja, é especificado em termos de aritmética e não de representação da máquina.
R .. GitHub Pare de ajudar o gelo
O computador Setun não é binário em nenhum sentido da palavra; portanto, o conjunto de instruções deve ser definitivamente diferente. No entanto, não estou familiarizado com o funcionamento desse computador, portanto não posso confirmar se a resposta está realmente correta - mas pelo menos faz sentido - e é altamente original. +1
virolino 07/02/19
32
Como é da Oracle, que tal uma tabela de pesquisa de respostas pré-calculadas. :-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);}
Primeiro, observe que
1/3=1/4+1/16+1/64+...
Agora, o resto é simples!
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+...
Agora, tudo o que precisamos fazer é somar esses valores de a! Opa! No entanto, não podemos adicionar, portanto, teremos que escrever uma função de adição usando operadores bit a bit! Se você está familiarizado com os operadores bit-wise, minha solução deve parecer bastante simples ... mas, caso você não esteja, analisarei um exemplo no final.
Outra coisa a notar é que primeiro eu mudo para a esquerda por 30! Isso é para garantir que as frações não sejam arredondadas.
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!
É simplesmente levar adição que você aprendeu quando criança!
1111011+0110-----10001
Esta implementação falhou porque não podemos adicionar todos os termos da equação:
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
Suponha o resultado de div_by_3(a)= x, então x <= floor(f(a, i)) < a / 3. Quando a = 3k, recebemos uma resposta errada.
funciona para entrada de 3? 1/4, 1/16, ... tudo de retorno 0 para 3, assim resumiria a 0, mas 3/3 = 1.
machado - feito com SOverflow
1
A lógica é boa, mas a implementação é problemática. A aproximação em série de n/3é sempre menor do n/3que significa que para qualquer n=3ko resultado seria em k-1vez de k.
Xyand
@ Albert, esta foi a primeira abordagem que tentei, com algumas variações, mas todas falharam em determinados números igualmente divisíveis por 3 ou igualmente divisíveis por 2 (dependendo da variação). Então, tentei algo mais direto. Eu gostaria de ver uma implementação dessa abordagem que funcione, para ver onde eu estava estragando tudo.
machado - feito com SOverflow 28/07/12
@hatchet, A questão está encerrada, por isso não posso postar uma nova resposta, mas a ideia é implementar div binária. Eu deveria ser fácil procurar.
Esse é um truque comum do compilador para solucionar divisões lentas. Mas você provavelmente precisa fazer algumas correções, pois 0x55555556 / 2 ** 32 não é exatamente 1/3.
CodesInChaos
multiply it. Isso não implicaria o uso do *operador proibido ?
27612 luiscubal
8
@luiscubal: Não, não vai. É por isso que eu disse: "Agora, tudo o que resta a fazer é implementar a multiplicação usando operações e turnos de bits " #
277
18
Mais uma solução. Isso deve lidar com todas as entradas (incluindo entradas negativas), exceto o valor mínimo de um int, que precisaria ser tratado como uma exceção codificada. Isso basicamente divide por subtração, mas apenas usando operadores de bits (turnos, xor e & e complemento). Para uma velocidade mais rápida, subtrai 3 * (potências decrescentes de 2). No c #, ele executa cerca de 444 dessas chamadas DivideBy3 por milissegundo (2,2 segundos para 1.000.000 de divisões), portanto, não é terrivelmente lento, mas não é tão rápido quanto um x / 3 simples. Em comparação, a boa solução da Coodey é cerca de 5 vezes mais rápida que esta.
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;}
Isso é c # porque é isso que eu tinha à mão, mas as diferenças de c devem ser menores.
Você só precisa tentar subtrair sub uma vez, porque se você pudesse subtraí-lo duas vezes, poderia subtraí-lo na iteração anterior, quando era duas vezes maior do que é agora.
315 Neil
Conta (a >= sub)como uma subtração?
315 Neil
@ Neil, acho que você pode estar certo. O tempo interno pode ser substituído por um simples if, salvando uma comparação desnecessária da segunda iteração do loop. Em relação a> = ser subtração ... Espero que não, porque isso tornaria isso muito difícil! Entendo o seu ponto de vista, mas acho que me apoiaria no lado que diz que> = não conta como subtração.
machado - feito com SOverflow 28/07/12
@ Neil, fiz essa alteração, que cortou o tempo pela metade (também salvou Negates desnecessários).
(Obviamente, omiti parte do programa por questões de brevidade.) Se o programador se cansar de digitar tudo isso, tenho certeza de que ele ou ela poderia escrever um programa separado para gerá-lo para ele. Por acaso, estou ciente de um certo operador /que simplificaria imensamente o trabalho dele.
@ Enes Unal: não para pequenos números :) Este algoritmo é muito básico.
GJ.
Cada primitivismo inclui fraquezas :)
totten
11
Este é o algoritmo de divisão clássica na base 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);}
Como a pergunta está marcada c, você provavelmente pode escrever uma função no Pascal e chamá-la no seu programa C; o método para fazer isso é específico do sistema.
Mas aqui está um exemplo que funciona no meu sistema Ubuntu com o fp-compilerpacote Free Pascal instalado. (Estou fazendo isso por pura teimosia extraviada; não afirmo que isso seja útil.)
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;}
Construir:
fpc divide_by_3.pas && gcc divide_by_3.o main.c -o main
Os operadores ++ e - são diferentes dos + e -! Na linguagem assembly, existem duas instruções ADDe INCelas não têm os mesmos códigos de operação.
Amir Saniyan
7
Não checou se esta resposta já foi publicada. Se o programa precisar ser estendido para números flutuantes, os números poderão ser multiplicados por 10 * o número de precisão necessária e o código a seguir poderá ser aplicado novamente.
#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;}
Isso deve funcionar para qualquer divisor, não apenas para três. Atualmente, apenas para não assinado, mas estendê-lo para assinado não deve ser tão difícil.
#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;}
Porque o que eles querem saber é se você sabe como o processador funciona internamente ... o uso de um operador matemático acabará por executar uma operação muito semelhante à resposta acima.
RaptorX 5/11/12
Ou eles querem saber se você pode reconhecer um problema inútil.
Gregoire
1
@Gregoire Eu concordo, não há absolutamente nenhuma necessidade de fazer tal implementação, é pouco necessário na vida comercial (Orcale) para evitar o cumprimento de requisitos inúteis: A resposta correta é: "Isso não faz nenhum sentido, porque perder dinheiro para isso? ")
#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);}
Bem, isso foi apenas um detalhe de implementação, para que eu pudesse digitá-lo como 3.0 / 1.0 em vez de 0.333333, mas devo seguir as regras. Fixo!
Wjl 30/07/12
Originalmente, tinha 3.0 / 1.0, o que ocorreu no meu teste. Usando um número de precisão mais alto, eles devem obter um resultado razoavelmente preciso. 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))
com 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)}
Embora ele use +, mas alguém já implementa add por bit a op.
Respostas:
Esta é uma função simples que executa a operação desejada. Mas isso requer o
+
operador, então tudo o que você precisa fazer é adicionar os valores com operadores de bits:Como Jim comentou, isso funciona, porque:
n = 4 * a + b
n / 3 = a + (a + b) / 3
Assim
sum += a
,n = a + b
e iterateQuando
a == 0 (n < 4)
,sum += floor(n / 3);
ou seja, 1,if n == 3, else 0
fonte
1 / 3 = 0.333333
:, os números repetidos facilitam o cálculo usandoa / 3 = a/10*3 + a/100*3 + a/1000*3 + (..)
. Em binário é quase o mesmo1 / 3 = 0.0101010101 (base 2)
:, o que leva aa / 3 = a/4 + a/16 + a/64 + (..)
. Dividir por 4 é a origem da mudança de bits. A última verificação de num == 3 é necessária porque só temos números inteiros para trabalhar.a / 3 = a * 0.111111 (base 4) = a * 4^-1 + a * 4^-2 + a * 4^-3 + (..) = a >> 2 + a >> 4 + a >> 6 + (..)
. A base 4 também explica por que apenas 3 é arredondado no final, enquanto 1 e 2 podem ser arredondados para baixo.n == 2^k
seguinte, é verdadeiro:,x % n == x & (n-1)
portanto, aquinum & 3
é usado para executarnum % 4
enquanto%
não é permitido.Condições idiotas exigem uma solução idiota:
Se também for necessária a parte decimal, basta declarar
result
comodouble
e adicionar o resultado defmod(number,divisor)
.Explicação de como funciona
fwrite
gravaçãonumber
(número sendo 123456 no exemplo acima).rewind
redefine o ponteiro do arquivo para a frente do arquivo.fread
lê no máximonumber
"registros" que estãodivisor
no arquivo e retorna o número de elementos que ele lê.Se você escrever 30 bytes e depois ler novamente o arquivo em unidades de 3, obterá 10 "unidades". 30/3 = 10
fonte
fonte
Math.log(Math.pow(Math.exp(709),0.33333333333333333333))
e #Math.log(Math.pow(Math.exp(709),Math.sin(Math.atan2(1,Math.sqrt(8)))))
fonte
Você pode usar montagem em linha (dependente da plataforma), por exemplo, para x86: (também funciona para números negativos)
fonte
asm
diretiva é. E eu acrescentaria que os compiladores C não são os únicos que têm montadores em linha, mas o Delphi também.asm
diretiva é mencionada apenas na norma C99 no Apêndice J - extensões comuns.Use itoa para converter em uma string base 3. Solte o último ponto e converta de volta para a base 10.
fonte
itoa
poderia usar uma base arbitrária. Se você fizer uma implementação de trabalho completa usandoitoa
Eu vou votar./
e%
... :-)printf
para exibir seu resultado decimal.(nota: veja o Edit 2 abaixo para uma versão melhor!)
Isso não é tão complicado quanto parece, porque você disse "sem usar o [..]
+
operadores [..] ". Veja abaixo, se você deseja proibir o uso do+
personagem todos juntos.então diga
div_by(100,3)
para dividir100
por3
.Editar : Você também pode substituir o
++
operador:Edit 2: versão ligeiramente mais rápido sem usar qualquer operador que contém o
+
,-
,*
,/
,%
caracteres .Usamos o primeiro argumento do
add
função porque não podemos denotar o tipo de ponteiros sem usar o*
caractere, exceto nas listas de parâmetros da função, onde a sintaxetype[]
é idênticatype* const
.FWIW, você pode implementar facilmente uma função de multiplicação usando um truque semelhante para usar o
0x55555556
truque proposto por AndreyT :fonte
++
: Por que você simplesmente não usa/=
?++
também é um atalho: paranum = num + 1
.+=
é finalmente um atalho paranum = num + 1
.É facilmente possível no computador Setun .
Para dividir um número inteiro por 3, desloque para a direita por 1 lugar .
Não tenho certeza se é estritamente possível implementar um compilador C em conformidade nessa plataforma. Talvez tenhamos que esticar um pouco as regras, como interpretar "pelo menos 8 bits" como "capaz de conter pelo menos números inteiros de -128 a +127".
fonte
>>
operador é o operador "division by 2 ^ n", ou seja, é especificado em termos de aritmética e não de representação da máquina.Como é da Oracle, que tal uma tabela de pesquisa de respostas pré-calculadas. :-D
fonte
Aqui está a minha solução:
Primeiro, observe que
Agora, o resto é simples!
Agora, tudo o que precisamos fazer é somar esses valores de a! Opa! No entanto, não podemos adicionar, portanto, teremos que escrever uma função de adição usando operadores bit a bit! Se você está familiarizado com os operadores bit-wise, minha solução deve parecer bastante simples ... mas, caso você não esteja, analisarei um exemplo no final.
Outra coisa a notar é que primeiro eu mudo para a esquerda por 30! Isso é para garantir que as frações não sejam arredondadas.
É simplesmente levar adição que você aprendeu quando criança!
Esta implementação falhou porque não podemos adicionar todos os termos da equação:
Suponha o resultado de
div_by_3(a)
= x, entãox <= floor(f(a, i)) < a / 3
. Quandoa = 3k
, recebemos uma resposta errada.fonte
n/3
é sempre menor don/3
que significa que para qualquern=3k
o resultado seria emk-1
vez dek
.Para dividir um número de 32 bits por 3, pode-se multiplicá-lo
0x55555556
e, em seguida, obter os 32 bits superiores do resultado de 64 bits.Agora tudo o que resta a fazer é implementar a multiplicação usando operações e turnos de bits ...
fonte
multiply it
. Isso não implicaria o uso do*
operador proibido ?Mais uma solução. Isso deve lidar com todas as entradas (incluindo entradas negativas), exceto o valor mínimo de um int, que precisaria ser tratado como uma exceção codificada. Isso basicamente divide por subtração, mas apenas usando operadores de bits (turnos, xor e & e complemento). Para uma velocidade mais rápida, subtrai 3 * (potências decrescentes de 2). No c #, ele executa cerca de 444 dessas chamadas DivideBy3 por milissegundo (2,2 segundos para 1.000.000 de divisões), portanto, não é terrivelmente lento, mas não é tão rápido quanto um x / 3 simples. Em comparação, a boa solução da Coodey é cerca de 5 vezes mais rápida que esta.
Isso é c # porque é isso que eu tinha à mão, mas as diferenças de c devem ser menores.
fonte
(a >= sub)
como uma subtração?É realmente muito fácil.
(Obviamente, omiti parte do programa por questões de brevidade.) Se o programador se cansar de digitar tudo isso, tenho certeza de que ele ou ela poderia escrever um programa separado para gerá-lo para ele. Por acaso, estou ciente de um certo operador
/
que simplificaria imensamente o trabalho dele.fonte
Dictionary<number, number>
vez de repetidasif
para terO(1)
complexidade de tempo!Usar contadores é uma solução básica:
Também é fácil executar uma função de módulo, verifique os comentários.
fonte
Este é o algoritmo de divisão clássica na base 2:
fonte
Escreva o programa em Pascal e use o
DIV
operador.Como a pergunta está marcada c, você provavelmente pode escrever uma função no Pascal e chamá-la no seu programa C; o método para fazer isso é específico do sistema.
Mas aqui está um exemplo que funciona no meu sistema Ubuntu com o
fp-compiler
pacote Free Pascal instalado. (Estou fazendo isso por pura teimosia extraviada; não afirmo que isso seja útil.)divide_by_3.pas
:main.c
:Construir:
Execução de amostra:
fonte
fonte
ADD
eINC
elas não têm os mesmos códigos de operação.Não checou se esta resposta já foi publicada. Se o programa precisar ser estendido para números flutuantes, os números poderão ser multiplicados por 10 * o número de precisão necessária e o código a seguir poderá ser aplicado novamente.
fonte
Isso deve funcionar para qualquer divisor, não apenas para três. Atualmente, apenas para não assinado, mas estendê-lo para assinado não deve ser tão difícil.
fonte
Seria trapaça usar o
/
operador "nos bastidores" usando umaeval
concatenação de strings?Por exemplo, em Javacript, você pode fazer
fonte
Usando BC Math em PHP :
MySQL (é uma entrevista da Oracle)
Pascal :
linguagem de montagem x86-64:
fonte
Primeiro que eu inventei.
EDIT: Desculpe, eu não percebi a tag
C
. Mas você pode usar a idéia sobre formatação de string, eu acho ...fonte
O script a seguir gera um programa C que resolve o problema sem usar os operadores
* / + - %
:fonte
Usando a calculadora de números Delight Magic do Hacker
Onde fma é uma função de biblioteca padrão definida no
math.h
cabeçalho.fonte
-
nem o*
operador?Que tal essa abordagem (c #)?
fonte
Eu acho que a resposta certa é:
Por que eu não usaria um operador básico para fazer uma operação básica?
fonte
Solução usando a função de biblioteca fma () , funciona para qualquer número positivo:
Veja minha outra resposta .
fonte
Use cblas , incluído como parte da estrutura Accelerate do OS X.
fonte
Geralmente, uma solução para isso seria:
log(pow(exp(numerator),pow(denominator,-1)))
fonte
Primeiro:
Em seguida, descubra como resolver x / (1 - y):
com y = 1/4:
Embora ele use
+
, mas alguém já implementa add por bit a op.fonte