¿Cómo te dividir un número entre 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

• Por lo tanto sum += a, n = a + by iterate

• 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 <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 declara resultcomo doubley agrégale el resultado de fmod(number,divisor).

Explicación de cómo funciona.

1. Los bytes de fwriteescritura number(el número es 123456 en el ejemplo anterior).
2. rewind restablece el puntero del archivo al frente del archivo.
3. freadlee un máximo de number"registros" que tienen una divisorlongitud del archivo y devuelve el número de elementos que lee.

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

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

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

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

Use itoa para convertir a una cadena de base 3. 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 Edición 2 a continuación para una mejor versión)

Esto no es tan complicado como parece, porque dijiste "sin usar los operadores [..] +[..] ". Vea a continuación, si desea prohibir el uso del 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 di div_by(100,3)dividir 100por 3.

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

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: Ligeramente más rápido versión sin necesidad de utilizar cualquier operador que contiene las +, -, *, /, % 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 addfunción porque no podemos denotar el tipo de punteros sin usar el *carácter, excepto en las listas de parámetros de funciones, donde la sintaxis type[]es idéntica type* const.

FWIW, puedes implementar fácilmente una función de multiplicación usando un truco similar para usar el 0x55555556truco 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 entre 3, cambie a la derecha por 1 lugar .

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

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

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 desplazados de bits de a! ¡Uy! Sin embargo, no podemos agregar, así que en su lugar, tendremos que escribir una función de agregar usando operadores de bits. Si está familiarizado con los operadores en cuanto a bits, mi solución debería parecer bastante simple ... pero en caso de que no lo esté, le explicaré un ejemplo al final.

¡Otra cosa a tener en cuenta es que primero cambio 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 una adición 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 resultado de div_by_3(a)= x, entonces x <= floor(f(a, i)) < a / 3. Cuando a = 3k, recibimos una respuesta incorrecta.

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

Otra solución más. Esto debería manejar todas las entradas (incluidas las entradas negativas) excepto el valor mínimo de un int, que debería manejarse como una excepción codificada. Básicamente, esto hace la división por sustracción, pero solo usa operadores de bits (desplazamientos, xor y &). 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 de 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 respecto a 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 programa en aras de la brevedad). Si el programador se cansa de escribir todo esto, estoy seguro de que él o ella podría escribir un programa separado para generarlo para él. Estoy al tanto de un cierto operador /que simplificaría enormemente 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, verifique los comentarios.

Este es el algoritmo de división clásica en la 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);
}

Escriba el programa en Pascal y use el DIVoperador.

Como la pregunta está etiquetada C, probablemente pueda escribir una función en Pascal y llamarla desde su 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 fp-compilerpaquete 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 <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 muestra:

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

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

     reminder--;
     reminder--;
     reminder--;
  }
  return result;
}

No verifiqué si esta respuesta ya está publicada. Si el programa necesita extenderse a números flotantes, los números se pueden multiplicar por 10 * número de precisión necesaria y luego se puede aplicar nuevamente 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;
}

Esto debería funcionar para cualquier divisor, no solo para tres. Actualmente solo para 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;
}

¿Sería una trampa usar el /operador "detrás de escena" usando evaluna concatenación de cadenas?

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 :

<?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 ensamblador x86-64:

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

Primero lo que se me ocurrió.

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

EDITAR: Lo siento, no noté la etiqueta C. Pero puedes usar la idea sobre el formato de cadenas, supongo ...

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

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 el math.hencabezado.

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

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 usa la función de biblioteca fma () funciona 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);
}

Mira mi otra respuesta .

Use cblas , incluido como parte del marco Acelerar 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

En general, una solución a esto sería:

log(pow(exp(numerator),pow(denominator,-1)))

Primero:

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

Luego descubra 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.