Le operazioni di cambio sono O(1) o O(n)?Il bit sta spostando O (1) o O (n)?
Ha senso che i computer in genere richiedono più operazioni per spostare 31 posizioni invece di spostare 1 posto?
O Ha senso il numero di operazioni richiesta per lo spostamento è costante indipendentemente dal numero di posti abbiamo bisogno di spostare?
PS: chiedendo se hardware è un tag appropriato ..
Alcuni set di istruzioni sono limitati a uno spostamento di bit per istruzione.E alcuni set di istruzioni consentono di specificare un numero qualsiasi di bit da spostare in un'unica istruzione, che di solito richiede un ciclo di clock sui processori moderni (il moderno è una parola volutamente vaga). Vedere dan04's answer su un barrel shifter, un circuito che sposta più di un bit in un'unica operazione.
Tutto si riduce all'algoritmo logico. Ogni bit nel risultato è una funzione logica basata sull'input. Per un singolo spostamento a destra, l'algoritmo sarebbe qualcosa di simile:
Ma l'equazione logica potrebbe facilmente essere:
Le porte logiche, essendo asincrone, possono fare tutto questo in un ciclo di clock. Eppure è vero che il singolo turno consente un ciclo di clock più veloce e meno porte da regolare, se tutto ciò che si sta confrontando sono questi due sapori di un'istruzione. Oppure l'alternativa sta richiedendo più tempo per stabilirsi, quindi l'istruzione prende 2 o 3 orologi o qualsiasi altra cosa, e la logica conta fino a 3, quindi blocca il risultato.
L'MSP430, ad esempio, ha solo istruzioni di rotazione di bit a destra (poiché è possibile eseguire un solo spostamento di bit o una rotazione a sinistra con un'altra istruzione, che lascerò al lettore per capire).
Il set di istruzioni ARM consente sia rotazioni multi-bit immediate e basate su registri, spostamenti aritmetici e spostamenti logici. Penso che ci sia solo un'effettiva istruzione di rotazione e l'altra è un alias, perché ruotare a sinistra 1 è la stessa di una rotazione a destra 32, è necessario solo un barilotto a una direzione per implementare una rotazione a più bit.
SHL in x86 consente più di un bit per istruzione, ma ha utilizzato più di un orologio.
e così via, è possibile esaminare facilmente qualsiasi set di istruzioni.
La risposta alla tua domanda è che non è stato risolto. A volte è una operazione, un ciclo, una istruzione. A volte è un ciclo di clock multipli di una istruzione. A volte si tratta di più istruzioni, più cicli di clock.
I compilatori spesso ottimizzano per questo tipo di cose. Supponiamo che tu abbia un'istruzione di registro a 16 bit impostata con un'istruzione swap byte e un'istruzione AND con immediato, ma solo un singolo bit shift. Potresti pensare che lo spostamento di 8 bit richiederebbe 8 cicli di istruzione di spostamento, ma potresti semplicemente scambiare byte (una istruzione) e poi AND la metà inferiore a zero (che potrebbe richiedere due istruzioni, o potrebbe essere un'istruzione di lunghezza di parola variabile di due parole, o potrebbe codificarsi in una singola istruzione) quindi richiede solo 2 o 3 cicli di istruzione/clock invece di 8. Per uno spostamento di 9 bit, puoi fare la stessa cosa e aggiungere uno spostamento, rendendolo 9 orologi contro 3 o 4 Inoltre, su alcune architetture, è più veloce moltiplicare per 256 che per passare da 8, ecc. Ecc. Ogni set di istruzioni ha le proprie limitazioni e trucchi.
Non è nemmeno il caso che la maggior parte dei set di istruzioni fornisca il multi bit o la maggior parte del limite per il bit singolo. I processori che rientrano nella categoria "computer", come X86, ARM, PowerPC e MIPS, si sposteranno verso un'operazione da spostare. Espandere a tutti i processori ma non necessariamente "computer" comunemente usati oggi, e si sposta nell'altro senso, direi che molti di loro sono single bit di multi bit, quindi sono necessarie più operazioni per eseguire uno spostamento multi-bit.
bit shifting è O (1) praticamente in ogni processore corrente.
Dai un'occhiata, ad esempio, all'istruzione xw "shrw". Il primo operando (nella sintassi AT &) è il numero di bit da spostare. Il modo in cui un compilatore implementa lo spostamento dipende dal compilatore, ma sarebbe sciocco mettere passaggi in un ciclo quando un processore può spostare N bit in un colpo solo.
Addendum: Ri: "Richiedono più operazioni per spostare a sinistra 31?" Ci sono diversi tipi di turni (se vi state chiedendo perché, considerate cosa fare con i bit che vengono spostati dal registro), ma la maggior parte dei processori può eseguire uno spostamento di istruzione singola di un numero di bit quanti il GPR può memorizzare. Per eseguire uno spostamento a 40 bit su un registro a 32 bit richiedere lo spostamento su più registri (si presume che un numero a 64 bit sia memorizzato su 2 registri a 32 bit), che su ogni processore che conosco richieda più istruzioni. Sarebbe comunque O (1), probabilmente non 1 orologio. Come interessante nota a margine, il processore Pentium IV è straordinariamente lento ai cambi di bit. Questo è ironico perché Intel ha storicamente raccomandato l'ottimizzazione di^2 divide e moltiplica per mezzo del cambio di bit. Vedi: this PDF e Google per ulteriori informazioni se interessati.
solo su 386+. quando si usano i conteggi di shift arbitrari su 286, è O (N) poiché i cicli di clock richiesti sono 5 + n. –
@MarcB: Perché, ovviamente, utilizzo ancora un 286, e quindi devo saperlo. : P –
Vuoi dire che il 90% dei processori in questi giorni è come l'x86 in quanto sono in grado di spostare N bit in una volta sola? – Pacerier
Per l'hardware normale, i registri di dimensioni fisse sono costanti indipendentemente dal numero di posizioni spostate.
notare che l'utilizzo della notazione O è piuttosto strano qui, si sarebbe normalmente utilizzato per indicare la complessità algoritmica in base al numero di non spostare il numero di posti per spostare anche ..
sì, avevo pensato che la notazione di O fosse strana, ma per il resto il titolo sarebbe molto lungo .. – Pacerier
1) Normalmente intendi moderno? 2) Non trovo la notazione O strana qui affatto. –
1) Intendo il 99,99% di hw ... –
A barrel shifter consente lo spostamento da eseguire in O(log n) passa — che può essere eseguito nello stesso ciclo di clock, rendendo lo spostamento di un'operazione O(1).
Ahem, testato per curiosità in C# e ottenuto risultati divertenti.
var sw = Stopwatch.StartNew();
long l = 1;
for (long i = 0; i < 20000000; i++) {
l = l << 60; l = l >> 60;
l = l << 60; l = l >> 60;
l = l << 60; l = l >> 60;
//...
// 50 of ^them^ total
}
Console.WriteLine(l + " " + sw.Elapsed);
Questo richiede 1,2 secondi sul mio PC. Ma se sostituisco
l = l << 60; l = l >> 60;
con
l = l << 1; l = l >> 1;
poi il tempo aumenta a 2,0 sec. Non ho idea di che tipo di ottimizzazioni siano in gioco qui, ma sembra strano.
Solo perché il compilatore non fa cose intelligenti, ciò non significa che le istruzioni non siano presenti nell'hardware. – Flexo
In realtà fa cose intelligenti, poiché ottengo lo stesso tempo per tutti i turni compresi tra 1 e 31 - 2,0 secondi. Poi ottengo 0,6 secondi se cambio esattamente di 32 bit, ma poi all'improvviso ottengo solo 1,2 secondi se il numero di turni è maggiore di 32. Questo è solo strano. – user1096188
Potrebbe essere meglio provare questo in C anziché in una lingua gestita. Probabilmente il jitter sta facendo alcune cose sotto il cofano che non stai vedendo. –
Come già notato, un barilotto può spostare un operando in una distanza arbitraria in tempo costante. Un barrel shifter, tuttavia, consuma una discreta quantità di spazio su un die CPU, quindi non sono inclusi in tutti i progetti di CPU.
Solo per un esempio abbastanza noto, l'Intel Pentium III includeva un barrel shifter - ma il Pentium IV ha fatto non. Il codice scritto per un Pentium III supponendo che un barrel shifter fosse presente a volte rallentava un po 'su un Pentium IV. Avevo un codice di crittografia (che include molti cambi e rotazioni) che girava circa 4 volte più velocemente su un Pentium III da 1.2 GHz rispetto a un Pentium IV da 2.8 GHz.
Richiedono più operazioni per spostare a sinistra 31? – Flexo
La mia conoscenza della CPU è piuttosto vecchia, ma ogni istruzione di turno che ho visto cambia di un bit, quindi è necessario eseguire un ciclo per spostarsi più di una volta. Suppongo sia possibile che le moderne CPU abbiano istruzioni di spostamento che si spostano di un numero specificato di bit in un ciclo di clock. –
Sulla mia macchina 'int test (int i) { return i << 30; } 'diventa' sall $ 30,% eax' – Flexo