¿Cómo escribir un programa en C para la multiplicación sin usar los operadores * y +?

68

¿Es posible escribir un programa en C que multiplique dos números sin usar los operadores de multiplicación y suma?

Encontré esto en Stack Overflow . Por favor, ayuda a este pobre programador con su problema. Y por favor no dé respuestas como c = a/(1/((float)b)), que es exactamente lo mismo que c = a*b. (Y ya se da como respuesta).

La respuesta con más votos a favor el 19 de enero de 2014 gana.

Nota: Esta es una pregunta de . No tome en serio la pregunta y / o las respuestas. Más información está en código trolling .

s3lph
fuente
2
@PaulR usa tu fantasía
John Dvorak
26
Code-golf.SE no debería ser un lugar para burlarse de las preguntas que ha visto en StackOverflow.
Gareth el
17
@Gareth, ¿estás seguro? La primera línea de esto sugiere que esto puede ser bastante apropiado.
Darren Stone el
55
Estoy esperando que alguien escriba un algoritmo basado en el sueño
kb_sou
21
Esta pregunta no es tan ridícula como parece. El hardware real de la computadora (transistores) no tiene operaciones de multiplicar y agregar: tienen operaciones lógicas básicas como NOT, AND, OR, XOR. Descubrir cómo responder a esta pregunta puede brindarle una excelente visión de cómo funciona realmente una computadora en el nivel de las puertas lógicas.
Gabe

Respuestas:

147

Siempre usa la recursividad

Recusion es la forma correcta!

int inc(int x) {
    return x&1?inc(x>>1)<<1:x|1;
}

int dec(int x) {
    return x&1?x^1:dec(x>>1)<<1|1;
}

int add(int x, int y) {
    return x?add(dec(x),inc(y)):y;
}

int mul(int x, int y) {
    return x?x^1?add(y,mul(dec(x),y)):y:0;
}

int main() {
    int a, b;
    scanf("%i\n%i", &a, &b);
    printf("%i", mul(a,b));
}
Oberon
fuente
8
Daría +3 si pudiera: uno para la última recursión, uno para ??::sin paréntesis, uno para resolver el problema sin tratar de modificar las reglas;)
yo
10
Si Picasso fuera un programador ...
R Hughes
44
@SargeBorsch Pero, ¿dónde estaría la diversión en eso ?
Oberon
3
@HC_ La incfunción prueba su argumento para ver si el bit más bajo es 1; si es así, se llama a sí mismo en los bits superiores restantes del argumento y devuelve el resultado con el mismo bit bajo que se verificó establecido 0, mientras que si no (es decir, el bit más bajo es 0), reemplaza eso 0con 1ay devuelve el resultado . El proceso es muy similar a lo que haría si estuviera agregando los valores a mano, dígito binario por dígito binario.
JAB
2
¿La función de incremento no entra en un bucle infinito para -1? (0xFFFF) ideone muestra (-1 >> 1) == -1.
Destrictor
87

Tendrá que compilar el programa cada vez, pero multiplica todos los enteros positivos exactamente en cualquier versión de C o C ++.

 #define A 45  // first number
 #define B 315 // second number

 typedef char buffer[A][B];

 main() {
    printf("%d\n",sizeof(buffer));
 }
Mark Lakata
fuente
44
Ponlo dentro de una estructura y no necesitas memoria.
Ben Jackson
44
Jajajaja genial !!
Almo
1
usar "%zu"cadena de formato.
Grijesh Chauhan
55
simplemente sizeof(char[A][B])funcionará (a menos que A <= 0 o B <= 0 o A * B se desborde, en cuyo caso debería obtener un tipo de error de 'tipo malo')
greggo
3
@DavidRicherby - Podría simplificar el código main(){return sizeof(char[A][B]);}y compilarlo usandocc -DA=6 -DB=7 a.c; ./a.out; echo $?
Mark Lakata
47

Si está de acuerdo con un poco de imprecisión, puede usar el método Monte Carlo :

#include <stdlib.h>
#include <stdio.h>

unsigned int mul(unsigned short a, unsigned short b) {
  const int totalBits = 24;
  const int total = (1 << totalBits);
  const int maxNumBits = 10;
  const int mask = (1 << maxNumBits) - 1;
  int count = 0, i;
  unsigned short x, y;
  for(i = 0; i < total; i++) {
    x = random() & mask;
    y = random() & mask;
    if ((x < a) && (y < b))
      count++;
  }
  return ((long)count) >> (totalBits - (maxNumBits << 1));
}

void main(int argc, char *argv[]) {
  unsigned short a = atoi(argv[1]);
  unsigned short b = atoi(argv[2]);
  printf("%hd * %hd = %d\n", a, b, mul(a, b));
}

