Divida un número por 3 sin usar los operadores *, /, +, -,%

¿Cómo dividirías un número por 3 sin usar operadores * , / , + , - , % ?

El número puede estar firmado o sin firmar.

Esta es una función simple que realiza la operación deseada. Pero requiere el operador + , por lo que todo lo que queda por hacer es agregar los valores con operadores de bits:

 // replaces the + operator int 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 comentó, esto funciona, porque:

  • n = 4 * a + b
  • n / 3 = a + (a + b) / 3
  • Entonces sum += a , n = a + b , e itera

  • Cuando a == 0 (n < 4) , sum += floor(n / 3); es decir, 1, if n == 3, else 0

Las condiciones idiotas requieren una solución idiota:

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

Si también se necesita la parte decimal, simplemente declare el result como el double y añádale el resultado de fmod(number,divisor) .

Explicación de cómo funciona

  1. El fwrite escribe bytes de number (el número es 123456 en el ejemplo anterior).
  2. rewind restablece el puntero del archivo al frente del archivo.
  3. fread lee un number máximo de “registros” number que tienen divisor de longitud desde el archivo y devuelve la cantidad de elementos que leyó.

Si escribe 30 bytes y vuelve a leer el archivo en unidades de 3, obtendrá 10 “unidades”. 30/3 = 10

 log(pow(exp(number),0.33333333333333333333)) /* :-) */ 
 #include  #include  int main(int argc, char *argv[]) { int num = 1234567; int den = 3; div_t r = div(num,den); // div() is a standard C function. printf("%d\n", r.quot); return 0; } 

Puede usar el ensamblaje en línea (dependiente de la plataforma), por ejemplo, para x86: (también funciona para números negativos)

 #include  int main() { int dividend = -42, divisor = 5, quotient, remainder; __asm__ ( "cdq; idivl %%ebx;" : "=a" (quotient), "=d" (remainder) : "a" (dividend), "b" (divisor) : ); printf("%i / %i = %i, remainder: %i\n", dividend, divisor, quotient, remainder); return 0; } 

Use itoa para convertir a una cadena de 3 bases. Suelta el último trit y vuelve a convertir a la 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 digit return strtol(str, NULL, 3); // Read back result } 

(nota: vea Editar 2 a continuación para una mejor versión!)

Esto no es tan complicado como suena, porque dijiste “sin usar los operadores [..] + [..]”. Vea a continuación, si desea prohibir el uso del carácter + todos juntos.

 unsigned div_by(unsigned const x, unsigned const 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; } 

luego solo di div_by(100,3) para dividir 100 entre 3 .


