Perché la divisione e la moltiplicazione per 2 utilizzano l'operatore di turno anziché l'operatore di divisione?

La moltiplicazione è complessa in genere ... a meno che uno dei moltiplicativi sia la base in cui i numeri sono di per sé.

Quando si lavora con matematica di base 10, moltiplicare per 10 è banale: "aggiungi lo stesso numero di zeri del 10". 2 * 10 = 20 e 3 * 100 = 300

Questo è molto facile per noi. La stessa esatta regola esiste in binario.

In binario, 2 * 3 = 6 è 10 * 11 = 110 e 4 * 3 = 12 è 100 * 11 = 1100 .

Per un sistema che già lavora con bit (AND e OR), operazioni come lo spostamento e il rotolo esistono già come parte del set di strumenti standard. Succede solo che tradurre N * 2^M in binario diventa shift N by M places

Se stiamo facendo qualcosa che non è una potenza di 2 in binario, dobbiamo tornare al vecchio moltiplicare e aggiungere. Certo, il binario è un po 'più facile, ma un po' più noioso allo stesso tempo.

11 * 14 diventa (da Wikipedia su moltiplicatore binario - una buona lettura in quanto si collega ad altri algoritmi di moltiplicazione per binari ... cambiare i poteri di due è ancora molto più semplice):

       1011   (this is 11 in decimal)
     x 1110   (this is 14 in decimal)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is 154 in decimal)

Puoi vedere, stiamo ancora facendo turni e aggiunge. Ma lascia che sia modificato in 11 * 8 per vedere come diventa facile e perché possiamo semplicemente saltare alla risposta:

       1011   (this is 11 in decimal)
     x 1000   (this is  8 in decimal)
     ======
       0000   (this is 1011 x 0)
      0000    (this is 1011 x 0, shifted one position to the left)
     0000     (this is 1011 x 0, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   1011000   (this is 88 in decimal)

Semplicemente saltando all'ultima fase, abbiamo drasticamente semplificato l'intero problema senza aggiungere molti 0 che siano ancora 0.

La divisione è la stessa cosa della moltiplicazione, solo del contrario. Proprio come 400 / 100 può essere riassunto come "cancella gli zeri", così può essere fatto anche in binario.

Utilizzando l'esempio di 88 / 8 dell'esempio precedente

         1011 r0
     ________
1000 )1011000
      1000
      ----
       0110
       0000
       ----
        1100
        1000
        ----
         1000
         1000
         ----
         0000

Puoi vedere che i passaggi nel lungo cammino di una lunga divisione per binario sono ancora piuttosto noiosi e, per una potenza di due, puoi semplicemente saltare alla risposta, in effetti, annullando gli zeri.

(come nota a margine, se questa è un'area interessante per te, potresti trovare sfogliare il tag binario su Math. SE , beh ... interessante.)

Questa è una ottimizzazione specifica che viene eseguita nel caso in cui il programmatore conosca il divisore sarà una potenza di 2.

Se il divisore non è altro che una potenza di 2, questa ottimizzazione non è possibile e il codice deve essere riscritto per utilizzare la divisione regolare.

Quindi, ad esempio, se abbiamo una funzione che è

dividebyNumberOFWeekendDays ( dividend )

Return dividend >> 1;

Speriamo che il nostro magico numero di giorni del fine settimana non diventi mai qualcosa di diverso da una potenza di due perché allora abbiamo bisogno di riscrivere e testare la funzione da capo.

Se scrivi

 b=a/2;

ci si deve fidare del compilatore per ottimizzarlo in un'operazione "shift" a livello di codice macchina (che è in genere più veloce di un'istruzione di divisione generale). E circa 25 anni fa, quando ho iniziato a lavorare con i compilatori C, non si poteva essere sicuri che il compilatore funzionasse in questo modo. Oggi, qualsiasi compilatore C decente sa come ottimizzare questo (almeno, quando non si disabilita l'ottimizzatore).

Se, tuttavia, scrivi

 b=a>>1;

puoi essere (quasi) sicuro che il compilatore genera un'operazione di shift, se attivi l'ottimizzatore o meno.