Ejemplo:

$ ./mul 300 250
300 * 250 = 74954

Supongo que esto podría ser lo suficientemente bueno;)

Petr Pudlák
fuente
3
Tienes mi voto positivo. Escuché que Monte Carlo es lo que la NASA usa para su aritmética. Pero me gustaría ver esto sin las dos instancias del ++operador.
Darren Stone el
1
@DarrenStone-= -1
Timtech
20
@Timtech |= 1(funcionará en el 50% de los números, el 100% del tiempo)
Darren Stone
2
+1, pero observando que podría ser demasiado lento, y podría agregar soporte multihilo, bloqueando cuidadosamente el 'conteo ++' :-)
greggo
1
Siempre hay un printfincremento: printf("%*cc%n\n", count, &count, 'c');(Imprime 'c' veces, luego otra 'c', y almacena el número de caracteres escritos nuevamente count.
MSalters
45

Como no especificó qué tamaño de número, supongo que se refiere a dos números de un bit.

#include <stdbool.h>
bool mul(bool a, bool b) {
    if (a && b) {
        return true;
    } else {
        return false;
    }
}

Si desea una implementación de máxima eficiencia, use la siguiente implementación pequeña:

m(a,b){return a&b;}

Tenga en cuenta que todavía solo acepta bits aunque los tipos son ints implícitos: requiere menos código y, por lo tanto, es más eficiente. (Y sí, se compila).

Cel Skeggs
fuente
8
Agradable. Una mala interpretación deliberada de la pregunta :-)
John Dvorak
66
Puede optimizar esto para return a && b;. Es más corto, por lo que es más rápido.
Ry-
1
@minitech: decidí no hacerlo para empeorar un poco el código. Si quisiera ir más allá con eso, lo lograría return a&b;.
Cel Skeggs
1
C tiene #include<stdbool.h>que definir truey false.
leewz
1
Sí, #include<stdbool.h>parece ser sólo tres #defines que usted puede hacer usted mismo ( true, false, bool, y una bandera para señalar que ha sido activada). También puede tomar un truco de una de las otras respuestas y usarlo implícito intpara la versión "corta".
leewz
31

Aquí hay un script de shell simple para hacerlo:

curl "http://www.bing.com/search?q=$1%2A$2&go=&qs=n&form=QBLH&pq=$1%2A$2" -s \
| sed -e "s/[<>]/\n/g" \
| grep "^[0-9 *]*=[0-9 ]*$"

ACTUALIZACIÓN: Por supuesto, para hacerlo en C, solo envuélvelo exec("bash", "-c", ...). (Gracias, AmeliaBR)

Vroo
fuente
41
No puedo decidir cuál es más horrible. Que está subcontratando su cálculo a un motor de búsqueda, o que su motor de búsqueda elegido es Bing. Desafortunadamente, no creo que esto funcione para nuestro OP desventurado, que necesitaba algo en C.
AmeliaBR
55
Gracias por atrapar ese descuido. Para su información, estoy usando Bing porque Google hace que sea más complicado emitir solicitudes como esta: debe agregar encabezados para convencer a Google de que su solicitud realmente proviene de un navegador.
Vroo
2
@abarnert hmm ... ¿Bing entiende los "tiempos"? Sin embargo, Wolfram Alpha podría.
John Dvorak
2
@ JanDvorak: Sí, Wolfram funciona. (Tenga en cuenta que %20para evitar el uso de +signos). Pero aún necesita analizar la salida (en C) para obtener el valor. Lo cual será especialmente complicado, ya que el resultado parece ser una imagen, no un texto. El análisis de HTML más OCR podría ser la mejor respuesta posible a este problema.
abarnert
3
@ JanDvorak: Eso no es divertido.
Esperaba
27

¡Por qué, hagamos una búsqueda a la mitad recursiva entre INT64_MIN e INT64_MAX!

#include <stdio.h>
#include <stdint.h>

int64_t mul_finder(int32_t a, int32_t b, int64_t low, int64_t high)
{
    int64_t result = (low - (0 - high)) / 2;
    if (result / a == b && result % a == 0)
        return result;
    else
        return result / a < b ?
            mul_finder(a, b, result, high) :
            mul_finder(a, b, low, result);
}

int64_t mul(int32_t a, int32_t b)
{
    return a == 0 ? 0 : mul_finder(a, b, INT64_MIN, INT64_MAX);
}

void main(int argc, char* argv[])
{
    int32_t a, b;
    sscanf(argv[1], "%d", &a);
    sscanf(argv[2], "%d", &b);
    printf("%d * %d = %ld\n", a, b, mul(a, b));
}

