Wie schreibe ich ein C-Programm zur Multiplikation ohne die Operatoren * und +?

68

Ist es möglich, ein C-Programm zu schreiben, das zwei Zahlen multipliziert, ohne die Multiplikations- und Additionsoperatoren zu verwenden?

Ich habe dies bei Stack Overflow gefunden . Bitte helfen Sie diesem armen Programmierer bei seinem Problem. Und bitte geben Sie keine Antworten wie c = a/(1/((float)b)), was genau das gleiche ist wie c = a*b. (Und wird schon als Antwort gegeben.)

Die Antwort mit den meisten positiven Stimmen am 19. Januar 2014 gewinnt.

Hinweis: Dies ist eine Frage. Bitte nehmen Sie die Frage und / oder die Antworten nicht ernst. Weitere Informationen finden Sie unter Code-Trolling .

s3lph
quelle
2
@ PaulR verwenden Sie Ihre Fantasie
John Dvorak
26
Code-golf.SE sollte kein Ort sein, an dem Sie Fragen verspotten können, die Sie auf StackOverflow gesehen haben.
Gareth
17
@ Gareth, bist du sicher? Die erste Zeile legt nahe, dass dies durchaus angemessen sein könnte.
Darren Stone
5
Ich warte darauf, dass jemand einen Algorithmus schreibt, der auf dem Schlaf basiert
kb_sou
21
Diese Frage ist nicht so lächerlich, wie es sich anhört. Tatsächliche Computerhardware (Transistoren) hat keine Multiplikations- und Additionsoperationen - sie haben grundlegende Logikoperationen wie NOT, AND, OR, XOR. Wenn Sie herausfinden, wie Sie diese Frage beantworten können, erhalten Sie einen hervorragenden Einblick in die Funktionsweise eines Computers auf der Ebene der Logikgatter.
Gabe

Antworten:

147

Verwenden Sie immer die Rekursion

Recusion ist der richtige Weg!

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
quelle
8
Ich würde +3 geben, wenn ich könnte: eine für die ultimative Rekursion, eine für ??::ohne Klammern, eine für das Lösen des Problems, ohne zu versuchen, die Regeln zu ändern;)
yo '
10
Wenn Picasso ein Programmierer wäre ...
R Hughes
4
@SargeBorsch Aber wo hat Spaß in sein , dass ?
Oberon
3
@HC_ Die incFunktion testet ihr Argument, um festzustellen , ob das niedrigste Bit ist 1. Wenn dies der Fall ist, ruft er die verbleibenden oberen Bits des Arguments auf und gibt das Ergebnis mit demselben niedrigen Bit zurück, auf das der Haken gesetzt 0wurde. Wenn dies nicht der Fall ist (dh das niedrigste Bit ist 0), ersetzt er das 0mit einem 1und gibt das Ergebnis zurück . Der Vorgang ist sehr ähnlich zu dem, was Sie tun würden, wenn Sie die Werte von Hand addieren würden, Binärziffer für Binärziffer.
JAB
2
Geht die Inkrementfunktion nicht für -1 in eine Endlosschleife? (0xFFFF) ideone zeigt (-1 >> 1) == -1.
Destrictor
87

Sie müssen das Programm jedes Mal kompilieren, aber es multipliziert alle positiven Ganzzahlen genau in jeder Version von C oder C ++.

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

 typedef char buffer[A][B];

 main() {
    printf("%d\n",sizeof(buffer));
 }
Mark Lakata
quelle
4
Platziere es in einer Struktur und du brauchst kein Gedächtnis.
Ben Jackson
4
Hahahah toll !!
Almo
1
verwenden "%zu"Format - String.
Grijesh Chauhan
5
just sizeof(char[A][B])wird funktionieren (es sei denn, A <= 0 oder B <= 0 oder A * B überläuft. In diesem Fall sollte ein Fehler vom Typ 'bad type'
angezeigt werden.
3
@DavidRicherby - Ich könnte den Code vereinfachen main(){return sizeof(char[A][B]);}und Sie kompilieren mitcc -DA=6 -DB=7 a.c; ./a.out; echo $?
Mark Lakata
47

Wenn Sie mit ein wenig Ungenauigkeit einverstanden sind, können Sie die Monte-Carlo-Methode anwenden :

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

Beispiel:

$ ./mul 300 250
300 * 250 = 74954

Ich denke das könnte gut genug sein;)

