Bitshift per moltiplicare con qualsiasi numero

Question

Utilizzando solo l'aggiunta, la sottrazione e il cambio di bit, come posso moltiplicare un numero intero con un numero dato?

Ad esempio, voglio moltiplicare un numero intero da 17.

So che lo spostamento a sinistra è moltiplicando per un multiplo di 2 e spostando a destra è la divisione per una potenza di 2, ma non so come generalizzare questo.

---

E i numeri negativi? Converti in complemento a due e fai la stessa procedura?

(EDIT: OK, ho ottenuto questo, non importa si converte in complemento a due e poi si fa a spostare in base al numero da sinistra a destra invece che da destra a sinistra..)

---

Ora arriva la parte difficile. Possiamo usare solo 3 operatori.

Per esempio, moltiplicando per 60 posso fare usando questo:

(x << 5) + (x << 4) + (x << 3) + (x << 2) 

Dove x è il numero che sto moltiplicando. Ma sono 7 operatori - come posso condensare per usare solo 3?

Answer 1

Per quanto ne so, non esiste un modo semplice per moltiplicare in generale utilizzando solo 3 operatori.

Moltiplicando con 60 è possibile, dal momento che 60 = 64-4: (x << 6) - (x << 2)

Answer 2

17 = 16 + 1 = (2^4) + (2^0). Pertanto, sposta il numero a sinistra di 4 bit (per moltiplicare per 2^4 = 16) e aggiungi il numero originale.

Un altro modo di guardarlo è: 17 è 10001 in binario (base 2), quindi è necessaria un'operazione di spostamento per ciascuno dei bit impostati nel moltiplicatore (cioè i bit 4 e 0, come sopra).

Non so C, quindi non mi metterò in imbarazzo offrendo codice.

Answer 3

Si chiama shift-and-add. Wikipedia ha una buona spiegazione di questo:

http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add

EDIT: Per rispondere alla tua altra domanda, sì la conversione in complimento a due funzionerà. Ma è necessario firmare estenderlo abbastanza a lungo da contenere l'intero prodotto. (supponendo che sia quello che desideri)

EDIT2: Se entrambi gli operandi sono negativi, solo due si complimentano entrambi fin dall'inizio e non dovrai preoccuparti di questo.

Answer 4

Ecco un esempio di moltiplicare per 3:

unsigned int y = (x << 1) + (x << 0); 

(dove sto supponendo che x è anche unsigned).

Spero che dovresti essere in grado di generalizzare questo.