PD: felizmente firmará con algunos valores. ;)

treamur
fuente
18

Desafortunadamente, esto solo funciona para enteros.

Como la adición no está permitida, creemos primero un operador de incremento:

int plusOne(int arg){
  int onMask = 1;
  int offMask = -1;
  while (arg & onMask){
    onMask <<= 1;
    offMask <<= 1;
  }
  return(arg & offMask | onMask);
}

A continuación, tenemos que manejar la señal. Primero, encuentre el bit de signo:

int signBit = -1;
while(signBit << 1) signBit <<=1;

Luego tome el signo y la magnitud de cada argumento. Para negar un número en el complemento de dos, invierta todos los bits y agregue uno.

int signA = a & signBit;
if(signA) a = plusOne(-1 ^ a);
int signB = b & signBit;
if(signB) b = plusOne(-1 ^ b);
int signRes = signA ^ signB;

Para multiplicar dos enteros positivos, podemos usar el significado geométrico de la multiplicación:

// 3x4
//
// ooo
// ooo
// ooo
// ooo

int res = 0;
for(int i = 0; i < a; i = plusOne(i))
  for(int j = 1; j < b; j = plusOne(j))
    res = plusOne(res);

if(signRes) res = plusOne(-1 ^ res);

trolls:

  • La adición no está permitida, pero ¿ a++realmente cuenta como adición? Apuesto a que el maestro tenía la intención de permitirlo.
  • Se basa en el complemento de dos, pero ese es un comportamiento definido por la implementación y no se especificó la plataforma de destino.
  • Del mismo modo, asume que la resta y la división también están prohibidas.
  • << es en realidad la multiplicación por una potencia de dos, por lo que técnicamente no se debe permitir.
  • diagrama innecesario es innecesario. Además, podría haberse transpuesto para guardar una línea.
  • El desplazamiento repetido de -1no es la mejor manera de encontrar el bit de signo. Incluso si no hubiera una constante incorporada, podría hacer un cambio lógico a la derecha de -1 y luego invertir todos los bits.
  • XOR -1 no es la mejor manera de invertir todos los bits.
  • Toda la farsa con representación de magnitud de signo es innecesaria. Solo enviar a aritmética modular y sin signo hará el resto.
  • Como el valor absoluto de MIN_INT(AKA signBit) es negativo, esto se rompe para ese valor. Afortunadamente, todavía funciona en la mitad de los casos, porque MIN_INT * [even number] debería ser cero.Además, se plusOnerompe para -1causar bucles infinitos cada vez que el resultado se desborda. plusOnefunciona bien para cualquier valor. Perdón por la confusion.
John Dvorak
fuente
+1 para un troll de código real: Parece que debería funcionar, pero es muy probable que explote en el OP y no tendrá idea de por qué.
Kevin
1
Es posible hacer sumas sin CUALQUIER operador de sumas simplemente usando shift, XOR y AND. Todos estos ++ están haciendo que me duela la cabeza: ADD de un solo bit con carry es (x ^ y) | ((x & y) << 1) (modifique cualquier error causado por escribir en este pequeño cuadro de texto).
Julie en Austin el
@JulieinAustin sí. El algoritmo es aún más ineficiente de lo que debe ser. ¿Debo modificar la lista de trolls? :-)
John Dvorak
1
@JulieinAustin (x ^ y) | ((x & y) << 1)no funciona del todo, no propagará carry cuando x o y y carry sean verdaderas en la misma posición :)
hobbs
Solución @hobbs: en lugar de ORing, agréguelos recursivamente si carry no es cero.
John Dvorak
14

Funciona también para números de coma flotante:

float mul(float a, float b){
  return std::exp(std::log(a) - std::log(1.0 / b));
}
nbubis
fuente
11

Todo el mundo sabe que Python es más fácil de usar que C. Y Python tiene funciones correspondientes a cada operador, en los casos en que no puede usar el operador. ¿Cuál es exactamente nuestra definición del problema, verdad? Entonces:

#include <Python.h>

void multiply(int a, int b) {
    PyObject *operator_name, *operator, *mul, *pa, *pb, *args, *result;
    int result;

    operator_name = PyString_FromString("operator");
    operator = PyImport_Import(operator_name);
    Py_DECREF(operator_name);
    mul = PyObject_GetAttrString(operator, "__mul__");
    pa = PyLong_FromLong((long)a);
    pb = PyLong_FromLong((long)b);
    args = PyTuple_New(2);
    PyTuple_SetItem(args, 0, pa);
    PyTuple_SetItem(args, 1, pb);
    presult = PyObject_CallObject(mul, args);
    Py_DECREF(args);
    Py_DECREF(mul);
    Py_DECREF(operator);
    result = (int)PyLong_AsLong(presult);
    Py_DECREF(presult);
    return result;
}