Petr Pudlák
quelle
3
Sie haben meine Stimme. Ich habe gehört, Monte Carlo ist das, was die NASA für ihre Arithmetik verwendet. Aber ich würde das gerne ohne die beiden Instanzen des ++Operators sehen.
Darren Stone
1
@ DarrenStone-= -1
Timtech
20
@ Timtech |= 1(wird auf 50% der Zahlen arbeiten, 100% der Zeit)
Darren Stone
2
+1, aber mit der Bemerkung, dass es zu langsam sein könnte, und Sie könnten Multi-Thread-Unterstützung hinzufügen, indem Sie vorsichtig die "Anzahl ++"
sperren
1
Es gibt immer printfInkremente: printf("%*cc%n\n", count, &count, 'c');(Druckt 'c', dann ein weiteres 'c' und speichert die Anzahl der zurückgeschriebenen Zeichen count.
MSalters
45

Da Sie nicht angegeben haben, wie groß die Zahl ist, gehe ich davon aus, dass Sie zwei Ein-Bit-Zahlen meinen.

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

Wenn Sie eine maximal effiziente Implementierung wünschen, verwenden Sie die folgende winzige Implementierung:

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

Beachten Sie, dass immer noch nur Bits akzeptiert werden, obwohl die Typen implizite Ints sind. Sie benötigen weniger Code und sind daher effizienter. (Und ja, es wird kompiliert.)

Cel Skeggs
quelle
8
Nett. Eine absichtliche Fehlinterpretation der Frage :-)
John Dvorak
6
Sie können dies zu optimieren return a && b;. Es ist kürzer, also schneller.
Ry
1
@minitech: Ich habe mich dagegen entschieden, um den Code etwas zu verschlechtern. Wenn ich noch weiter gehen wollte, würde ich es schaffen return a&b;.
Cel Skeggs
1
C muss #include<stdbool.h>definieren trueund false.
Leewz
1
Ja, #include<stdbool.h>scheint nur drei zu sein , #defines , die Sie selbst tun können ( true, false, boolund ein Flag zu markieren , dass es aktiviert ist schon). Sie können auch einen Trick aus einer der anderen Antworten nehmen und implizit intfür die "kurze" Version verwenden.
Leewz
31

Hier ist ein einfaches Shell-Skript, um dies zu tun:

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 ]*$"

UPDATE: Natürlich, um es in C zu tun, wickeln Sie es einfach in exec("bash", "-c", ...). (Danke, AmeliaBR)

Vroo
quelle
41
Ich kann mich nicht entscheiden, was schrecklicher ist. Dass Sie Ihre Berechnung an eine Suchmaschine auslagern oder dass Ihre gewählte Suchmaschine Bing ist. Leider glaube ich nicht, dass dies für unsere unglückliche OP funktionieren wird, die etwas in C brauchte.
AmeliaBR
5
Danke, dass du dieses Versehen erwischt hast. Zu Ihrer Information, ich verwende Bing, weil es bei Google schwieriger ist, Anfragen wie diese zu stellen. Sie müssen Header hinzufügen, um Google davon zu überzeugen, dass Ihre Anfrage wirklich von einem Browser stammt.
Vroo
2
@abarnert hmm ... versteht Bing "mal"? Wolfram Alpha könnte es aber.
John Dvorak
2
@ JanDvorak: Ja, Wolfram arbeitet. (Beachten Sie das %20, um die Verwendung von +Vorzeichen zu vermeiden .) Sie müssen jedoch die Ausgabe (in C) analysieren, um den Wert daraus zu erhalten. Das wird besonders schwierig, da die Ausgabe ein Bild und kein Text zu sein scheint. Durch HTML-Analyse und OCR ist dies möglicherweise die bestmögliche Antwort auf dieses Problem.
Abarnert
3
@ JanDvorak: Das macht keinen Spaß. Ich freute mich darauf, dass jemand eine einfache OCR-Bibliothek ohne Addition oder Multiplikation
schreibt
27

Lassen Sie uns eine rekursive Halbierungssuche zwischen INT64_MIN und INT64_MAX durchführen!

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

PS Es wird glücklich mit einigen Werten sigsegv. ;)

treamur
quelle
18

Leider funktioniert dies nur für ganze Zahlen.

Da das Hinzufügen nicht zulässig ist, erstellen wir zunächst einen Inkrement-Operator:

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

Als nächstes müssen wir mit dem Schild umgehen. Finden Sie zuerst das Vorzeichenbit:

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

