moltiplicazione di due numeri

Question

Pochi giorni fa ho avuto un'intervista con Qualcomm. Ero kinnda bloccato a una domanda, la domanda mi sembrava molto semplice ma né io né l'intervistatore erano soddisfatti delle mie risposte, se qualcuno fosse in grado di fornire una buona soluzione a questo problema.

La domanda è:

Moltiplicare 2 numeri senza utilizzare qualsiasi loop ed integrazioni e, naturalmente, senza moltiplicazione e divisione.

a cui ho risposto: ricorsione

Ha detto niente altro al livello molto basso.

A cui il pensiero genuino che mi è venuto in mente era un po 'mutevole, ma il bit shifting moltiplicherebbe solo il numero per potenza di 2 e per altri numeri dovremmo finalmente fare un'aggiunta.

Ad esempio: 10 * 7 può essere realizzata come: (binaria di 7 ~~ 111) < 2 + 10 < < 1 + 10 40 + 20 + 10 = 70

Ma ancora aggiunta non era permesso.

Qualche idea su questo argomento ragazzi.

Answer 1

Come su tabelle di moltiplicazione?

Answer 2

Forse è possibile aggiungere in modo ricorsivo, utilizzando operazioni bit a bit in sostituzione dell'operatore di addizione. Vedi: Adding Two Numbers With Bitwise and Shift Operators

Answer 3

E la moltiplicazione dei contadini russi senza l'aggiunta? C'è un modo semplice (poche righe, nessun loop) per simulare l'aggiunta usando solo AND, OR, XOR e NOT?

Answer 4

È possibile implementare gli operatori addizionatori con bit. Ma comunque, se vuoi evitare i loop, dovresti scrivere molto codice. (Ho usato per implementare la moltiplicazione senza operatori aritmetici, ma uso il ciclo, spostando l'indice fino a diventare zero. Se può aiutarti, dimmelo, e cercherò il file)

Answer 5

Puoi separare i tuoi problemi prima implementando l'addizione e quindi la moltiplicazione basata sull'aggiunta.

Per l'aggiunta, attuare quello che fanno su processori a livello cancello utilizzando gli operatori sui bit C:

http://en.wikipedia.org/wiki/Full_adder

Poi per la moltiplicazione, con l'aggiunta è implementato, usa goto istruzioni ed etichette così non verrà utilizzata alcuna istruzione loop (le dichiarazioni di iterazione for, while e do).

Answer 6

Ecco una soluzione che utilizza solo ricerca, aggiunta e spostamento. La ricerca non richiede la moltiplicazione in quanto è una matrice di puntatori a un altro array, quindi è necessaria l'aggiunta per trovare la matrice giusta. Quindi, utilizzando il secondo valore, è possibile ripetere l'aritmetica del puntatore e ottenere il risultato della ricerca.

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

int main(int argc, char **argv) 
{ 
    /* Note:As this is an array of pointers to an array of values, addition is 
    only required for the lookup. 

    i.e. 

    First part: lookup + a value -> A pointer to an array 
    Second part - Add a value to the pointer to above pointer to get the value 
    */ 
    unsigned char lookup[16][16] = { 
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, 
    { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 }, 
    { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45 }, 
    { 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60 }, 
    { 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75 }, 
    { 0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90 }, 
    { 0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105 }, 
    { 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120 }, 
    { 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, 135 }, 
    { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150 }, 
    { 0, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143, 154, 165 }, 
    { 0, 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, 132, 144, 156, 168, 180 }, 
    { 0, 13, 26, 39, 52, 65, 78, 91, 104, 117, 130, 143, 156, 169, 182, 195 }, 
    { 0, 14, 28, 42, 56, 70, 84, 98, 112, 126, 140, 154, 168, 182, 196, 210 }, 
    { 0, 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, 210, 225 } 
    }; 
    unsigned short answer, mult; 
    unsigned char x, y, a, b; 

    x = (unsigned char)atoi(argv[1]); 
    y = (unsigned char)atoi(argv[2]); 
    printf("Multiple %d by %d\n", x, y); 

    answer = 0; 
    /* First nibble of x, First nibble of y */ 
    a = x & 0xf; 
    b = y & 0xf; 
    mult = lookup[a][b]; 
    answer += mult; 
    printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer); 

    /* First nibble of x, Second nibble of y */ 
    a = x & 0xf; 
    b = (y & 0xf0) >> 4; 
    mult = lookup[a][b]; 
    answer += mult << 4; 
    printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer); 

    /* Second nibble of x, First nibble of y */ 
    a = (x & 0xf0) >> 4; 
    b = y & 0xf; 
    mult = lookup[a][b]; 
    answer += mult << 4; 
    printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer); 

    /* Second nibble of x, Second nibble of y */ 
    a = (x & 0xf0) >> 4; 
    b = (y & 0xf0) >> 4; 
    mult = lookup[a][b]; 
    answer += mult << 8; 
    printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer); 

    return 0; 
} 

Answer 7

Domanda: Moltiplicare 2 numeri senza utilizzare qualsiasi loop ed integrazioni e, naturalmente, senza moltiplicazione e divisione.

La moltiplicazione è definita in termini di aggiunta. È impossibile non trovare aggiunte in un'implementazione della moltiplicazione.

I numeri arbitrari di precisione non possono essere moltiplicati senza loop/ricorsione.

La moltiplicazione di due numeri di bit-bit fissi può essere implementata tramite una ricerca tabella. Il problema è la dimensione del tavolo. La generazione della tabella richiede l'aggiunta.

La risposta è: Non è possibile.

Answer 8

È possibile utilizzare invece logaritmi e sottrazioni.

log (a * b) = log (a) + log (b)
a + b = - (- ter)
exp (log (a)) = a

round(exp(-(-log(a)-log(b))))