int main(int argc, char *argv[]) {
    int c;
    Py_Initialize();
    c = multiply(2, 3);
    printf("2 * 3 = %d\n", c);
    Py_Finalize();
}
abarnert
fuente
10

Ninguna de las otras respuestas es teóricamente sólida. Como dice el primer comentario sobre la pregunta:

Por favor sea más específico sobre "números"

Necesitamos definir la multiplicación y los números, incluso antes de que sea posible una respuesta. Una vez que lo hacemos, el problema se vuelve trivial.

La forma más popular de hacer esto al comenzar la lógica matemática es construir ordinales de von Neumann sobre la teoría de conjuntos ZF , y luego usar los axiomas de Peano .

Esto se traduce naturalmente en C, suponiendo que tenga un tipo de conjunto que pueda contener otros conjuntos. No tiene que contener nada más que conjuntos, lo que lo hace trivial (nada de eso void*sin sentido en la mayoría de las bibliotecas de conjuntos), por lo que dejaré la implementación como un ejercicio para el lector.

Entonces, primero:

/* The empty set is 0. */
set_t zero() {
    return set_new();
}

/* The successor of n is n U {n}. */
set_t successor(set_t n) {
    set_t result = set_copy(n);
    set_t set_of_n = set_new();
    set_add(set_of_n, n);
    set_union(result, set_of_n);
    set_free(set_of_n);
    return result;
}

/* It is an error to call this on 0, which will be reported by
   running out of memory. */
set_t predecessor(set_t n) {
    set_t pred = zero();
    while (1) {
        set_t next = successor(pred);
        if (set_equal(next, n)) {
            set_free(next);
            return pred;
        }
        set_free(pred);
    }
}        

set_t add(set_t a, set_t b) {
    if (set_empty(b)) {
        /* a + 0 = a */
        return a;
    } else {
        /* a + successor(b) = successor(a+b) */
        set_t pred_b = predecessor(b)
        set_t pred_ab = add(a, pred_b);
        set_t result = successor(pred_ab);
        set_free(pred_b);
        set_free(pred_ab);
        return result;
    }
}

set_t multiply(set_t a, set_t b) {
    if (set_empty(b)) {
        /* a * 0 = 0 */
        return b;
    } else {
        /* a * successor(b) = a + (a * b) */
        set_t pred_b = predecessor(b)
        set_t pred_ab = mul(a, pred_b);
        set_t result = successor(pred_ab);
        set_free(pred_b);
        set_free(pred_ab);
        return result;
    }
}

Si desea expandir esto a enteros, racionales, reales, surrealistas, etc., puede arrancar con una precisión infinita (suponiendo que tenga memoria y CPU infinitas). Pero como dijo Kroenecker, Dios hizo los números naturales; todo lo demás es obra del hombre, así que realmente, ¿por qué molestarse?

abarnert
fuente
1
Guau. Eres incluso más lento que yo.
John Dvorak
10
unsigned add( unsigned a, unsigned b )
{
    return (unsigned)&((char*)a)[b];  // ignore compiler warnings
       // (if pointers are bigger than unsigned). it still works.
}
unsigned umul( unsigned a, unsigned b )
{
    unsigned res = 0;
    while( a != 0 ){
        if( a & 1) res = add( res, b );
        b <<= 1;
        a >>= 1;
    }
    return res;
}

int mul( int a, int b ){
    return (int)umul( (unsigned)a, (unsigned)b );
}

Si considera que el truco a [b] es una trampa (ya que es realmente un complemento), entonces esto funciona en su lugar. Pero las búsquedas de tablas también incluyen punteros añadidos.

Ver http://en.wikipedia.org/wiki/IBM_1620 , una computadora que realmente hizo la suma usando tablas de búsqueda ...

Algo satisfactorio sobre el uso de un mecanismo de tabla para 'acelerar' una operación que en realidad podría hacerse en una sola instrucción.

static unsigned sumtab[17][16]= {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15},
{ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16},
{ 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17},
{ 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18},
{ 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19},
{ 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20},
{ 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21},
{ 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22},
{ 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23},
{ 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24},
{10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25},
{11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26},
{12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27},
{13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28},
{14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29},
{15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30},
{16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}
};