Dann nimm das Vorzeichen und die Stärke jedes Arguments. Um eine Zahl im Zweierkomplement zu negieren, müssen Sie alle Bits invertieren und eins hinzufügen.

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

Um zwei positive ganze Zahlen zu multiplizieren, können wir die geometrische Bedeutung der Multiplikation verwenden:

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

Trolle:

  • Hinzufügung ist nicht erlaubt, zählt aber a++wirklich als Hinzufügung? Ich wette, der Lehrer wollte es zulassen.
  • Beruht auf dem Komplement von zwei, aber das ist ein implementierungsdefiniertes Verhalten, und die Zielplattform wurde nicht angegeben.
  • In ähnlicher Weise wird angenommen, dass Subtraktion und Division ebenso unzulässig sind.
  • << ist eigentlich die Multiplikation mit einer Zweierpotenz, daher sollte sie technisch nicht zugelassen werden.
  • Nicht benötigtes Diagramm ist nicht erforderlich. Es hätte auch transponiert werden können, um eine Zeile zu speichern.
  • Das wiederholte Verschieben von -1ist nicht die beste Möglichkeit, das Vorzeichenbit zu finden. Selbst wenn keine eingebaute Konstante vorhanden wäre, könnten Sie eine logische Verschiebung nach rechts von -1 ausführen und dann alle Bits invertieren.
  • XOR-1 ist nicht der beste Weg, um alle Bits zu invertieren.
  • Die ganze Scharade mit der Darstellung der Vorzeichengröße ist unnötig. Nur auf vorzeichenlose und modulare Arithmetik umgewandelt, wird der Rest erledigt.
  • da der absolute Wert von MIN_INT(AKA signBit) negativ ist, wird dieser Wert unterbrochen. Zum Glück klappt es immer noch in der Hälfte der Fälle, denn MIN_INT * [even number] sollte Null sein.Außerdem werden plusOnePausen -1eingelegt, die zu Endlosschleifen führen, sobald das Ergebnis überläuft. plusOnefunktioniert gut für jeden Wert. Entschuldigung für die Verwirrung.
John Dvorak
quelle
+1 für einen tatsächlichen Code-Troll: Es sieht so aus, als ob es funktionieren sollte, aber es wird sehr wahrscheinlich auf dem OP explodieren und er / sie wird keine Ahnung haben warum.
Kevin
1
Es ist möglich, Additionen ohne ANY-Additionsoperatoren durchzuführen, indem Sie einfach shift, XOR und AND verwenden. All diese ++ 's machen mir den Kopf weh - Single Bit ADD mit Carry ist (x ^ y) | ((x & y) << 1) (Modulo alle Fehler durch das Eingeben in diesem beschissenen kleinen Textfeld verursacht.)
Julie in Austin
@ JulieinAustin yep. Der Algorithmus ist noch ineffizienter als er sein muss. Sollte ich die Trollliste ändern? :-)
John Dvorak
1
@JulieinAustin (x ^ y) | ((x & y) << 1)funktioniert nicht ganz, es wird kein Carry übertragen, wenn x oder y und Carry in derselben Position wahr sind :)
hobbs
@hobbs-Lösung: Fügen Sie sie anstelle von ORing rekursiv hinzu, wenn der Übertrag ungleich Null ist.
John Dvorak
14

Funktioniert auch für Gleitkommazahlen:

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

Jeder weiß, dass Python einfacher zu verwenden ist als C. Und Python verfügt über Funktionen, die jedem Operator entsprechen, für Fälle, in denen Sie den Operator nicht verwenden können. Welches ist genau unsere Problemdefinition, richtig? Damit:

#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
quelle
10

Keine der anderen Antworten ist theoretisch zutreffend. Wie der allererste Kommentar zu dieser Frage besagt:

Bitte seien Sie genauer über "Zahlen"

Wir müssen Multiplikation und Zahlen definieren, bevor überhaupt eine Antwort möglich ist. Sobald wir das tun, wird das Problem trivial.

Der beliebteste Weg, dies zu Beginn der mathematischen Logik zu tun, besteht darin , von Neumann-Ordnungszahlen auf der ZF-Mengen-Theorie aufzubauen und dann die Peano-Axiome zu verwenden .

Dies wird natürlich in C übersetzt, vorausgesetzt, Sie haben einen Settyp, der andere Sätze enthalten kann. Es muss nichts anderes als Mengen enthalten, was es trivial macht (nichts von dem, was void*in den meisten Mengenbibliotheken Unsinn macht ), also überlasse ich die Implementierung dem Leser als Übung.

