relacionales - sobrecarga de operadores c++

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

Éste es el algoritmo de división clásico en 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 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<<bit; // remove R bits from X if (r >= 3) y |= 1<<bit; // new output bit x |= mod3[r]<<bit; // new remainder inserted in X } printf("Y=%u/n",y); }

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

El número puede estar firmado o sin firmar.

¿Qué tal este enfoque (c #)?

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

¿Sería engañoso usar el operador / "detrás de escena" utilizando eval y concatenación de cadenas?

Por ejemplo, en Javacript, puedes hacer

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

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

En primer lugar, tenga en cuenta que

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

Ahora, el resto 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 sumar estos valores de bit desplazados de a! Ups! Sin embargo, no podemos agregar, así que, en lugar de eso, ¡tendremos que escribir una función de agregar usando operadores de bit bitwise! Si estás familiarizado con los operadores de bit bitwise, mi solución debería parecer bastante simple ... pero en caso de que no lo estés, veré un ejemplo al final.

Otra cosa a tener en cuenta es que primero me desplazo a la izquierda por 30! Esto es para asegurarse de que las fracciones no se redondean.

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 llevar además lo que aprendiste de 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.

Bueno, creo que todos estamos de acuerdo en que esto no es un problema del mundo real. Así que solo por diversión, aquí está 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;

Creo que la respuesta correcta es:

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

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

#!/usr/bin/env python3 print(''''''#include <stdint.h> #include <stdio.h> 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)); } '''''')

Es fácilmente posible en la computadora Setun .

Para dividir un entero por 3, gire a la derecha por 1 lugar .

Sin embargo, no estoy seguro de si es estrictamente posible implementar un compilador de C conforme a esta plataforma. Es posible que tengamos que estirar las reglas un poco, como interpretar "al menos 8 bits" como "capaz de mantener al menos enteros de -128 a +127".

Es realmente muy 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 programa por razones de brevedad.) Si el programador se cansa de escribir todo esto, estoy seguro de que podría escribir un programa separado para generárselo. Resulta que estoy al tanto de cierto operador, que simplificaría enormemente su trabajo.

Escribe el programa en Pascal y usa el operador DIV .

Dado que la pregunta está etiquetada c , probablemente puedas escribir una función en Pascal y llamarla desde tu programa 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 Free Pascal fp-compiler 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 <stdio.h> #include <stdlib.h> 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 la muestra:

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

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

Esto debería funcionar para cualquier divisor, no solo tres. Actualmente solo para los no firmados, pero extenderlo a firmado no debería ser tan 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) 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; }

La solución que utiliza la fma para cualquier número positivo:

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

Vea mi otra respuesta .

Las condiciones idiotas requieren una solución idiota:

#include <stdio.h> #include <stdlib.h> 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 double y agregue el resultado de fmod(number,divisor) .

Explicación de cómo funciona

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

Si escribe 30 bytes, luego vuelva a leer el archivo en unidades de 3, obtendrá 10 "unidades". 30/3 = 10

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

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

Otra solución más. Esto debería manejar todos los ints (incluidos los ints negativos) excepto el valor mínimo de un int, que debería manejarse como una excepción codificada. Básicamente, esto hace división por resta, pero solo utiliza operadores de bit (desplazamientos, xor, y y complemento). Para una velocidad más rápida, resta 3 * (potencias decrecientes de 2). En c #, ejecuta alrededor de 444 de estas llamadas DivideBy3 por milisegundo (2.2 segundos para 1,000,000 divisiones), por lo que no es terriblemente 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 con c deberían ser menores.

Para dividir un número de 32 bits por 3, se puede multiplicar 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 utilizando operaciones de bit y desplazamientos ...

Primero que se me haya ocurrido.

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

EDIT: Lo siento, no me di cuenta de la etiqueta C Pero puedes usar la idea sobre el formato de cadena, supongo ...

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

#include <stdio.h> 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; }

Usa itoa para convertir en una base de 3 cuerdas. Deja caer 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 }

Usando la calculadora de números de Hacker''s Delight Magic

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

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

Usando BC Math en PHP :

<?php $a = 12345; $b = bcdiv($a, 3); ?>

MySQL (es una entrevista de Oracle)

> SELECT 12345 DIV 3;

Pascal :

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

lenguaje de ensamblaje x86-64:

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

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, verifique los comentarios.

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

[02:31:59] [william@relativity ~]$ cat div3.c #import <stdio.h> #import <Accelerate/Accelerate.h> 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

Ya que es de Oracle, ¿qué tal una tabla de búsqueda de respuestas precalculadas? :-RE

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

(nota: ver Edición 2 a continuación para una mejor versión)

Esto no es tan complicado como parece, porque usted dijo "sin usar los operadores [..] + [..]". Vea a continuación, si desea prohibir el uso del carácter + a la vez.

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 simplemente diga div_by(100,3) para dividir 100 por 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 ligeramente más rápida sin utilizar 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[] sintaxis 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]); }

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

int div3(int x) { int reminder = abs(x); int result = 0; while(reminder >= 3) { result++; reminder--; reminder--; reminder--; } return result; }

log(pow(exp(number),0.33333333333333333333)) /* :-) */

relacionales - sobrecarga de operadores c++

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

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

Edición 2: versión ligeramente más rápida sin utilizar ningún operador que contenga los caracteres + , - , * , / , % .

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

Edición 2: versión ligeramente más rápida sin utilizar ningún operador que contenga los caracteres `+` , `-` , `*` , `/` , `%` .