unsigned add( unsigned a, unsigned b )
{
   static const int add4hack[8] =  {4,8,12,16,20,24,28,32};
   unsigned carry = 0;
   unsigned (*sumtab0)[16] = &sumtab[0];
   unsigned (*sumtab1)[16] = &sumtab[1];
   unsigned result = 0;
   int nshift = 0;
   while( (a|b) != 0 ){
      unsigned psum = (carry?sumtab1:sumtab0)[ a & 0xF ][ b & 0xF ];
      result = result | ((psum & 0xF)<<nshift);
      carry = psum >> 4;
      a = a >> 4
      b = b >> 4;
      nshift= add4hack[nshift>>2];  // add 4 to nshift.
   }
   return result;
}
Greggo
fuente
Vaya, hay *char (aunque no es multiplicación)
Sarge Borsch
Uh, la búsqueda de tablas usa la suma - (a [i]) es lo mismo que (* (a + i)).
Julie en Austin el
@JulieinAustin Lo mencioné. La búsqueda de la tabla se puede hacer sin agregar, combinando campos (como se ilustra en el IBM 1620, vea el enlace), pero es complicado configurarlo en C: por una cosa, debe alinear la tabla a una dirección adecuada para que los índices puedan ser Just or'd in.
Greg
8

No estoy seguro de qué constituye "trampa" en estas publicaciones de "código troll", pero esto multiplica 2 enteros arbitrarios, en tiempo de ejecución, sin operador *o +utilizando bibliotecas estándar (C99).

#include <math.h>
main()
{
  int a = 6;
  int b = 7;
  return fma(a,b,0);
}
Mark Lakata
fuente
8

Mi solución troll para unsigned int:

#include<stdio.h>

unsigned int add(unsigned int x, unsigned int y)
{
  /* An addition of one bit corresponds to the both following logical operations
     for bit result and carry:
        r     = x xor y xor c_in
        c_out = (x and y) or (x and c_in) or (y and c_in)
     However, since we dealing not with bits but words, we have to loop till
     the carry word is stable
  */
  unsigned int t,c=0;
  do {
    t = c;
    c = (x & y) | (x & c) | (y & c);
    c <<= 1;
  } while (c!=t);
  return x^y^c;
}

unsigned int mult(unsigned int x,unsigned int y)
{
  /* Paper and pencil method for binary positional notation:
     multiply a factor by one (=copy) or zero
     depending on others factor actual digit at position, and  shift 
     through each position; adding up */
  unsigned int r=0;
  while (y != 0) {
    if (y & 1) r = add(r,x);
    y>>=1;
    x<<=1;
  }
  return r;
}

int main(int c, char** param)
{
  unsigned int x,y;
  if (c!=3) {
     printf("Fuck!\n");
     return 1;
  }
  sscanf(param[1],"%ud",&x);
  sscanf(param[2],"%ud",&y);
  printf("%d\n", mult(x,y));
  return 0;
}
Matías
fuente
1
+1 Buena implementación de la evaluación de acarreo. Me gusta tu código :)
yo '
@ BЈовић: Mi culpa, pensé que el trolling no se trata de entender. Se cambiaron los nombres y se agregaron comentarios.
Matthias
lo siento. No entendí qué es esa etiqueta y de qué se trata realmente la Q. Deberías revertirlo
B 13овић
@Matthias en este caso es útil entender cómo funciona para poder apreciar cuán retorcida es esa operación de transporte convergente. En una situación real de código troll, los comentarios podrían ser redactados :-)
greggo
Me gustaría señalar que si desea agregar números invertidos en bits (con un valor alto a bajo) y no tiene una instrucción 'bitrev', este es probablemente un enfoque perfectamente razonable (después de cambiar a c> > = 1 por supuesto)
greggo
7

Aquí hay muchas buenas respuestas, pero no parece que muchas de ellas aprovechen el hecho de que las computadoras modernas son realmente poderosas. Hay múltiples unidades de procesamiento en la mayoría de las CPU, entonces, ¿por qué usar solo una? Podemos explotar esto para obtener excelentes resultados de rendimiento.

#include <stdio.h>
#include <limits.h>
#include "omp.h"

int mult(int a, int b);

void main(){
        int first;
        int second;
        scanf("%i %i", &first, &second);
        printf("%i x %i = %i\n", first, second, mult(first,second));
}

int mult(int second, int first){
        int answer = INT_MAX;
        omp_set_num_threads(second);
        #pragma omp parallel
        for(second = first; second > 0; second--) answer--;
        return INT_MAX - answer;
}

Aquí hay un ejemplo de su uso:

$ ./multiply
5 6
5 x 6 = 30

La #pragma omp paralleldirectiva hace que OpenMP divida cada parte del ciclo for en una unidad de ejecución diferente, ¡así que estamos multiplicando en paralelo!

Tenga en cuenta que debe usar el -fopenmpindicador para indicarle al compilador que use OpenMP.