So zuerst:

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

Wenn Sie dies auf Ganzzahlen, Rationalitäten, Realzahlen, Surreals usw. erweitern möchten, können Sie - mit unendlicher Präzision (vorausgesetzt, Sie haben unendlichen Speicher und unendliche CPU) - booten. Aber wie Kroenecker berühmt sagte, machte Gott die natürlichen Zahlen; Alles andere ist das Werk des Menschen. Warum also die Mühe machen?

abarnert
quelle
1
Beeindruckend. Du bist sogar langsamer als ich.
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 );
}

Wenn Sie den a [b] -Hack als Betrug ansehen (da es sich wirklich um ein Add handelt), funktioniert dies stattdessen. Bei Tabellensuchen werden jedoch auch Zeiger hinzugefügt.

Siehe http://en.wikipedia.org/wiki/IBM_1620 - ein Computer, der tatsächlich mithilfe von Nachschlagetabellen hinzugefügt hat ...

Etwas Befriedigendes daran, einen Tabellenmechanismus zu verwenden, um eine Operation zu beschleunigen, die tatsächlich in einer Anweisung ausgeführt werden könnte.

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
quelle
Hoppla, es gibt *Saibling (obwohl es keine Multiplikation ist)
Sarge Borsch
Äh, die Tabellensuche verwendet Addition - (a [i]) ist dasselbe wie (* (a + i)).
Julie in Austin
@ JulieinAustin Ich erwähnte das. Die Tabellensuche kann durch Zusammenführen von Feldern (wie in IBM 1620 dargestellt, siehe Link) ohne Adds durchgeführt werden. Die Einrichtung in C ist jedoch problematisch. Zum einen müssen Sie die Tabelle an einer geeigneten Adresse ausrichten, damit die Indizes übereinstimmen können Just or'd in.
Greggo
8

Ich bin nicht sicher, was "Betrügen" in diesen "Code-Troll" -Postings bedeutet, aber dies multipliziert 2 beliebige Ganzzahlen zur Laufzeit mit no *oder +operator unter Verwendung von Standardbibliotheken (C99).

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

Meine Trolllösung für 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;
}
Matthias
quelle
1
+1 Gute Implementierung der Übertragbewertung. Ich mag deinen Code :)
yo '
@ BЈовић: Meine Schuld, ich dachte beim Trolling geht es nicht um Verstehen. Namen geändert und Kommentare hinzugefügt.
Matthias
Es tut uns leid. Ich habe falsch verstanden, was dieses Tag ist und worum es bei dem Q wirklich geht. Sie sollten es
zurücksetzen
@Matthias In diesem Fall ist es hilfreich zu verstehen, wie es funktioniert, damit wir erkennen können, wie verdreht diese Converging-Carry-Operation ist. In einer aktuellen Code-Troll-Situation könnten die Kommentare
korrigiert
Ich möchte darauf hinweisen, dass, wenn Sie bitumgekehrte Zahlen hinzufügen möchten (mit high to lo carry prop) und keine 'bitrev'-Anweisung haben, dies wahrscheinlich ein völlig vernünftiger Ansatz ist (nachdem Sie zu c> gewechselt haben) > = 1 natürlich)
Greggo
7

Hier gibt es viele gute Antworten, aber es sieht nicht so aus, als würden viele von ihnen die Tatsache ausnutzen, dass moderne Computer wirklich leistungsstark sind. In den meisten CPUs gibt es mehrere Prozessoreinheiten. Warum also nur eine? Wir können dies ausnutzen, um hervorragende Leistungsergebnisse zu erzielen.

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

Hier ist ein Beispiel für die Verwendung:

$ ./multiply
5 6
5 x 6 = 30

Die #pragma omp parallelDirektive veranlasst OpenMP, jeden Teil der for-Schleife auf eine andere Ausführungseinheit aufzuteilen, also multiplizieren wir parallel!

Beachten Sie, dass Sie das -fopenmpFlag verwenden müssen, um den Compiler anzuweisen, OpenMP zu verwenden.


Trollteile:

  1. Irreführend über die Verwendung der parallelen Programmierung.
  2. Funktioniert nicht bei negativen (oder großen) Zahlen.
  3. Teilt die Teile der forSchleife nicht wirklich - jeder Thread führt die Schleife aus.
  4. Ärgerliche Variablennamen und Wiederverwendung von Variablen.
  5. Es gibt eine subtile Rennbedingung answer--; Meistens wird es nicht angezeigt, aber gelegentlich werden ungenaue Ergebnisse erzielt.
