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


650


origen


Respuestas:


Esto es un función simple que realiza la operación deseada. Pero requiere el + operador, entonces 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 
  • So sum += a, n = a + be iterar

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


530



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, solo declare result como double y agregarle el resultado de fmod(number,divisor).

Explicación de cómo funciona

  1. los fwrite escribe number bytes (el número es 123456 en el ejemplo anterior).
  2. rewind restablece el puntero del archivo al frente del archivo.
  3. fread lee un máximo de number "registros" que son divisor en 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


429



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

304



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

199



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

111



Utilizar itoa para convertir a una base de 3 cuerdas. Suelta el último Trit y convertir de nuevo 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
}

102



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

Esto no es tan complicado como suena, porque dijiste "sin usar el [..] + [..] operadores". Consulte a continuación, si desea prohibir el uso de la + personaje 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;
}

entonces solo 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 un poco más rápida sin usar ningún operador que contenga el +,-,*,/,%  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 add función porque no podemos denotar el tipo de punteros sin usar el * carácter, excepto en las listas de parámetros de función, donde la sintaxis type[] es idéntico a type* const.

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

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

56



Es fácilmente posible en el Setun computadora.

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

Sin embargo, no estoy seguro de si es estrictamente posible implementar un compilador 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".


44



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 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 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 ha fallado 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 resuello de div_by_3(a) = x, luego x <= floor(f(a, i)) < a / 3. Cuando a = 3k, recibimos una respuesta incorrecta.


32