Editar : Puedes continuar y reemplazar el operador ++ también:

 unsigned inc(unsigned x) { for (unsigned mask = 1; mask; mask <<= 1) { if (mask & x) x &= ~mask; else return x & mask; } return 0; // overflow (note that both x and mask are 0 here) } 

Edición 2: Versión un poco más rápida sin usar ningún operador que contenga los caracteres + , - , * , / , % .

 unsigned add(char const zero[], unsigned const x, unsigned const y) { // this exploits that &foo[bar] == foo+bar if foo is of type char* return (int)(uintptr_t)(&((&zero[x])[y])); } unsigned div_by(unsigned const x, unsigned const 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 el primer argumento de la función de add porque no podemos denotar el tipo de punteros sin usar el carácter * , excepto en las listas de parámetros de función, donde el type[] syntax type[] es idéntico al type* const .

FWIW, puedes implementar fácilmente una función de multiplicación usando un truco similar para usar el truco 0x55555556 propuesto por AndreyT :

 int mul(int const x, int const y) { return sizeof(struct { char const ignore[y]; }[x]); } 

Es fácilmente posible en la computadora Setun .

Para dividir un número entero por 3, cambia a la derecha por 1 lugar .

Sin embargo, no estoy seguro de si es estrictamente posible implementar un comstackdor de C conforme en una plataforma de este tipo. Podríamos tener que estirar las reglas un poco, como interpretar “al menos 8 bits” como “capaz de contener al menos enteros de -128 a +127”.

Aquí está mi solución:

 public static int div_by_3(long a) { a <<= 30; for(int i = 2; i <= 32 ; i <<= 1) { a = add(a, a >> i); } return (int) (a >> 32); } public static long add(long a, long b) { long carry = (a & b) << 1; long sum = (a ^ b); return carry == 0 ? sum : add(carry, sum); } 

Primero, tenga en cuenta que

 1/3 = 1/4 + 1/16 + 1/64 + ... 

¡Ahora, el rest es simple!

 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 + ... 

¡Ahora todo lo que tenemos que hacer es sumr estos valores de bit shift de a! Oops! Sin embargo, no podemos agregar, así que en su lugar, tendremos que escribir una función de agregar utilizando operadores de bits. Si está familiarizado con operadores bit a bit, mi solución debería ser bastante simple ... pero, por si acaso no lo está, le daré un ejemplo al final.

Otra cosa a tener en cuenta es que primero cambié a la izquierda por 30! Esto es para asegurarse de que las fracciones no se redondeen.

 11 + 6 1011 + 0110 sum = 1011 ^ 0110 = 1101 carry = (1011 & 0110) << 1 = 0010 << 1 = 0100 Now you recurse! 1101 + 0100 sum = 1101 ^ 0100 = 1001 carry = (1101 & 0100) << 1 = 0100 << 1 = 1000 Again! 1001 + 1000 sum = 1001 ^ 1000 = 0001 carry = (1001 & 1000) << 1 = 1000 << 1 = 10000 One last time! 0001 + 10000 sum = 0001 ^ 10000 = 10001 = 17 carry = (0001 & 10000) << 1 = 0 Done! 

¡Es simplemente un complemento que aprendiste cuando eras niño!

 111 1011 +0110 ----- 10001 

Esta implementación falló porque no podemos agregar todos los términos de la ecuación:

 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 

Supongamos que el reslut de div_by_3(a) = x, entonces x <= floor(f(a, i)) < a / 3 . Cuando a = 3k , obtenemos una respuesta incorrecta.

Dado que es de Oracle, ¿qué tal una tabla de búsqueda de respuestas pre calculadas? :-RE

Para dividir un número de 32 bits por 3 uno puede multiplicarlo por 0x55555556 y luego tomar los 32 bits superiores del resultado de 64 bits.

Ahora todo lo que queda por hacer es implementar la multiplicación usando operaciones de bits y cambios …

Otra solución más Esto debería manejar todas las entradas (incluidas las entradas negativas), excepto el valor mínimo de una int, que debería manejarse como una excepción codificada. Esto básicamente hace división por sustracción, pero solo usa operadores de bits (cambios, xor, & y complemento). Para una velocidad más rápida, resta 3 * (poderes decrecientes de 2). En c #, se ejecutan alrededor de 444 de estas llamadas DivideBy3 por milisegundo (2.2 segundos para 1,000,000 de divisiones), por lo que no es tremendamente lento, pero no tan rápido como un simple x / 3. En comparación, la buena solución de Coodey es aproximadamente 5 veces más rápida que esta.

 public static int DivideBy3(int a) { bool negative = a < 0; if (negative) a = Negate(a); int result; int sub = 3 << 29; int threes = 1 << 29; result = 0; while (threes > 0) { if (a >= sub) { a = Add(a, Negate(sub)); result = Add(result, threes); } sub >>= 1; threes >>= 1; } if (negative) result = Negate(result); return result; } public static int Negate(int a) { return Add(~a, 1); } public static int Add(int a, int b) { int x = 0; x = a ^ b; while ((a & b) != 0) { b = (a & b) << 1; a = x; x = a ^ b; } return x; } 

Esto es c # porque eso es lo que tenía a mano, pero las diferencias de c deberían ser menores.

Es realmente bastante fácil.

 if (number == 0) return 0; if (number == 1) return 0; if (number == 2) return 0; if (number == 3) return 1; if (number == 4) return 1; if (number == 5) return 1; if (number == 6) return 2; 

(Por supuesto, he omitido parte del progtwig en aras de la brevedad.) Si el progtwigdor se cansa de escribir todo esto, estoy seguro de que podría escribir un progtwig por separado para generarlo para él. Resulta que estoy al tanto de cierto operador, / , que simplificaría inmensamente su trabajo.

Usar contadores es una solución básica:

 int DivBy3(int num) { int result = 0; int counter = 0; while (1) { if (num == counter) //Modulus 0 return result; counter = abs(~counter); //++counter if (num == counter) //Modulus 1 return result; counter = abs(~counter); //++counter if (num == counter) //Modulus 2 return result; counter = abs(~counter); //++counter result = abs(~result); //++result } } 

También es fácil realizar una función de módulo, verificar los comentarios.

Este es el algoritmo de división clásico en la base 2:

 #include  #include  int main() { uint32_t mod3[6] = { 0,1,2,0,1,2 }; uint32_t x = 1234567; // number to divide, and remainder at the end uint32_t y = 0; // result int bit = 31; // current bit printf("X=%u X/3=%u\n",x,x/3); // the '/3' is for testing while (bit>0) { printf("BIT=%d X=%u Y=%u\n",bit,x,y); // decrement bit int h = 1; while (1) { bit ^= h; if ( bit&h ) h <<= 1; else break; } uint32_t r = x>>bit; // current remainder in 0..5 x ^= r<= 3) y |= 1< 
 int div3(int x) { int reminder = abs(x); int result = 0; while(reminder >= 3) { result++; reminder--; reminder--; reminder--; } return result; } 

Escriba el progtwig en Pascal y use el operador DIV .

Como la pregunta está etiquetada c , probablemente pueda escribir una función en Pascal y llamarla desde su progtwig C; el método para hacerlo es específico del sistema.

Pero aquí hay un ejemplo que funciona en mi sistema Ubuntu con el paquete de fp-compiler Free Pascal instalado. (Estoy haciendo esto por pura terquedad fuera de lugar, no pretendo que esto sea ú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  #include  extern int div_by_3(int n); int main(void) { int n; fputs("Enter a number: ", stdout); fflush(stdout); scanf("%d", &n); printf("%d / 3 = %d\n", n, div_by_3(n)); return 0; } 

Para construir:

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

Ejecución de muestra:

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

No verificó si esta respuesta ya está publicada. Si el progtwig necesita extenderse a números flotantes, los números se pueden multiplicar por 10 * cantidad de precisión necesaria y luego se puede aplicar el siguiente código.

 #include  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); return 0; } 

Esto debería funcionar para cualquier divisor, no solo para tres. Actualmente solo para unsigned, pero extenderlo para firmar no debería ser tan difícil.

 #include  unsigned sub(unsigned two, unsigned one); unsigned bitdiv(unsigned top, unsigned bot); unsigned sub(unsigned two, unsigned one) { unsigned bor; bor = one; do { one = ~two & bor; two ^= bor; bor = one<<1; } while (one); return two; } unsigned bitdiv(unsigned top, unsigned bot) { unsigned result, shift; if (!bot || top < bot) return 0; for(shift=1;top >= (bot<<=1); shift++) {;} bot >>= 1; for (result=0; shift--; bot >>= 1 ) { result <<=1; if (top >= bot) { top = sub(top,bot); result |= 1; } } return result; } int main(void) { unsigned arg,val; for (arg=2; arg < 40; arg++) { val = bitdiv(arg,3); printf("Arg=%u Val=%u\n", arg, val); } return 0; } 

¿Sería una trampa usar el / operador “detrás de escena” mediante el uso de la concatenación eval y string?

Por ejemplo, en Javacript, puedes hacer

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

Usando BC Math en PHP :

  

MySQL (es una entrevista de Oracle)

 > SELECT 12345 DIV 3; 

Pascal :

 a:= 12345; b:= a div 3; 

lenguaje ensamblador x86-64:

 mov r8, 3 xor rdx, rdx mov rax, 12345 idiv r8 

Primero que me he presentado.

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

EDITAR: Perdón, no noté la etiqueta C Pero puede usar la idea sobre el formato de cadenas, supongo …

El siguiente script genera un progtwig C que resuelve el problema sin usar los operadores * / + - % :

 #!/usr/bin/env python3 print('''#include  #include  const int32_t div_by_3(const int32_t input) { ''') for i in range(-2**31, 2**31): print(' if(input == %d) return %d;' % (i, i / 3)) print(r''' return 42; // impossible } int main() { const int32_t number = 8; printf("%d / 3 = %d\n", number, div_by_3(number)); } ''') 

Usando Hacker’s Delight Calculadora de números mágicos

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

Donde fma es una función de biblioteca estándar definida en el encabezado math.h

¿Qué tal este enfoque (c #)?

 private int dividedBy3(int n) { List a = new Object[n].ToList(); List b = new List(); while (a.Count > 2) { a.RemoveRange(0, 3); b.Add(new Object()); } return b.Count; } 

Creo que la respuesta correcta es:

¿Por qué no usaría un operador básico para hacer una operación básica?

La solución que utiliza la función de biblioteca fma () funciona para cualquier número positivo:

 #include  #include  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); } 

Ver mi otra respuesta .

Use cblas , incluido como parte del marco Accelerate de OS X.

 [02:31:59] [william@relativity ~]$ cat div3.c #import  #import  int main() { float multiplicand = 123456.0; float multiplier = 0.333333; printf("%f * %f == ", multiplicand, multiplier); cblas_sscal(1, multiplier, &multiplicand, 1); printf("%f\n", multiplicand); } [02:32:07] [william@relativity ~]$ clang div3.c -framework Accelerate -o div3 && ./div3 123456.000000 * 0.333333 == 41151.957031 

primero:

 x/3 = (x/4) / (1-1/4) 

luego averigua cómo resolver 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)) 

con 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) } 

aunque usa + , pero alguien ya implementa add by bitwise op

De acuerdo, creo que todos estamos de acuerdo en que este no es un problema del mundo real. Así que solo por diversión, así es cómo hacerlo con Ada y multihilo:

 with Ada.Text_IO; procedure Divide_By_3 is protected type Divisor_Type is entry Poke; entry Finish; private entry Release; entry Stop_Emptying; Emptying : Boolean := False; end Divisor_Type; protected type Collector_Type is entry Poke; entry Finish; private Emptying : Boolean := False; end Collector_Type; task type Input is end Input; task type Output is end Output; protected body Divisor_Type is entry Poke when not Emptying and Stop_Emptying'Count = 0 is begin requeue Release; end Poke; entry Release when Release'Count >= 3 or Emptying is New_Output : access Output; begin if not Emptying then New_Output := new Output; Emptying := True; requeue Stop_Emptying; end if; end Release; entry Stop_Emptying when Release'Count = 0 is begin Emptying := False; end Stop_Emptying; entry Finish when Poke'Count = 0 and Release'Count < 3 is begin Emptying := True; requeue Stop_Emptying; end Finish; end Divisor_Type; protected body Collector_Type is entry Poke when Emptying is begin null; end Poke; entry Finish when True is begin Ada.Text_IO.Put_Line (Poke'Count'Img); Emptying := True; end Finish; end Collector_Type; Collector : Collector_Type; Divisor : Divisor_Type; task body Input is begin Divisor.Poke; end Input; task body Output is begin Collector.Poke; end Output; Cur_Input : access Input; -- Input value: Number : Integer := 18; begin for I in 1 .. Number loop Cur_Input := new Input; end loop; Divisor.Finish; Collector.Finish; end Divide_By_3;