Millinon
quelle
2
Kombinieren Sie dies mit der SIMD-Antwort von Paul R. So können Sie 32-mal schneller als 8-mal schneller arbeiten. Obwohl Sie wirklich die GPU und die Kerne mit einbeziehen möchten; dann würde es wirklich brennen. :)
abarnert
2
Könnte auch OpenMPI verwenden, um es auf einigen Rechnern parallel auszuführen.
Millinon
6

Leider ist die Multiplikation in der Informatik ein sehr schwieriges Problem. Die beste Lösung ist, stattdessen Division zu verwenden:

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

Im wirklichen Leben antworte ich normalerweise auf Trolling mit Wissen, daher hier eine Antwort, die überhaupt nicht trollt. intSoweit ich sehen kann, funktioniert es für alle Werte.

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

Nach meinem besten Verständnis ist dies sehr ähnlich, wie eine CPU tatsächlich eine ganzzahlige Multiplikation durchführen könnte. Zuerst stellen wir sicher, dass mindestens eines der Argumente ( a) positiv ist, indem wir das Vorzeichen auf beide setzen, wenn aes negativ ist (und nein, ich zähle Negation nicht als eine Art Addition oder Multiplikation). Dann while (a)fügt die Schleife bdem Ergebnis für jedes gesetzte Bit in eine verschobene Kopie von hinzu a. Die doSchleife implementiert die r += xVerwendung von und, xoder und das Verschieben einer Gruppe von Halbaddierern, wobei die Übertragsbits zurückgespeist werden, xbis sie nicht mehr vorhanden sind (eine echte CPU würde Volladdierer verwenden, was effizienter ist, C jedoch nicht). Wir haben nicht die Operatoren, die wir dafür benötigen, es sei denn, Sie zählen den +Operator).

hobbs
quelle
4
Der Fragesteller hat nicht getrollt. Du sollst trollen.
John Dvorak
2
Es ist ein Stealth-Troll! Der geheime Fehler liegt bei == INT_MIN.
Jander
1
@ Jander hmm. Ja, das ist gut. Ich vermute (auf gewöhnlichen Zweierkomplementsystemen), dass das Ergebnis des Negierens von a immer noch negativ ist und die while(a)Schleife niemals endet.
Hobbs
@hobbs Ja, das klingt für mich richtig. Ansonsten eine sehr schöne Antwort.
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
quelle
1
Dies wird schrecklich scheitern, wenn das Ergebnis überläuft. Nett! Du solltest aber nicht drucken.
John Dvorak
2
scheitert für a = 2, b = 2, c = 5
BЈовић
@ BЈовић: while(C/A != B || C%A)?
Abarnert
2
Beachten Sie, dass dies wirklich der Versuch ist, das Gleiche wie der Nachfolger von Deep Thought zu tun, aber für alle möglichen Universen , anstatt nur für die, auf die die Antwort 42 lautet. Was sehr beeindruckend wäre, wenn der Fehler nicht wäre. Und die fehlende Fehlerbehandlung bei Vogons.
Abarnert
1
Benötigt mehrere Threads. Sie wissen, um es effizient zu machen.
Greggo
6

Wirf dies in die Mischung:

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

Von der Infoseite .

- Etwas extrem Unannehmbares oder Unangemessenes in den Code einführen, das nicht entfernt werden kann, ohne alles wegzuwerfen, was die Antwort für das OP völlig unbrauchbar macht.

- […] Die Absicht ist, die Hausaufgaben in einer Sprache zu machen, die der faule OP für akzeptabel hält, ihn aber dennoch frustriert.

Runium
quelle
2
msgstr "ohne Verwendung der Multiplikations - und Additionsoperatoren". Nettes Biegen der Regeln - das wird für den Fragesteller absolut nutzlos sein :-)
John Dvorak
2
Dies ist keine echte C-Lösung. Außerdem kann es auf meinem ARM9 nicht kompiliert werden.
Abarnert
1
@abarnert: Erkenne deine Aussage nicht als relevantes Argument.
Runium
@Sukminder: Die Frage ist "Ist es möglich, ein C-Programm zu schreiben ...?" Inline-Assembly ist nicht C. Die Tatsache, dass einige C-Compiler auch Inline-Assemblys ausführen können, ändert nichts daran, ebenso wenig wie die Tatsache, dass einige C-Compiler auch C ++ oder ObjC ausführen können, dass C ++ oder ObjC als C-Code gelten.
Abarnert
2
@abarnert: Es ist eingebetteter Code, der häufig in C-Programmen verwendet wird. Obwohl es sich um eine Kreuzung handelt, kann man behaupten, dass es sich um ein C-Programm handelt . Es ist sogar plausibel, dass OP es als C-Code erkennt. Es ist eindeutig kein Python, oder?
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
quelle
5