Troll partes:

  1. Engañoso sobre el uso de la programación paralela.
  2. No funciona en números negativos (o grandes).
  3. En realidad no divide las partes del forbucle: cada subproceso ejecuta el bucle.
  4. Nombres de variables molestos y reutilización de variables.
  5. Hay una sutil condición de carrera answer--; la mayoría de las veces, no aparecerá, pero ocasionalmente causará resultados inexactos.
Millinon
fuente
2
¿Por qué no combinar esto con la respuesta SIMD de Paul R, para que pueda ejecutar 32 veces más rápido en lugar de 8 veces? Aunque realmente, usted quiere involucrar a la GPU así como a los núcleos; entonces realmente ardería. :)
abarnert
2
También podría usar OpenMPI para ejecutarlo en algunas máquinas en paralelo.
millinon el
6

Desafortunadamente, la multiplicación es un problema muy difícil en informática. La mejor solución es usar la división en su lugar:

#include <stdio.h>
#include <limits.h>
int multiply(int x, int y) {
    int a;
    for (a=INT_MAX; a>1; a--) {
        if (a/x == y) {
            return a;
        }
    }
    for (a=-1; a>INT_MIN; a--) {
        if (a/x == y) {
            return a;
        }
    }
    return 0;
}
main (int argc, char **argv) {
    int a, b;
    if (argc > 1) a = atoi(argv[1]);
    else a = 42;
    if (argc > 2) b = atoi(argv[2]);
    else b = 13;
    printf("%d * %d is %d\n", a, b, multiply(a,b));
}
usuario3175123
fuente
6

En la vida real, generalmente respondo al trolling con conocimiento, así que aquí hay una respuesta que no trolló en absoluto. Funciona para todos los intvalores hasta donde puedo ver.

int multiply (int a, int b) {
  int r = 0;
  if (a < 0) { a = -a; b = -b }

  while (a) {
    if (a&1) {
      int x = b;
      do { int y = x&r; r ^= x; x = y<<1 } while (x);
    }
    a>>=1; b<<=1;
  }
  return r;
}

A mi entender, esto es muy parecido a cómo una CPU podría hacer multiplicación de enteros. Primero, nos aseguramos de que al menos uno de los argumentos ( a) sea positivo volteando el signo en ambos si aes negativo (y no, me niego a contar la negación como un tipo de suma o multiplicación). Luego, el while (a)bucle agrega una copia desplazada de bal resultado para cada bit establecido a. El dobucle implementa el r += xuso y, xor y el cambio en lo que claramente es un conjunto de medios sumadores, con los bits de arrastre retroalimentados xhasta que no haya más (una CPU real usaría sumadores completos, lo que es más eficiente, pero C no lo hace) No tenga los operadores que necesitamos para esto, a menos que cuente el +operador).

hobbs
fuente
44
El autor de la pregunta no trolló. Se supone que debes troll.
John Dvorak
2
¡Es un troll sigiloso! El error secreto está en un == INT_MIN.
Jander
1
@Jander hmm. Sí, esa es buena. Supongo (en los sistemas complementarios de dos ordinarios) que el resultado de negar a sigue siendo negativo, y el while(a)ciclo nunca termina.
hobbs
@hobbs Sí, eso me suena bien. De lo contrario, una respuesta muy bonita.
Jander
6
 int bogomul(int A, int B)
{
    int C = 0;
    while(C/A != B)
    {

        print("Answer isn't: %d", C);
        C = rand();

    }
    return C;
}
Chengarda
fuente
1
Esto fallará horriblemente si el resultado se desborda. ¡Agradable! Sin embargo, supongo que no deberías imprimir.
John Dvorak el
2
falla para a = 2, b = 2, c = 5
BЈовић
@ BЈовић while(C/A != B || C%A):?
abarnert
2
Tenga en cuenta que este es realmente un intento de hacer lo mismo que el sucesor de Deep Thought, pero para todos los universos posibles , en lugar de solo aquel donde la respuesta es 42. Lo que sería muy impresionante si no fuera por el error. Y la falta de manejo de errores en el caso de Vogons.
abarnert
1
Necesita múltiples hilos. Ya sabes, para que sea eficiente.
greggo
6

Lanzando esto a la mezcla:

#include <stdio.h>
#include <stdlib.h>

int mul(int a, int b)
{
        asm ("mul %2"
            : "=a" (a)
            : "%0" (a), "r" (b) : "cc"
        );
        return a;
}

int main(int argc, char *argv[])
{
        int a, b;

        a = (argc > 1) ? atoi(argv[1]) : 0;
        b = (argc > 2) ? atoi(argv[2]) : 0;

        return printf("%d x %d = %d\n", a, b, mul(a, b)) < 1;
}