Ist es möglich, ein C-Programm zu schreiben, das zwei Zahlen multipliziert, ohne die Multiplikations- und Additionsoperatoren zu verwenden?

Sicher:

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

Aber das ist natürlich Betrug. Offensichtlich will er in der Lage sein, zwei Zahlen zu liefern, oder?

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
quelle
Es war mir überhaupt nicht klar!
Leewz
4

Es gibt keine Arithmetik wie die Zeigerarithmetik:

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

Die Funktion fimplementiert die Multiplikation. mainnennt es einfach mit zwei Argumenten.
Funktioniert auch für negative Zahlen.

ugoren
quelle
Negativ a, ja, negativ bdenke ich nicht. Aber das kann auf viele kreative Arten behoben werden. Am einfachsten wäre sign_a ^ = sign_b, sign_b = 0.
MSalters
@MSalters, getestet und funktioniert für alle Zeichenkombinationen (mit Linux / gcc).
Ugoren
3

C #

Ich denke Subtraktion und Negation sind nicht erlaubt ... Egal:

int mul(int a, int b)
{
    int t = 0;
    for (int i = b; i >= 1; i--) t -= -a;
    return t;
}
thepirat000
quelle
1
Dies ist genau die Lösung, an die ich gedacht habe ... aber als ich zu spät zur Party kam, wusste ich, dass es eine Frage des Scrollens war, bis ich herausfand, dass es bereits jemand geschrieben hatte. Trotzdem bekommst du von mir einen - (- 1).
Floris
3

C mit SSE-Eigenheiten (weil mit SIMD alles besser ist):

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

Der große Vorteil dieser Implementierung ist, dass sie leicht angepasst werden kann, um ohne *oder +falls erforderlich 4 parallele Multiplikationen durchzuführen .

Paul R
quelle
Ich glaube nicht, dass das Trolling ist ...
John Dvorak
Ja wirklich ? Ich dachte, die sinnlose, unentgeltliche und architekturspezifische Verwendung von SIMD würde es für das Code-Trolling qualifizieren?
Paul R
hmm ... stimmt. Wusste nicht, dass dies architekturspezifisch ist.
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;
}
  • arbeiten nur für Multiplikationsergebnis <1 000 000
  • Bisher kann nicht loswerden - Operator, möglicherweise hier zu verbessern
  • Verwendung des% n-Formatspezifizierers in printf, um die Anzahl der gedruckten Zeichen zu zählen.
  • Druckt a * b Zeichen von '*'
marol
quelle
Warten Sie jetzt auf die Lösung zur Emulation von Turing-Maschinen.
Greggo
1
while strlen(cg) != aist eine sehr trollende Methode, um das zu eliminieren --(macht es zu O (N * N)).
MSalters
3

Wahrscheinlich zu schnell :-(

   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
quelle
1
Ungh. Das ist kein Trolling. Dies ist ein völlig vernünftiger Weg, um dies zu tun.
John Dvorak
1
Es ist Trolly, weil es zu schnell ist :-)
Timtech
3

Diese Haskell-Version funktioniert nur mit nichtnegativen ganzen Zahlen, aber sie multipliziert so, wie Kinder es zuerst lernen. Dh 3x4 ist 3 Gruppen von 4 Dingen. In diesem Fall sind die gezählten "Dinge" Kerben ('|') auf einem Stock.

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

Dies funktioniert möglicherweise in C99, wenn das Wetter stimmt und Ihr Compiler undefinierten Unsinn unterstützt.

Konrad Borowski
quelle
3

Da das OP nicht nach C gefragt hat , ist hier eines in (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
quelle
1
Mein Gott, es ist voll von *s!
Paul R
1
@PaulR :) aber sie sind keine Operatoren .
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;
}

Kann Spuren von UD enthalten.

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

Testlauf:

$ ./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
quelle