De la página de información .

- Introducir algo extremadamente inaceptable o irrazonable en el código que no se puede eliminar sin tirar todo, lo que hace que la respuesta sea completamente inútil para el OP.

- [...] La intención es hacer la tarea en un idioma que el OP perezoso podría considerar aceptable, pero aún así frustrarlo.

Runium
fuente
2
"sin usar los operadores de multiplicación y suma". Buena flexión de las reglas: esto será absolutamente inútil para el que pregunta :-)
John Dvorak
2
Esto no es realmente una solución C. Además, no se compila en mi ARM9.
abarnert
1
@abarnert: no reconoce su declaración como un argumento relevante.
Runium
@Sukminder: La pregunta es "¿Es posible escribir un programa en C ...?" El ensamblaje en línea no es C. El hecho de que algunos compiladores de C también puedan hacer ensamblaje en línea no cambia eso, al igual que el hecho de que algunos compiladores de C también pueden hacer C ++ u ObjC hace que C ++ u ObjC cuenten como código C.
abarnert
2
@abarnert: es un código incrustado ampliamente utilizado en programas en C. A pesar de que se trata de una raza cruzada se puede argumentar que es un programa en C . Incluso es posible que OP lo reconozca como código C. Claramente no es python, o?
Runium
5
#include <stdio.h>
#include <stdlib.h>

int mult (int n1, int n2);
int add (int n1, int n2 );
int main (int argc, char** argv)
{
        int a,b;
        a = atoi(argv[1]);
        b = atoi(argv[2]);

        printf ("\n%i times %i is %i\n",a,b,mult(a,b));
        return 0;
}

int add (int n1, int n2 )
{
        return n1 - -n2;
}

int mult (int n1, int n2)
{
        int sum = 0;
        char s1='p', s2='p';
        if ( n1 == 0 || n2 == 0 ) return 0;
        if( n1 < 0 )
        {
                s1 = 'n';
                n1 = -n1;
        }
        if( n2 < 0 )
        {
                s2 = 'n';
                n2 = -n2;
        }
        for (int i = 1; i <= n2; i = add( i, 1 ))
        {
                sum = add(sum,  n1);
        }
        if ( s1 != s2 ) sum = -sum;
        return sum;
}
Jaybers
fuente
5

¿Es posible escribir un programa en C que multiplique dos números sin usar los operadores de multiplicación y suma?

Seguro:

void multiply() {
    printf("6 times 7 is 42\n");
}

Pero, por supuesto, eso es trampa; obviamente quiere poder suministrar dos números, ¿verdad?

void multiply(int a, int b) {
    int answer = 42;
    if (answer / b != a || answer % b) {
        printf("The answer is 42, so that's the wrong question.\n");
    } else {
        printf("The answer is 42, but that's probably not the right question anyway.\n");
    }
}
abarnert
fuente
¡Por qué no me resultó obvio en absoluto!
leewz
4

No hay aritmética como la aritmética de puntero:

int f(int a, int b) {
        char x[1][b];
        return x[a] - x[0];
}

int
main(int ac, char **av) {
        printf("%d\n", f(atoi(av[1]),atoi(av[2])));
        return 0;
}

La función fimplementa la multiplicación. mainsimplemente lo llama con dos argumentos.
Funciona para números negativos también.

Ugoren
fuente
Negativo a, sí, negativo b, no lo creo. Pero eso se puede solucionar de muchas maneras creativas. Más simple sería sign_a ^ = sign_b, sign_b = 0.
MSalters
@MSalters, probado y funciona para todas las combinaciones de signos (con Linux / gcc).
ugoren
3

C#

Creo que la resta y la negación no están permitidas ... De todos modos:

int mul(int a, int b)
{
    int t = 0;
    for (int i = b; i >= 1; i--) t -= -a;
    return t;
}
thepirat000
fuente
1
Esta es exactamente la solución en la que pensé ... pero al llegar tarde a la fiesta sabía que era cuestión de desplazarse hacia abajo hasta que descubrí que alguien ya lo había escrito. Aún así, obtienes un - (- 1) de mí.
Floris
3

C con intrínsecos SSE (porque todo es mejor con SIMD):

#include <stdio.h>
#include <stdlib.h>
#include <xmmintrin.h>

static float mul(float a, float b)
{
    float c;

    __m128 va = _mm_set1_ps(a);
    __m128 vb = _mm_set1_ps(b);
    __m128 vc = _mm_mul_ps(va, vb);
    _mm_store_ss(&c, vc);
    return c;
}

int main(int argc, char *argv[])
{
    if (argc > 2)
    {
        float a = atof(argv[1]);
        float b = atof(argv[2]);
        float c = mul(a, b);
        printf("%g * %g = %g\n", a, b, c);
    }
    return 0;
}

La gran ventaja de esta implementación es que se puede adaptar fácilmente para realizar 4 multiplicaciones paralelas sin *o +si es necesario.

Paul R
fuente
No creo que esto sea trolling ...
John Dvorak
De Verdad ? ¿Pensé que el uso inútil, gratuito y específico de la arquitectura de SIMD lo calificaría para el trolling de código?
Paul R
hmm ... cierto. No me di cuenta de que esto era específico de la arquitectura.
John Dvorak
3
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define INF 1000000

char cg[INF];

int main()
{
    int a, b;

    char bg[INF];
    memset(bg, '*', INF);

    scanf("%d%d", &a, &b);

    bg[b] = 0;

    while(a--)  
        strcat(cg, bg);

    int result;
    printf("%s%n",cg,&result);
    printf("%d\n", result);

    return 0;
}
  • trabajar solo para el resultado de multiplicación <1 000 000
  • Hasta ahora no puedo deshacerme del operador, posiblemente mejorando aquí
  • usando el especificador de formato% n en printf para contar el número de caracteres impresos (publico esto principalmente para recordar la existencia% n en C, en lugar de% n, por supuesto, podría borrarse, etc.)
  • Imprime los caracteres a * b de '*'
marol
fuente
Ahora esperando la solución de 'emulación de máquina de turing'.
greggo
1
while strlen(cg) != aes un método muy trolling para eliminar el --(lo hace O (N * N)).
MSalters
3

Probablemente demasiado rápido :-(

   unsigned int add(unsigned int a, unsigned int b)
    {
        unsigned int carry;

        for (; b != 0; b = carry << 1) {
            carry = a & b;
            a ^= b;
        }
        return a;
    }

    unsigned int mul(unsigned int a, unsigned int b)
    {
        unsigned int prod = 0;

        for (; b != 0;  a <<= 1, b >>= 1) {
            if (b & 1)
                prod = add(prod, a);
        }
        return prod;
    }
David Laight
fuente
1
Ungh Esto no es trolling. Esta es una forma completamente razonable de hacer esto.
John Dvorak
1
Es trolly porque es demasiado rápido :-)
Timtech
3

Esta versión de Haskell solo funciona con enteros no negativos, pero multiplica la forma en que los niños la aprenden por primera vez. Es decir, 3x4 es 3 grupos de 4 cosas. En este caso, las "cosas" que se cuentan son muescas ('|') en un palo.

mult n m = length . concat . replicate n . replicate m $ '|'
mhwombat
fuente
3
int multiply(int a, int b) {
    return sizeof(char[a][b]);
}

Esto puede funcionar en C99, si hace buen tiempo, y su compilador admite tonterías indefinidas.

Konrad Borowski
fuente
3

Como el OP no solicitó C , ¡aquí hay uno en (Oracle) SQL!

WITH
   aa AS (
      SELECT LEVEL AS lvl 
      FROM dual
      CONNECT BY LEVEL <= &a
   ),
   bb AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &b
   )
SELECT COUNT(*) AS addition
FROM (SELECT * FROM aa UNION ALL SELECT * FROM bb);

WITH
   aa AS (
      SELECT LEVEL AS lvl 
      FROM dual
      CONNECT BY LEVEL <= &a
   ),
   bb AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &b
   )
SELECT COUNT(*) AS multiplication
FROM aa CROSS JOIN bb;
SQB
fuente
1
¡Dios mío, está lleno de *s!
Paul R
1
@PaulR :) pero no son operadores .
SQB
2
int add(int a, int b) {
    return 0 - ((0 - a) - b);
}

int mul(int a, int b) {
    int m = 0;
    for (int count = b; count > 0; m = add(m, a), count = add(count, 0 - 1)) { }
    return m;
}

Puede contener trazas de UD.

Joker_vD
fuente
2
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
  int x = atoi(argv[1]);
  int y = atoi(argv[2]);
  FILE *f = fopen("m","wb");
  char *b = calloc(x, y);
  if (!f || !b || fwrite(b, x, y, f) != y) {
    puts("503 multiplication service is down for maintenance");
    return EXIT_FAILURE;
  }
  printf("%ld\n", ftell(f));
  fclose(f);
  remove("m");
  return 0;
}

Prueba de funcionamiento:

$ ./a.out 1 0
0
$ ./a.out 1 1
1
$ ./a.out 2 2
4
$ ./a.out 3 2
6
$ ./a.out 12 12
144
$ ./a.out 1234 1234
1522756
Kaz
fuente